实验报告(二叉树的构建、基本操作和遍历)

实验报告课程：数据结构（c语言） 实验名称：二叉树的构建、基本操作和遍历系别：数字媒体技术 实验日期： 专业班级：媒体161 组别：无 姓名： 学号：实验报告内容验证性实验一、 预习准备：实验目的：1、熟练掌握二叉树的结构特性，熟悉二叉树的各种存储结构的特点及适用范围；2、熟练掌握二叉树的遍历方法及遍历算法；3、掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。实验环境：Widows操作系统、VC6.0实验原理：1. 定义：树：树(tree)是n(n0)个结点的有限集T，其中，有且仅有一个特定的结点，称为树的根(root)。当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)二叉树：二叉树是n(n=0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。哈夫曼树: 最优二叉树赫夫曼树设有n个权值w1,w2,wn，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫Huffman树。2. 特点：树：树中至少有一个结点根树中各子树是互不相交的集合二叉树：每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒哈夫曼树：一棵有n个叶子结点的Huffman树有2n-1个结点采用顺序存储结构动态分配数组存储3. 表示：遍历二叉树：先序遍历：先访问根结点,然后分别先序遍历左子树、右子树中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：先后序遍历左、右子树，然后访问根结点按层次遍历：从上到下、从左到右访问各结点构造Huffman树的方法Huffman算法（1) 根据给定的n个权值w1,w2,wn，构造n棵只有根 结点的二叉树，令起权值为wj；(2) 在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和；(3) 在森林中删除这两棵树，同时将新得到的二叉树加入森林中重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。4. 实验内容和要求：（1）二叉树 建立如下图所示的二叉树：ABCDEFG 要求：1、建立带头结点的二叉树，将二叉树初始化为空； 2、依次将二叉树的所有结点插入，建立上图所示的二叉树； 3、用户可由键盘输入数据实现对二叉树各结点的插入、删除等操作； 4、打印二叉树； 5、对二叉树实现前序、中序、后序遍历；算法思想： 建立一棵只有头结点的二叉树，并通过调用插入左子树和插入右子树操作，依次将上图中的结点插入二叉树中，利用二叉树的特殊中序遍历方法将该树以凹入表示法打印显示。最后，调用二叉树的前序、中序、后序遍历函数对二叉树进行遍历，并显示遍历结果。(2)、哈夫曼树设有字符集A、B、C、D，各字符在电文中出现的次数集为1，3，5，7，设计各字符的哈夫曼编码。要求：1、构造字符集的哈夫曼树，其结点数据结构如下：weightflagparentleftChildrightChild 2、由哈夫曼树构造哈夫曼编码，输出权值及其对应的编码。算法思想： 首先，由给定的n个权值构造有2n-1个结点的哈夫曼树。在哈夫曼树中，其叶结点的权值为相应的给定权值，非叶结点的权值为其孩子结点的权值之和。哈夫曼树构造过程如下： 1. 根据给定的 n 个权值 w1，w2，wn，构成的 n 棵二叉树的森林 F = T1，T2，Tn，其中每棵二叉树 Ti 中只有一个权值为 wi 的结点，其左、右子树均为空；2. 在 F 中选取根结点的权值最小和次小的两棵树作为左、右子树构造一棵新的二叉树，且置新二叉树的根结点的权值为其左、右子树上根结点的权值之和；3. 在 F 中删除这两棵二叉树，并将新二叉树加入到 F 中；4. 重复 2 和 3，直到 F 中只含一棵树为止。这棵树就是哈夫曼树。其次，对n个结点的哈夫曼树进行不等长编码。保证任何一个字符的哈夫曼编码不为另一字符的哈夫曼编码的前缀。二、 实验过程： 实验中的关键语句：前序遍历中序遍历什么的都是一个道理，只是输出的时候的顺序不同，都是先访问左孩子或者右孩子后在访问另一边 (1) 先序遍历二叉树T的递归算法Status PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) Status PrintElement( ElemType e ) printf( e ); return OK; PreOrderTraverse(T, PrintElement); if (T) if (Visit(T-data) if (PreOrderTraverse(T-lchild, Visit) if (PreOrderTraverse(T-rchild, Visit) return OK; return ERROR; else return OK; / PreOrderTraverse (2) 中序遍历二叉树T的非递归算法Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) Stack S; BiTree p; InitStack(S); Push(S, T); while (!StackEmpty(S) while (GetTop(S, p) & p) Push(S, p-lchild); Pop(S, p); if (!StackEmpty(S) Pop(S, p); if (!Visit(p-data) return ERROR; Push(S, p-rchild); return OK; / InOrderTraverse (3)void Huffman:CreateHTree(int a,int n) HTree=new HNode 2*n-1;for(int i=0;in;i+) HTreei.weight=ai; HTreei.lchild=-1; HTreei.rchild=-1; HTreei.parent=-1; static int k=0; int bb1000; static int x; static int y; int min=1000; for(int jj=0;jjn;jj+) if(HTreejj.weightmin) min=HTreejj.weight; x=jj; bbk=x; k+; int _min=1000; for(int jjj=0;jjjn;jjj+) int kk; for( kk=0;kk=HTreex.weight) if(HTreejjj.weight_min) _min=HTreejjj.weight; y=jjj; bbk=y;k+; HTreex.parent=HTreey.parent=n; HTreen.weight=HTreex.weight+HTreey.weight;HTreen.lchild=x;HTreen.rchild=y;HTreen.parent=-1; for(int ii=n+1;ii2*n-1;ii+) min=1000; for(int jj=0;jjii;jj+) int kk; for( kk=0;kk=HTreey.weight ) if(HTreejj.weightmin) min=HTreejj.weight; x=jj; bbk=x; k+; int _min=1000; for(int jjj=0;jjjii;jjj+) int kk; for( kk=0;kk=HTreex.weight) if(HTreejjj.weight_min) _min=HTreejjj.weight; y=jjj; bbk=y;k+; HTreex.parent=HTreey.parent=ii; HTreeii.weight=HTreex.weight+HTreey.weight;HTreeii.lchild=x;HTreeii.rchild=y;HTreeii.parent=-1; 编写及调试程序中遇到的问题及解决方法:（1）执行程序时程序停止运行。解决：看到程序停止运行，推测可能的原因：遇到死循环、参数设置不合理或者结构体没有造好。首先对结构体进行了检查，各个成员声明正常无误，在对程序进行调试，程序正常跳出循环，因此最可能是自定义函数的参数设置的不合理，因此对调用的自定义函数进行相应的改动，将参数由具体类型改为指针类型后，程序正常运行。（2）程序不停的输出同一个结点的数据。解决：分析运行结果可知，第一不停的输出证明遇到了死循环，第二输出的是同一个结点的数据，表示指针没有按预期进行指向，首先对程序进行调试，发现程序没有添加循环结束条件，添加循环结束条件后，只能输出树的部分结点的数据，对标志位进行修改后，程序运行正常，也能正确输出遍历结果。实验总结： 1. 实验结果及分析：运行结果显示可以实现实验要求。2. 实验总结：遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。 递归方法比较简单，首先获得结点指针如果指针不为空