最优二叉树(哈夫曼树)

1、实验4.2最优二叉树（哈夫曼树）、实验的目的要求1、了解树和哈夫曼树的特性，以及它们在实际问题中的应用。2、掌握树和哈夫曼树的实现方法以及它们的基本操作，学会运用树和二叉树来解决问 题。、实验的主要内容1、请设计一个算法，对于给定的n个结点的权值，建立一棵哈夫曼树。 具体要求如下: 算法输入：n个结点的权值。 算法输出：哈夫曼树，打印出哈夫曼树的所有的结点序号、双亲结点、左孩子、右孩 子和权值。 测试数据：设结点数n=7,权值分别为7、5、2、3、8、10、20 ；设结点数n=8,权值分别为 7、19、2、6、32、3、21、10。三、解题思路图5-L哈夫曼啊示世图1、 哈夫曼树的存储结构：用

2、哈夫曼算法求得的哈夫曼树中共有 2n-l个结点，其中n个叶结点是初始森林中的n个孤立结点，其余 n-1个结点是构造过程中生成的度为2的结点。因此，有2n-l个结点的哈天曼树可用大小为2n-l的向量来存储。每个结点包括4个域：权值域、左/右孩子域和双亲域，双亲域不但可用来存放双亲在向量中的下标，而且可区分该结点是否为根结点。因为在当前森林中合并两棵二叉树时，必须在森林的所有结点中先取两个权值最小的根结点，所以有必要为每个结点设置一个标记以区分根和非根结点。2、解题步骤如下： 将哈天曼树向量tree中的2n-l个结点初始化：即将各结点中的三个指针和权值均置 为0。 读入n个权值放入向量tree的前

3、n个分量中，它们是初始森林中的n个孤立的根结点上的权值。 对森林中的树进行n I次合并，共产生 n I个新结点，依次放入向量tree的第t个分量中（n+l wtw m）（第t个分量的下标值为t 一 I）。每次合并的方法如下：在当前森林的所有结点treej(O j i 一 l, i=t-l)中，选取具有最小权值和次小权值的两个根结点，分别用pl和p2记住这两个根结点在向量tree中的下标。将根为treepl和treep2的两棵树合并，使其成为新结点treei的左右孩子，得到一 棵以新结点treei为根的二叉树。同时修改treepl和treep2的双亲域，使其指向新结点treei，这意味着它们在当

4、前森林中已不再是根，将treepl和treep2的权值相加后，作为新结点treei的权值。05-2哈夭曼树的三叉链表存储形式示盍图四、原程序清单c+程序#in clude#in clude#in cludeusing n amespace std;#defi ne MAXVAL 10000000 typedef int datatype;typedef structdouble weight;int num;datatype lchild,rchild,pare nt; htree;htree tree100;int n, m,flag=1;void create()int i,j,p1,p2

5、;double small1,small2,w;coutncinn;/定义一个足够大的数，方便之后的操作定义哈夫曼树结构体类型结点的权值/结点的左、右孩子指针和父指针/定义全局变量，方便操作n表示预处理的结点数，m表示处理的结点总数/健立哈夫曼树的函数/i,j用于循环语句，p1、p2用于记录操作结果 /操作的中间变量请输入预处理的结点数：;m=2* n-1; if(n=0) printf(n*n);printf(这是一棵空树n);printf( *n); return;printf(n*n);printf(”请依次输入个结点的权值(各权值以空格隔开)n);prin tf(*n)for(i=1;

6、i w; treei.weight=w; treei. num=i; treei.pare nt=O; treei.lchild=O; treei.rchild=O;for(i=n+1;i=m;i+)p仁0;p2=0;small1=MAXV AL;small2=MAXV AL;for(j=1;j=i-1;j+) if(treej.pare nt=0)if(treej.weightsmall1)small2=small1;small仁treej.weight; p2=p1;p1=j;else if(treej.weightsmall2) small2=treej.weight; p2=j;tre

7、ep1.pare nt=i;treep2.pare nt=i;treei. num=i;treei.pare nt=O;treei.lchild=p1;treei.rchild=p2;treei.weight=treep1.weight+treep2.weight; prin tf(n* n);printf（”哈弗曼树初始化完毕n）;printf(* n);void prin t1(htree t)用于输出哈夫曼树的先序序列coutttt .num tt.weighte ndl; if(t.lchild!=O)prin t1(treet.lchild);if(t.rchild!=0)prin

8、t1(treet.rchild);void prin t2(htree t)用于输出哈夫曼树的中序序列if(t.lchild!=0)prin t2(treet.lchild);coutttt .num tt.weighte ndl; if(t.rchild!=0)prin t2(treet.rchild);void prin t3(htree t)用于输出哈夫曼树的中序序列if(t.lchild!=0)prin t3(treet.lchild);if(t.rchild!=0)prin t3(treet.rchild);coutttt .num tt.weightb)return a;retur

