哈夫曼树例题/*在给定权值为w1，w2…wn的n个叶结点所构成的所有扩充二元树中，WPL=∑wj·lj最小的称为huffman树哈夫曼树的构造算法：1由给定的n个权值{w0,w1,w2,…,wn-1}，构造具有n棵扩充二元树的森林F={T0,T1,T2,…,Tn-1}，其中每棵扩充二叉树Ti只有一个带权值wi的根结点,其左、右子树均为空。2重复以下步骤,直到F中仅剩下一棵二元树为止：①在F中选取两棵根结点的权值最小的扩充二元树,做为左、右子树构造一棵新的二元树，且置新的二元树的根结点的权值为其左、右子树上根结点的权值之和。②在...
/*在给定权值为w1，w2…wn的n个叶结点所构成的所有扩充二元树中，WPL=∑wj·lj最小的称为huffman树哈夫曼树的构造算法：1由给定的n个权值{w0,w1,w2,…,wn-1}，构造具有n棵扩充二元树的森林F={T0,T1,T2,…,Tn-1}，其中每棵扩充二叉树Ti只有一个带权值wi的根结点,其左、右子树均为空。2重复以下步骤,直到F中仅剩下一棵二元树为止：①在F中选取两棵根结点的权值最小的扩充二元树,做为左、右子树构造一棵新的二元树，且置新的二元树的根结点的权值为其左、右子树上根结点的权值之和。②在F中删去这两棵二元树。③把新的二元树加入F。*/#include#definen5#definem2*n-1typedefstruct{doubleweight;intlchild;intrchild;intparent;}HTNODE;/*静态三叉链表表示，又是游标表示即使用整型变量标记/指向节点*/typedefHTNODEHuffmanT[m];/*初始值，依据教材的例子，存放相应数据P116*/voidInitHT(HuffmanTT){/*每个节点就是一个树，因此是森林F，共有n棵二叉树*/T[0].weight=0.12;T[0].parent=-1;T[0].lchild=-1;T[0].rchild=-1;/*书中代码从1开始，不良习惯！*/T[1].weight=0.40;T[1].parent=-1;T[1].lchild=-1;T[1].rchild=-1;T[2].weight=0.15;T[2].parent=-1;T[2].lchild=-1;T[2].rchild=-1;T[3].weight=0.08;T[3].parent=-1;T[3].lchild=-1;T[3].rchild=-1;T[4].weight=0.25;T[4].parent=-1;T[4].lchild=-1;T[4].rchild=-1;/*可以只存放前5个节点，后面的是为了与结果比较*/T[5].weight=0;T[5].parent=-1;T[5].lchild=-1;T[5].rchild=-1;T[6].weight=0;T[6].parent=-1;T[6].lchild=-1;T[6].rchild=-1;T[7].weight=0;T[7].parent=-1;T[7].lchild=-1;T[7].rchild=-1;T[8].weight=0;T[8].parent=-1;T[8].lchild=-1;T[8].rchild=-1;}/*打印HuffmanT[m]数组元素，每个元素是一个哈夫曼树的结构体*/voidPrintHT(HuffmanTT){inti;for(i=0;iT[i].weight)/*取较小的*/&&(T[i].parent==-1)/*没有合并或者合并后双亲指针为空的节点*/&&(*p2!=i))/*?与p2不同，取最小的两个节点!正是因此，导致左右孩子错误?*/*p1=i;for(j=0;j<=nn;j)/*同上*/if((T[*p2].weight>T[j].weight)&&(T[j].parent==-1)&&(*p1!=j))*p2=j;/*书中没有此判断代码！确保左子树的权值小于右子树*/if(T[*p1].weight>T[*p2].weight){temp=*p1;*p1=*p2;*p2=temp;}}/*第四版的教材，国家级精品课程还是这样，可怜中国IT，更可悲中国GIS！*/voidCreateHT(HuffmanTT){inti,p1,p2;InitHT(T);/*初始化*/PrintHT(T);/*打印初始化后情况*/for(i=n;i
本文档为【哈夫曼树例题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483