实验五_二叉树与最优二叉树_09082229刘增鹏

1、实验5二叉树与最优二叉树一、实验要求1、了解树和二叉树的特性，以及它们在实际问题中的应用。2、掌握树和二叉树的实现方法以及它们的基本操作，学会运用树和二叉树 来解决问题。二、实验题目1、用菜单驱动的手法，编写一个完整的程序，生成一棵二叉树，求二叉树 的高度，求二叉树的叶子结点数，输出二叉树的所有结点。2、编写一个完整的程序实现，利用哈夫曼算法建立哈夫曼树，并输出这棵 树中所有结点数据。三、算法描述二叉树：一般常用的是动态链式存储，这时一般不用担心空间溢出问题， 也不必关心存储管理的细节（由系统完成），这使我们能用更多的精力去考虑其 他问题。在此用动态链表存储二叉树。二叉链表是二叉树最常用的存储

2、结构，其中每个结点除了存储结点本身的 数据外，还设置两个指针域Ichild和rchild，分别指向该结点的左孩子和右孩 子。这是二叉树链式存储的二指针形式。就像单链表由头指针惟一确定一样， 一个二义链表也由指向根结点的根指针惟一确定。为了某些运算的方便，也可 给二义链表增加头结点（但一般并没有这样做）。二叉树的生成是指如何在内存中建立二叉树的存储结构。建立顺序存储结 构的问题较简单，这里仅讨论如何建立二叉链表。要建立二叉链表，就需要按 照某种方式输人二叉树的结点及其逻辑信息。注意到对二叉树遍历时，不仅得 到了结点信息，而且由序列中结点的先后关系还可获得一定的逻辑信息，如果 这些信息足够，就可根

3、据遍历序列生成相应的二叉树二叉树的生成方法就是基于遍历序列的，相当于遍历问题的逆问题，即由 遍历序列反求二叉树，这需要分析和利用二叉树遍历序列的特点。哈夫曼算法（最优二叉树）：在许多应用中，常常将树中结点赋予一个有某种 意义的实数，称为该结点的权。结点到树根之间的路径长度与该结点权的乘积 称为该结点的带权路径长度。树的（外部）带权路径长度（Weighted Path Length），定义为树中所有叶于结点的带权路径长度之和，通常记为：WPL=芝 wli=1其中，n表示子结点的数目，w和分别表示叶结点i的权值和它到根之间的路径长度。在权为w1，w2,，wn的n个叶结点的所有二叉树中，带权路径 长

4、度WPL最小的二叉树.n（1）首先，根据给定的n个权值w1，w2，wn构造含有n棵二叉树的森林F=T；，T2，T ，其中每棵二叉树T.中只有一个权值为W.的 根结点，没有左右子树。 11（2）在森林F中选出两棵根结点权值最小的树（当这样的树不止两棵树 时，可从中任选两棵），将这两棵树合并成一棵新的二叉树。这时会增加一个新的根结点， 它的权取为原来两棵树的根的权值之和，而原来的两棵树就作为它的左右子树 （谁左，谁右无关紧要）。（3）对新的森林F重复（2），直到森林F中只剩下一棵树为止。这棵树 便是哈大曼树。由算法知，哈夫曼树不一定惟一（但WPL是相同的，并且都为最小）。原 因在于每次合并时，原两

5、棵树谁左谁右、以及候选的两棵树有多个时选哪两个 等。在哈夫曼算法中，初始森林共有n棵二叉树，每棵树中仅有一个结点，它 们既是根，又是叶子。算法的第二步是将当前森林中的两棵根结点权值最小的 二叉树合并成一棵新二叉树。每合并一次，森林中就减少一棵树。显然，要进 行nl次合并，才能使森林中二叉树的数目由n棵减少到只剩一棵，即最终的 哈夫曼树。另外，每合并一次都要产生一个新结点，合并n- l次共产生n- l个新结点。 由此可知，最终求得的哈大曼树中共有n+（nl）=2n1个结点，其中的叶 结点就是初始森林中的n个孤立结点。在哈夫曼树中，每个分支结点都是合并过程中产生的，它们的度为2,所 以树中没有度为

6、1的分支结点。四、程序清单#include#include#include#define M 200#define null 0#define n 8叶子结点数，假设为20#define m 15 结点总数#define max 1000typedef char Etype; /* 定义数据类型 */typedef struct BiTNode/* 定义结点类型 */ Etype data;struct BiTNode *lch,*rch;/*左 右子树 */ BiTNode,*BiTree;BiTree queM;int front=0,rear=0;int count=0;BiTNode