9、n b;int mai n()stri ng i,j; while(1) printf(n*printf(”欢迎使用菜单驱动程序n);printf( * if(flag=1)printf(1初始化哈弗曼树n);/第一级菜单prin tf(n请选择您要的操作:);cin i;if(i=1)create。；flag=0;elseprintf(n*printf(”操作错误n);printf(* n);con ti nue;printf(”1重新初始化哈弗曼树n);/第二级菜单printf(”2输出哈弗曼树的高度n);printf(”3输出哈弗曼树的叶子结点的个数n);printf(”4输出哈弗曼树n

10、);printf(”5清屏 n);printf(”0结束操作n);prin tf(n请选择您要的操作:;);cin i;if(i=1)create(); else if(i=2) if(n=0)prin tf(这是一棵空树，高度为0n);printf(n*printf(*n); elseprintf(n*printf(”该树的高度为 dn ,high(treem);printf( *else if(i=3)if(n=0)printf(n*printf(”这是棵空树，叶子结点的个数为0n);printf( *elseprintf(n* printf(该树的叶子结点的个数为%dn,n);print

11、f( *else if(i=4)if(n=0) printf(n* printf(这是一棵空树n);printf( * con ti nue; while(1)printf(”欢迎使用菜单驱动程序n);printf(n*prin tf(*n)printf(”1输出哈弗曼树的先序序列n); II第三级菜单printf(”2输出哈弗曼树的中序序列n ”)；printf(”3输出哈弗曼树的后序序列n ”)；printf(”4返回上层n);printf(”5清屏 n);printf(”0结束操作n);prin tf(n请输入您要的操作：”)；fflush(stdi n); cinj; if(j=1)p

12、rintf(n*n)；printf(”哈弗曼树的先序序列如下(左为结点序号，右为为结点权值prin tf(*n)；prin t1(treem);else if(j=2)printf(n*n)；prin tf(哈弗曼树的中序序列如下(左为结点序号，右为为结点权值prin tf(*n)；prin t2(treem);else if(j=3)printf(n*n);printf(”哈弗曼树的后序序列如下(左为结点序号，右为为结点权值)n);)n);)n);printf(“*n);prin t3(treem);else if(j=4)break;else if(j=5)system(cls); els

13、e if(j=0) prin tf(n*printf(”谢谢使用，再见n);printf(*n);return 1;elseprintf(n* printf(操作错误 n);printf( * else if(i=5)system(cls);else if(i=O)prin tf(n* n);printf(”printf(谢谢使用，再见n);* n);return 1; elseprintf(n*printf(操作错误n);printf( *运行结果*欢迎使用菜单驱动程序*1初始化哈夫曼树请选择您要的操作:op*操作错误*欢迎使用菜单驱动程序*1初始化哈夫曼树请选择您要的操作:1请输入预处理的

14、结点数：0*这是一棵空树*欢迎使用菜单驱动程序1. 重新初始化哈夫曼树2输出哈夫曼树的高度3. 输出哈夫曼树的叶子结点的个数4. 输出哈夫曼树5. 清屏0.结束操作请选择您要的操作:2*这是一棵空树，高度为 0*欢迎使用菜单驱动程序*1. 重新初始化哈夫曼树2. 输出哈夫曼树的高度3. 输出哈夫曼树的叶子结点的个数4. 输出哈夫曼树5. 清屏0.结束操作请选择您要的操作:3*这是一棵空树，叶子结点的个数为0*欢迎使用菜单驱动程序*1. 重新初始化哈夫曼树2. 输出哈夫曼树的高度3. 输出哈夫曼树的叶子结点的个数4. 输出哈夫曼树5. 清屏0.结束操作请选择您要的操作:4*这是一棵空树*欢迎使用

15、菜单驱动程序*1. 重新初始化哈夫曼树2输出哈夫曼树的高度3. 输出哈夫曼树的叶子结点的个数4. 输出哈夫曼树5. 清屏0.结束操作请选择您要的操作:6*操作错误*欢迎使用菜单驱动程序*1. 重新初始化哈夫曼树2. 输出哈夫曼树的高度3. 输出哈夫曼树的叶子结点的个数4. 输出哈夫曼树5. 清屏0.结束操作请选择您要的操作:1请输入预处理的结点数：5*请依次输入个结点的权值（各权值以空格隔开）*1 2 3 4 5*哈夫曼树初始化完毕*欢迎使用菜单驱动程序*1. 重新初始化哈夫曼树2输出哈夫曼树的高度3输出哈夫曼树的叶子结点的个数4. 输出哈夫曼树5清屏0.结束操作请选择您要的操作:2*该树的高

16、度为 4*欢迎使用菜单驱动程序*1. 重新初始化哈夫曼树2. 输出哈夫曼树的高度3. 输出哈夫曼树的叶子结点的个数4. 输出哈夫曼树5. 清屏0.结束操作请选择您要的操作:3*该树的叶子结点的个数为5*欢迎使用菜单驱动程序*1. 重新初始化哈夫曼树2. 输出哈夫曼树的高度3. 输出哈夫曼树的叶子结点的个数4. 输出哈夫曼树5. 清屏0.结束操作请选择您要的操作:4*欢迎使用菜单驱动程序*1.输出哈夫曼树的先序序列2输出哈夫曼树的中序序列3输出哈夫曼树的后序序列4返回上层5清屏0结束操作请输入您要的操作：1*哈夫曼树的先序序列如下（左为结点序号，右为为结点权值）*9157 63 36 31 12

17、 28 94 45 5*欢迎使用菜单驱动程序*1输出哈夫曼树的先序序列2输出哈夫曼树的中序序列3输出哈夫曼树的后序序列4返回上层5清屏0结束操作请输入您要的操作：2*哈夫曼树的中序序列如下（左为结点序号，右为为结点权值）*3 37 6116 32 29 154 48 9*欢迎使用菜单驱动程序*1输出哈夫曼树的先序序列2输出哈夫曼树的中序序列3输出哈夫曼树的后序序列4返回上层5清屏0结束操作请输入您要的操作：3*哈夫曼树的后序序列如下（左为结点序号，右为为结点权值）*3 311226 37 64 45 58 99 15*欢迎使用菜单驱动程序*1输出哈夫曼树的先序序列2输出哈夫曼树的中序序列3输出哈夫曼树的后序序列4返回上层5清屏0结束操作请输入您要的操作：6*操作错误*欢迎使用菜单驱动程序*1输出哈夫曼树的先序序列2输出哈夫曼树的中序序列3输出哈夫曼树的后序序列4返回上层5清屏0结束操作请输入您要的操作：4*欢迎使用菜单驱动程序*1.重新初始化哈夫曼树2输出哈夫曼树的高度3. 输出哈夫曼树的叶子结点的个数4. 输出哈夫