实验题目
树和二叉树
小组合作
否
姓名
班级
学    号
一、实验目的
(1)掌握树的相关概念,包括树、结点的度、树的度、分支结点、叶子结点、儿子结点、双亲结点、树的深度、森林等定义。
(2)掌握二叉树的概念,包括二叉树、满二叉树和完全二叉树的定义。
(3)掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码产生方法。
二．实验环境
装有Visual C++6.0的计算机一台。
三、实验内容与步骤
1、二叉树遍历递归算法：
假设二叉树采用二叉链存储结构存储，是设计一个算法，输出一棵给定二叉树的所有叶子节结点。
#include "stdafx.h"
#include "exam7-8.cpp"
int main(int argc, char* argv[])
{
    BTNode *b;
    CreateBTNode(b,"A(B(D(,G)),C(E,F))");
    printf("b:");DispBTNode(b);printf("\n");
    printf("从左到右输出所有叶子结点:");DispLeaf(b);printf("\n");
    printf("从右到左输出所有叶子结点:");DispLeaf1(b);printf("\n");
    return 0;
}
假设二叉树采用二叉树链式存储结构，设计一个算法输出从根结点到每个叶子结点的路径之逆（因为树中路径是从根结点到其他结点的结点序列，就是求叶子结点及其双亲结点、该双亲结点的双亲结点，直到根结点的序列，或者说求叶子结点及其所有祖先结点的序列）。要求采用后根遍历非递归算法。
#include "stdafx.h"
#include "exam7-12.cpp"
int main(int argc, char* argv[])
{
    BTNode *b;
    CreateBTNode(b,"A(B(D(,G)),C(E,F))");
    printf("b:");DispBTNode(b);printf("\n");
    printf("输出所有从叶子结点到根结点的序列:\n");
    AllPath1(b);
    return 0;
}
设计一个算法将二叉树的顺序存储结构转换成二叉链式存储结构。
#include "stdafx.h"
#include "exam7-14.cpp"
int main(int argc, char* argv[])
{
        int i,n=10;
    BTNode *b;
    SqBTree a;
    ElemType s[]="0ABCD#EF##G";
    for (i=0;i<=n;i++)
        a.data[i]=s[i];
    a.n=n;
    b=trans(a,1);
    printf("b:");DispBTNode(b);printf("\n");
    return 0;
}
四、实验过程与分析
1. 先序遍历
先序遍历二叉树的过程是：
(1) 访问根结点；(2) 先序遍历左子树；(3) 先序遍历右子树。
2. 中序遍历
中序遍历二叉树的过程是：
(1) 中序遍历左子树；(2) 访问根结点；(3) 中序遍历右子树。
3. 后序遍历
后序遍历二叉树的过程是：
(1) 后序遍历左子树；(2) 后序遍历右子树；(3) 访问根结点。
五、实验总结
通过此次试验我对二叉树的遍历有了一定的了解，仅有一个序列无法确定这棵二叉树的树形。但是，如果同时知道一棵二叉树的先序序列和中序序列，或者同时知道中序序列和后序序列，就能确定这棵二叉树。
六、指导教师评语及成绩
有完整的实验过程，运行出了正确的实验结果，很好的达到了实验的要求及实验目的。在实验过程中，该同学有效的发现了实验中的问题，并且很好的解决了问题，达到了培养解决问题的能力。
二叉树定义

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。