7、*t,*p;typedef int datatype;typedef struct float weight;int parent,lchild,rchild;hftree; 结点类型hftree treem+1,tree2m+1;哈夫曼树类型，数组从0号单元开始使用哈夫曼树向量/*建立二叉树(层次法)*/BiTNode *creat_bt1()(BiTNode *t,*p,*v20;int i,j; Etype e;printf(输入二叉树各结点的编号和对 应的值(用空格隔开)：，scanf(%d %c”,&i,&e);while(i!=-1)(p=(BiTNode*)malloc(size

8、of(BiTNode);p-data=e;p-lch=NULL;p-rch=NULL;vi=p;if(i=1)t=p;else( j=i/2;if(i%2=0)vj-lch=p;else vj-rch=p;printf(输入二叉树各结点的编号和对应的值(输入i为-1时结束)：，scanf(%d %c”,&i,&e);return(t);/先根法建立二叉树BiTNode *creat_bt2()(BiTNode *t;char ch;fflush(stdin);scanf(%c”,&ch);if(ch=)return null;else(t=(BiTNode*)malloc(sizeof(BiT

9、Node);t-data=ch;t-lch=creat_bt2();t-rch=creat_bt2();return t;void huffman(hftree tree)( int i,j,p1,p2,kz,ky,exchange; /p1,p2 十己当 前选的权值最小的两棵树根结点在向量T 中的下标float sm1,sm2;for(i=1;i=n;i+)(/初始化，根结点(叶子)的双亲和左、右孩子指针置为-1treei.parent=0;treei.lchild = treei.rchild=0;treei.weight=0.0;printf(Hello huffman!n);print

10、f(t请输入d个叶子结点的权值： n,n);for(i=1;i=n;i+)输入n个叶子的权值( scanf (%f”,&treei.weight); for(i=1;i=n;i+)printf(%2.2f ”,treei.weight);printf(nn);for(i=n+1;i=m;i+)/第 i 次合并，产生第i棵新树(结点).共进行n-l次合并。(p1=p2=0;/此句可不要sm1=sm2=max;/max 为float型的最大值,它大于所有结点权值for (j=1;j=i-1;j+)从第0i-1棵树中找两个权值最小的根结点，/作为第i个生成的新树( if (treej.parent

11、!= 0) continue;/ 不考虑已合并的点,双亲域不为-1时就不是 根if(treej.weightsm1)/修改最小权和次小权及位置( sm2=sm1;/sml中记当前找到的最小者权值,sm2记次小者 权值sm1= treej.weight;p2=p1; /pl 中记当 前找到的权值最小者结点的下标，/ p2记当前权值次小者结 点的下标p】=j；else if(treej.weight0;i-) printf(%4d”,i);printf(%10d: ,treei.parent);k=treei.parent;printf(%5.2f,treek.weight);printf(%10

12、d: ,treei.lchild);k=treei.lchild;printf(%5.2f,treek.weight);printf(%10d: ,treei.rchild);k=treei.rchild;printf(%5.2f,treek.weight);printf(%10.2fn,treei.weight);printf(Print end！ nn);void preorder(BiTNode *p )/* 先序遍历二叉 树*/ if(p) printf(%c ,p-data);preorder(p-lch);preorder(p-rch); void inorder(BiTNode

13、*p) /* 中序遍历*/ if(p) inorder(p-lch);printf(%c ,p-data);inorder(p-rch); void postorder(BiTNode *p) /*后序遍历 */ if(p) postorder(p-lch);postorder(p-rch);printf(%c ,p-data);void enqueue(BiTree T)( if(front!=(rear+1)%M)( rear=(rear+1)%M;querear=T;BiTree delqueue()( if(front=rear)return NULL;front=(front+1)%

14、M;return (quefront);void levorder(BiTree T)/*层次遍历二叉树 */( BiTree p;if(T)( enqueue(T);while(front!=rear)( p=delqueue();printf(%c ,p-data);if(p-lch!=NULL)enqueue(p-lch);if(p-rch!=NULL)enqueue(p-rch);int treedepth(BiTree bt)/*二 叉树高度*/( int hl,hr,max1;if(bt!=NULL)( hl=treedepth(bt-lch);hr=treedepth(bt-rc

15、h);max1=(hlhr)? hl:hr;return(max1+1);else return(0);void prtbtree(BiTree bt,int level)/*打 印 */ int j;if(bt) prtbtree(bt-rch,level+1);printf(%dn,bt-data);prtbtree(bt-lch,level+1);void exchange(BiTree bt)/*交换二叉树左右 子树*/ BiTree p;if(bt) p=bt-lch;bt-lch=bt-rch;bt-rch=p;exchange(bt-lch);exchange(bt-rch);i

16、nt leafcount(BiTree bt) /* 叶子结点数*/ if(bt!=NULL) leafcount(bt-lch);leafcount(bt-rch);if(bt-lch=NULL)&(bt-rch=NUL L)count+;return(count);void paintleaf(BiTree bt)/* 叶子结点值 */ if(bt!=NULL)if(bt-lch=NULL&bt-rch=NULL)printf(%d ,bt-data);paintleaf(bt-lch);paintleaf(bt-rch);void print_menu()printf(主 菜单); pr

17、intf(n 1.建立二叉树(层次发)”)； printf(n 2.建立二叉树(先根法); printf(n 3.先序递归遍历二叉树”)；printf（n 4.中序递归遍历二叉树”）；break;printf（n 5.后序递归遍历二叉树”）； printf（n 6.层次遍历二叉树”）； printf（n7.计算二叉树的高度和叶子结点个数”）；printf（n8.建立哈夫曼树”）；printf（n 9.打印哈夫曼树”）；printf（n 0.打印二叉树”）；printf（n E.结束程序运行”）；printf（n）；case 3:if(t) printf(先序遍历二 叉树:，preorder(t

18、);printf(n);else printf(该二叉树 为空!n);break;printf(n 请选择：n)；char chioce_menu()( char ch;for(；)( scanf(%c”,&ch);if(chE)printf(”输入错误，重新选择：n”); elsebreak;case 4:if(t) printf(中序遍历 二叉树:，inorder(t);printf(n);else printf(该二叉树 为空!n);break;return ch；main()( char x;do( print_menu();switch(chioce_menu()(case 1:t=

19、creat_bt1();break;case 5:if(t) printf(后序遍历 二叉树:，postorder(t);printf(n);else printf(该二叉树 为空!n);break;/*建立二叉树算法*/case 2: printf（t先根遍历 建立二叉树：n）;printf（t 请输入二 叉树结点的值！ n）;printf（可以输那 个值均为字母或（n100）字符间以回车 换行，想结束时输多个：n）;case 6:if(t)printf(-层次遍历二叉树:，levorder(t);printf(n);else printf(该二叉树 为空!n);break;t=creat_bt2();case 7:if(t)printf(二叉树的高度为:dn”,treedepth(t);printf(二叉树的叶 子结点数为:dn”,leafcount