6781人阅读
一：什么是最优二叉树？
从我个人理解来说，最优二叉树就是从已给出的目标带权结点(单独的结点) 经过一种方式的组合形成一棵树.使树的权值最小. 最优二叉树是带权路径长度最短的二叉树。根据结点的个数，权值的不同，最优二叉树的形状也各不相同。它们的共同点是：带权值的结点都是叶子结点。权值越小的结点，其到根结点的路径越长
官方定义：
在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。
二：下面先弄清几个几个概念：
1.路径长度
在树中从一个结点到另一个结点所经历的分支构成了这两个结点间的路径上的分支数称为它的路径长度
2．树的路径长度
&&& 　树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。
3．树的带权路径长度(Weighted Path Length of Tree，简记为WPL)
　　结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。
　　结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。
　　树的带权路径长度(Weighted Path Length of Tree)：定义为树中所有叶结点的带权路径长度之和，通常记为：&
&&&&&&&&&&&&&&&&
&&& n表示叶子结点的数目
&&& wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。
&&& 树的带权路径长度亦称为树的代价。
三：用一个例子来理解一下以上概念
【例】给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为：
&&&&&&& (a)WPL=7*2+5*2+2*2+4*2=36
&&&&&&& (b)WPL=7*3+5*3+2*1+4*2=46
&&&&&&& (c)WPL=7*1+5*2+2*3+4*3=35
其中(c)树的WPL最小，可以验证，它就是哈夫曼树。
&&& ① 叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。
&&& ② 最优二叉树中，权越大的叶子离根越近。
&&& ③ 最优二叉树的形态不唯一，WPL最小
四.哈夫曼算法
对于给定的叶子数目及其权值构造最优二叉树的方法，由于这个算法是哈夫曼提出来的，故称其为哈夫曼算法。其基本思想是：
　　(1)根据给定的n个权值wl，w2，…，wn构成n棵二叉树的森林F={T1，T2，…，Tn}，其中每棵二叉树Ti中都只有一个权值为wi的根结点，其左右子树均空。
　　(2)在森林F中选出两棵根结点权值最小的树(当这样的树不止两棵树时，可以从中任选两棵)，将这两棵树合并成一棵新树，为了保证新树仍是二叉树，需 要增加一个新结点作为新树的根，并将所选的两棵树的根分别作为新根的左右孩子(谁左，谁右无关紧要)，将这两个孩子的权值之和作为新树根的权值。
　　(3)对新的森林F重复(2)，直到森林F中只剩下一棵树为止。这棵树便是哈夫曼树。&
&&& ① 初始森林中的n棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子
&&& ② n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点。最终求得的哈夫曼树中共有2n-1个结点。
&&& ③ 哈夫曼树是严格的二叉树，没有度数为1的分支结点。
五：最优二叉树算法具体实现思路
在构造哈夫曼树时，可以设置一个结构数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n－1个结点，所以数组HuffNode的大小设置为2n－1，数组元素的结构形式如下：&&
其中，weight域保存结点的权值，lchild和rchild域分别保存该结点的左、右孩子结点在数组HuffNode中的序号，从而建立起结 点之间的关系。为了判定一个结点是否已加入到要建立的哈夫曼树中，可通过parent域的值来确定。初始时parent的值为－1，当结点加入到树中时， 该结点parent的值为其双亲结点在数组HuffNode中的序号，就不会是－1了。构造哈夫曼树时，首先将由n个字符形成的n个叶结点存放到数组HuffNode的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HuffNode数组中的前n个分量的后面。
具体实现：
1）存储结构
#define n 100
//叶结点数目
#define m 2*n-1
//树中结点总数
typedef struct
//权值，设权值均大于零
intlchild,rchild,
//左右孩子及双亲指针
typedef HTNode HuffmanTree[m]; //哈夫曼树是一维数组
(2)赫夫曼算法的数组法构造
void CreateHuffmanTree(HuffmanTree T)
int i,p1,p2;
//构造哈夫曼树，T[m-1]为其根结点
InitHuffmanTree(T);
InputWeight(T);
//输入叶子权值至T[0．．n-1]的weight域
for(i=n;i&m;i++)
SelectMin(T,i-1,&p1,&p2);//共进行n-1次合并，新结点依次存于T[i]中
//在T[0…i-1]中选择两个权最小的根结点，其序号分别为p1和p2
T[p1].parent=T[p2].parent=i;
T[i].1child=p1;
//最小权的根结点是新结点的左孩子
T[i].rchild=p2;
//次小权的根结点是新结点的右孩子
T[i].weight=T[p1].weight+T[p2].
}//CreateHuffman
C语言实现全部代码：
#include &stdio.h&
#include &stdlib.h&
#define m 100
struct ptree
//定义二叉树结点类型
//定义结点权值
struct ptree *
//定义左子结点指针
struct ptree *
//定义右子结点指针
struct pforest
//定义链表结点类型
struct pforest *
struct ptree *
int WPL=0;
//初始化WTL为0
struct ptree *hafm();
void travel();
struct pforest *inforest(struct pforest*f,struct ptree *t);
void travel(struct ptree *head,int n)
//为验证harfm算法的正确性进行的遍历
struct ptree *p;
if(p!=NULL)
if((p-&lchild)==NULL && (p-&rchild)==NULL) //如果是叶子结点
printf(&%d &,p-&w);
printf(&the hops of the node is: %d/n&,n);
WPL=WPL+n*(p-&w);
//计算权值
travel(p-&lchild,n+1);
travel(p-&rchild,n+1);
struct ptree *hafm(int n, int w[m])
struct pforest *p1,*p2,*f;
struct ptree *ti,*t,*t1,*t2;
f=(pforest *)malloc(sizeof(pforest));
f-&link=NULL;
for(i=1;i&=n;i++)
//产生n棵只有根结点的二叉树
ti=(ptree*)malloc(sizeof(ptree));//开辟新的结点空间
ti-&w=w[i];
//给结点赋权值
ti-&lchild=NULL;
ti-&rchild=NULL;
f=inforest(f, ti);
//按权值从小到大的顺序将结点从上到下地挂在一颗树上
while(((f-&link)-&link)!=NULL)//至少有二棵二叉树
f-&link=p2-&
//取出前两棵树
t=(ptree *)malloc(sizeof(ptree));//开辟新的结点空间
t-&w = (t1-&w)+(t2-&w);
t-&lchild=t1;
t-&rchild=t2;
//产生新二叉树
f=inforest(f,t);
return(t);
pforest *inforest(struct pforest *f,structptree *t)
//按权值从小到大的顺序将结点从上到下地挂在一颗树上
struct pforest *p, *q, *r;
struct ptree *
r=(pforest *)malloc(sizeof(pforest)); //开辟新的结点空间
r-&root=t;
while (p!=NULL)
//寻找插入位置
if(t-&w & ti-&w)
//如果t的权值大于ti的权值
//p向后寻找
//强迫退出循环
r-&link=q-&
q-&link=r;
//r接在q的后面
return(f);
void InPut(int &n,int w[m])
printf(&please input the sum ofnode/n&); //提示输入结点数
scanf(&%d&,&n);
//输入结点数
printf (&please input weight of everynode/n&); //提示输入每个结点的权值
for(int i=1;i&=n;i++)
scanf(&%d&,&w[i]);
//输入每个结点权值
int main( )
struct ptree *
int n,w[m];
InPut(n,w);
head=hafm(n,w);
travel(head,0);
printf(&The length of the best path isWPL=%d&, WPL);//输出最佳路径权值之和
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1597072次
积分：19792
积分：19792
排名：第126名
原创：210篇
转载：41篇
评论：3343条
阅读：77613
阅读：42900
文章：12篇
阅读：62575
文章：18篇
阅读：80902
文章：14篇
阅读：71699
阅读：41095
文章：112篇
阅读：735522
(1)(1)(1)(1)(8)(1)(5)(1)(3)(1)(4)(1)(1)(2)(3)(4)(9)(13)(10)(7)(2)(8)(29)(25)(35)(15)(14)(6)(5)(9)(7)(7)(12)您所在的位置：
& 湖北3C媒体库 & 正文
哈夫曼树和压缩算法
日11:31 　
　　认识哈夫曼树之前首先我们简单的来了解一下二叉树，不难理解，二叉树就是每个节点都只有2个子节点的树状结构，也就分为父节点(parentnode)、左子树(leftchild)和右子树(rightchild)。每个节点最多只能有2个节点，当然也可以更少，比如只有左节点没有右节点或者相反，没有子节点的节点我们称之为叶节点，有子树的称之为根节点。
　　二叉树相关就先介绍到这里，我们还是回到主题。首先，哈夫曼树就是一种特殊的二叉树，也是一种加权二叉树。首先，我们对我们需要储存到二叉树的数据赋予权重，权比较高的放在浅层，权重低的放在深层，并且所有的数据都储存在叶节点。接下来的问题就是如何构造这个哈夫曼树了。
　　举个例子：我们要储存的数据及其权重分别为：a:1|b:4|c:4|d:2|e:7|f:3，下面将通过例子来讲解哈夫曼树的构造方法
　　首先，将数据按权重排序!--
　　Code highlighting produced byActiproCodeHighlighter(freeware)
　　--> a | d | f | b | c | e
　　1 | 2 | 3 | 4 | 4 | 7
　　我们先将权最低的2个节点组成一个二叉树，根节点为A，没有数据，但权重为2个子节点的和，并将他们的根节点放入列表重新排序：
　　Code highlighting produced byActiproCodeHighlighter(freeware)
　　--> A(3) f(3) d(4) c(4) e(7)
　　a(1) b(2)
　　重复上一步骤，取新的根节点为B
　　Code highlighting produced byActiproCodeHighlighter(freeware)
　　-->b(4)c(4) B(6) e(7)
　　A(3) f(3)
　　a(1)b(2)
　　Code highlighting produced byActiproCodeHighlighter(freeware)
　　--> B(6) C(8) e(7)
　　/ \ / \
　　A(3) f(3) d(4) c(4)
　　a(1) b(2)
　　Code highlighting produced byActiproCodeHighlighter(freeware)
　　--> e(7) D(14)
　　B(6) C(8)
　　/ \ / \
　　A(3) f(3) d(4) c(4)
　　a(1) b(2)
　　引用!--
　　Code highlighting produced byActiproCodeHighlighter(freeware)
　　--> E(21)
　　e(7) D(14)
　　B(6) C(8)
　　/ \ / \
　　A(3)f(3) d(4) c(4)
　　a(1) b(2)
　　这个哈夫曼树我们就算完成了，最后将无关的东西去掉：
　　引用!--
　　Code highlighting produced byActiproCodeHighlighter(freeware)
　　--> ○
　　/ \ / \
　　○ f d c
　　大功告成!
　　哈夫曼树的意义就在于可以对其中的数据重新编码，编码方式很简单，左树为0右树为1，每下一层加一个数字，以上图中的例子来说，abcdef对应编码就是：!--
　　Code highlighting produced byActiproCodeHighlighter(freeware)
　　-->|a|1000
　　|b|1001
　　|c|111
　　|d|110
　　|f|101
　　大家不难发现，这几个编码没有任何一个是另一个编码的前置。这是由哈夫曼树的特性决定的，哈夫曼树所有的数据都在页节点，如果出现一个数据是另一个数据编码的前置，这个数据必然在另一个数据的路径前，也就是在根节点，然而这是不可能的，这也确保了解码的唯一性，避免了歧义的出现，就拿刚才的例子来说，01的解码只可能是cdefb而不会是别的。
　　对于程序来说，取得这个编码就牵扯到一个二叉树遍历的问题了，通常来说，遍历一个二叉树可以用递归方式解决，这里举个简单的例子：!--
　　Code highlighting produced byActiproCodeHighlighter(freeware)
　　-->//首先，我们假设节点类为Node，包含getLChild()和getRChild()两个方法
　　//分别取得左子节点和右子节点，然后一个chardata属性储存值
　　//code为储存编码的字符串，Code类为编码类，包含data和code两个个属性
　　public voidviewBTree(Nodend,Stringcode,ListcL){
　　NodeleftNode=nd.getLChild();//取得左子树
　　NoderightNode=nd.getRChild();//取得右子树
　　viewBTree(leftNode,code+0,cL);//递归，编码字符串加0
　　viewBTree(rightNode,code+1,cL);//递归遍历右子树
　　CodenCode=newCode(nd.data,code);//新建编码对象
　　cL.add(nCode);//存入队列
　　当然也有其他方法，这里就不赘述了。
　　哈夫曼树大家应该基本了解了，现在我们就需要应用它做点事了，就是今天的另一个主题：压缩算法。哈夫曼树压缩算法的原理就是对所有的byte进行重新编码，由于哈夫曼树生成的编码是长短不一的。我们可以把出现频率高的byte放在哈夫曼树的上层，出现频率低的放在下层，缩短出现频率高的byte的编码，延长出现频率低的byte的编码，替换掉固定的8位二进制编码，达到压缩的目的。所以一个所有byte完全平均的文件经过哈夫曼树压缩算法后大小不会有变化，然而这个可能性很低，通常一篇文章中总有一些字词出现频率很高，在文件中也是一样，有些byte出现频率也比较高，这种情况越不平均，哈夫曼树压缩算法的压缩效率越高。
　　通过以上原理，我们就需要在对文件压缩前对文件中的所有byte做一个统计，把该byte出现的次数作为它的权，然后生成哈夫曼树，然后遍历生成编码。现在又出现一个新的问题了，我们在之前的例子中生成的编码是用字符串保存的，如何将其转换为二进制位就成了一个新的问题，因为java中最小的单位是byte，怎样把一个byte分解为单二进制位就是一个瓶颈了。当然，方法很多如下就是一个方法，由于java没有保存bit的单位，我们暂且用byte数组表示!--
　　Code highlighting produced byActiproCodeHighlighter(freeware)
　　-->/**
　　*将String编码转换为二进制位，用byte[]表示
　　*code: String 编码
　　*return:用byte[]表示的二进制位代码
　　public byte[] getBit(String code){
　　byte[] bi = newbyte[code.length];
　　for(inti=0;i<code.i++){//取出String中的每个字符
　　char ch =code.charAt(i);
　　bi[i]=0;
　　bi[i]=1;
　　然而这还不够，因为哈夫曼树组生成的编码是不等长的，而一个byte必须是8个bit组成，所以需要拼接，将不足8位的用下一个byte的编码补充完整并截断，如若a的编码是01101，b的编码是0011，那么ab组成的byte就应该是.......，后面的则由下一位补齐。将二进制位转成二进制不算太难，如二进制位运算、二进制四则运算都可以完成。
　　举个例子，我们假设byte[]changeByte(byteoBt)方法就是将原byte转换为用byte[]表示的二进制位，注意：此方法不完善!!--
　　Code highlighting produced byActiproCodeHighlighter(freeware)
　　-->/**
　　*将二进制位转换为byte方法
　　*oBytes组成源文件的byte[]
　　*return:转换后的Byte队列
　　public byte[] compressor(byte[]oBytes){
　　byte[]bits=newbyte[8];//储存8位二进制位
　　ListbL=newArrayList();//转换后长度未知，先用list储存
　　intbitsLeft=8;//储存当前bits中剩余位数
　　for(byte b:oBytes){
　　byte[]nBits=changeByte(b);//转码，得到二进制位
　　for(byteoneBit:nBits){
　　bits[8-bitsLeft]=oneB//将新二进制位加入到当前byte的二进制位中
　　bitsLeft--;//当前byte剩余位数-1
　　bytenByte = changeToByte();
　　bL.add(nByte);
　　bitsLeft=8;
　　}catch(Exceptionef){}
　　*将8位二进制位转换为byte方法，此处用的是位运算
　　*bits:储存8个二进制位的byte[]
　　* return :转换成的byte
　　*throws:bits不是8个二进制位格式：不是8位或不止0和1
　　public byte changeToByte throwsException(byte[] bits){
　　thrownewException(不是8位！);
　　byte b=0;
　　for(int i = 0;i<8;i++){
　　thrownewException(值不是0或1)
　　b=(byte)(b<<1);//左移1位
　　b+=bits[i];
　　相信有些人又发现问题了，最后一个byte编完的时候很可能出现没有补满的情况，那么最后一位怎么填满就成了第二个比较重要的问题了，弄不好就会出现解压时候多了个byte的情况，当然解决的方法也有很多，可以在最前面添加一个参数表示最后一位的空位数然后填满，也可以填入一个编码表中不存在的编码，我采用的是后者，可以节省1个byte的说明。
　　这样下来，一个文件算是压缩完了，然而不能只压缩不解压，要解压的话，我们需要把编码表存入文件。由于文件长度未知，一般可以保存在文件头部。当然，编码表和正文部分需要用标记来区分开的，我自己是计算出编码表长度在开头用个int值注明，然后读取int个字节作为编码表，后面的就是正文了。当然还有别的方法，就看各位看官自己探索了~
　　下面就是解压了，由于哈夫曼树生成的编码长度的不同，压缩过程中我们需要把8个bit转换为一个byte，c过程就会需要把一个byte拆分为8个bit，方法同样有很多，我这里提供一种方法：!--
　　Code highlighting produced byActiproCodeHighlighter(freeware)
　　-->/**
　　*将一个byte的bit拆分方法
　　* b:需要拆分的byte
　　*return:一个长度为8的byte[]，每个元素储存一位bit
　　public byte[] getBits(byte b){
　　byte[]bits=newbyte[8];//定义用于储存bit的byte[]
　　for(int i=0;i<8;i++){
　　byte t=(byte)(b<<i);//左移i位
　　t=(byte)(t>>7)//再右移7位，这样最低位就是从高位开始第一位了
　　t=(byte)(Math.abs(t));//避免负数的影响，主要是当该位为1时
　　bits[i] =t;//赋值
　　特别注意的是，将bit[]合并为byte和将byte拆分为bit[]的过程千万不要将byte的高低位弄颠倒!我就犯过这个错误。。找了半天才找到问题。有了这个方法，我们就可以做出解压动作了，将文件中每个byte依次读出(前面的编码表不要再读进来了)，将byte拆分为bit[]，然后一位一位的对照，就是先取bit[]第一位，查看编码表，没有再取前2位对照，如此反复，找到对应的就储存下来，一个byte读完了读下一个，一直到结束，这个文件就被解压完成了。
　　后面的扩展就靠各位看官了，比如如何提高压缩/解压效率、压缩多个文件如何实现等，另外，如果修改下这个算法，各byte加权不是由出现次数来定而是事先约定，压缩的时候不将编码表存入文件，那么我们做出来的就是一个加密程序
[] [] [] []求C语言C++高手赐教额~~~关于哈夫曼树的程序~~&.& 急求~~一定要可以运行的噢。。~_百度知道
求C语言C++高手赐教额~~~关于哈夫曼树的程序~~&.& 急求~~一定要可以运行的噢。。~
哈夫曼树应用功能： (1)从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；(2)利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。(3)利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。分步实施： 1） 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2） 完成最低要求：完成功能1；3） 进一步要求：完成功能2和3。有兴趣的同学可以自己扩充系统功能。
提问者采纳
/*说实话，哈夫曼树的编码有点难度，这个代码是我花了三四个小时写的，不能完全满足你的要求，但是可以进行哈夫曼编码，你试着向你题目的要求改一下吧。*/#include&iostream.h&#include&iomanip.h&#define N 5#define M 2*N-1typedef struct HF_Node{
}HTNODE;typedef struct Node {
Node * Node *}*BTtypedef HTNODE HuffmanT[M];bool Is_Empty(BTree root){ if(root)
}void Visit(BTree root)
//访问二叉树的结点{ cout&&root-&x&&&
&;}void Print(HuffmanT T)
//以数组的形式输出哈夫曼树{ for(int i=0;i&M;++i) {
cout&&setw(4)&&T[i].weight&&setw(4)&&T[i].parent&&setw(4)&&T[i].lchild&&setw(4)&&T[i].rchild&& }}void InitHT(HuffmanT T){ for(int i=0;i&M;++i) {
T[i].lchild=T[i].rchild=T[i].parent=-1;
T[i].weight=0; } T[0].weight=0.12,T[1].weight=0.40,T[2].weight=0.15,T[3].weight=0.08,T[4].weight=0.25;
//书上例题，已经初始化好，}void SelectMin(HuffmanT T,int n,int &p,int &q){ int i,j; for(i=0;i&=n;++i) {
if(T[i].parent==-1)
} } for(j=i+1;j&=n;++j) {
if(T[j].parent==-1)
} } for(i=0;i&=n;++i) {
if((T[p].weight&T[i].weight)&&(T[i].parent==-1)&&(q!=i))
p=i; } for(j=0;j&=n;++j) {
if((T[q].weight&T[j].weight)&&(T[j].parent==-1)&&(p!=j))
q=j; }}void Create_HT(HuffmanT T)
//创建哈夫曼树{ int i,p,q; InitHT(T); for(i=N;i&M;++i) {
SelectMin(T,i-1,p,q);
T[p].parent=T[q].parent=i;
T[i].lchild=p;
T[i].rchild=q;
T[i].weight=T[p].weight+T[q]. }}void Create_BTree(BTree &root)
//以先序递归建立二叉树{
root=0; cout&&&请输入数据，以-1结束：&&& cin&&x; if(x==-1)
root = new N root-&x=x; root-&lchild=0; root-&rchild=0; Create_BTree(root-&lchild); Create_BTree(root-&rchild);}void InOrder(BTree root)
//以中序遍历二叉树{ if(!Is_Empty(root)) {
InOrder(root-&lchild);
Visit(root);
InOrder(root-&rchild); }}void PostOrder(BTree root){ if(!Is_Empty(root)) {
PostOrder(root-&lchild);
PostOrder(root-&rchild);
Visit(root); }}void Distroy_BTree(BTree &root)
//以后序遍历删除二叉树{ if(!Is_Empty(root)) {
Distroy_BTree(root-&lchild);
Distroy_BTree(root-&rchild);
//为了防止指针出现错误，最好加上}void HF_PreOrder(HuffmanT T,int i)
//哈夫曼树的所有内节点都有两个孩子，都经过扩充,先序遍历{ if(T[i].lchild==-1||T[i].rchild==-1) {
cout&&T[i].weight&&
} cout&&T[i].weight&& i=T[i]. HF_PreOrder(T,i); i=T[i].
//访问完左子树之后通过其双亲结点访问其右兄弟，必须通过双亲结点才能找到右兄弟 i=T[i].
//因为i=T[i].lchild使i的值不断变化，且回溯后不能变为递归之前的状态 HF_PreOrder(T,i);}void HF_InOrder(HuffmanT T,int i)
//中序遍历{ if(T[i].lchild==-1||T[i].rchild==-1) {
cout&&T[i].weight&&
} i=T[i]. HF_InOrder(T,i); i=T[i].
//必须在此处找到双亲结点 cout&&T[i].weight&& //访问双亲结点 i=T[i].
//因为i已经为双亲结点，所以不必找双亲结点了 HF_InOrder(T,i);}void HF_PostOrder(HuffmanT T,int i)
//后序遍历{
if(T[i].lchild==-1||T[i].rchild==-1) {
cout&&T[i].weight&&
} i=T[i]. HF_PostOrder(T,i); i=T[i].
//必须在此处找到双亲结点
//通过双亲结点找到右兄弟 HF_PostOrder(T,i);
//左右结点都访问结束后访问双亲结点，再找双亲结点 cout&&T[i].weight&& //访问双亲结点}void HuffmanCode(HuffmanT T)
//构造哈弗曼编码{
//找双亲结点 int i=0,j=0; for(i=0;i&N;++i) {
cout&&setw(4)&&T[i].weight&&&: &;
while(p!=-1)
if(T[p].lchild==j)
//如果为双亲结点的左孩子，则输出0
cout&&&0&;
if(T[p].rchild==j)
//如果为双亲结点的右孩子，则输出1
cout&&&1&;
//保存当前结点
//找到当前结点的双亲结点
cout&& }}void main(){ HuffmanT T; Create_HT(T); Print(T); cout&&&先序遍历：&&& HF_PreOrder(T,M-1); cout&& cout&&&中序遍历：&&& HF_InOrder(T,M-1); cout&& cout&&&后序遍历：&&& HF_PostOrder(T,M-1);
cout&& cout&&&哈夫曼编码：&&& HuffmanCode(T);BTree BT; Create_BTree(BT); InOrder(BT); cout&& Distroy_BTree(BT);}
提问者评价
呼~~好吧~虽然已经不用了呢~~不过还是要谢谢你噢。分给你啦。
其他类似问题
哈夫曼树的相关知识
其他3条回答
高手赐教额~~~关于哈夫曼树的程序~~
我已经发给你了哦·~~
我已经发给你了哦·~~
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁分类：&&180人阅读&&&
1、基本概念
a、路径和路径长度
若在一棵树中存在着一个结点序列 k1，k2，……，kj， 使得&ki是ki&#43;1&的双亲（1&=i&j），则称此结点序列是从 k1 到 kj 的路径。
从 k1 到 kj 所经过的分支数称为这两点之间的路径长度，它等于路径上的结点数减1.
b、结点的权和带权路径长度
在许多应用中，常常将树中的结点赋予一个有着某种意义的实数，我们称此实数为该结点的权，(如下面一个树中的蓝色数字表示结点的权)
结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘积。
c、树的带权路径长度
树的带权路径长度定义为树中所有叶子结点的带权路径长度之和，公式为：
其中，n表示叶子结点的数目，wi 和 li 分别表示叶子结点 ki 的权&#20540;和树根结点到 ki 之间的路径长度。
如下图中树的带权路径长度 WPL = 9 x 2 &#43; 12 x 2 &#43; 15 x 2 &#43; 6 x 3 &#43; 3 x 4 &#43; 5 x 4& =& 122
d、哈夫曼树
哈夫曼树又称最优二叉树。它是 n 个带权叶子结点构成的所有二叉树中，带权路径长度 WPL 最小的二叉树。
如下图为一哈夫曼树示意图。
2、构造哈夫曼树
假设有n个权&#20540;，则构造出的哈夫曼树有n个叶子结点。 n个权&#20540;分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权&#20540;最小的树合并，作为一棵新树的左、右子树，且新树的根结点权&#20540;为其左、右子树根结点权&#20540;之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
&如：对 下图中的六个带权叶子结点来构造一棵哈夫曼树，步骤如下：
注意：为了使得到的哈夫曼树的结构尽量唯一，通常规定生成的哈夫曼树中每个结点的左子树根结点的权小于等于右子树根结点的权。
具体算法如下：
3、哈夫曼编码
在电报通信中，电文是以二进制的0、1序列传送的，每个字符对应一个二进制编码，为了缩短电文的总长度，采用不等长编码方式，构造哈夫曼树，
将每个字符的出现频率作为字符结点的权&#20540;赋予叶子结点，每个分支结点的左右分支分别用0和1编码，从树根结点到每个叶子结点的路径上
所经分支的0、1编码序列等于该叶子结点的二进制编码。如上文所示的哈夫曼编码如下：
a 的编码为：00
b 的编码为：01
c 的编码为：100
d 的编码为：1010
e 的编码为：1011
f 的编码为：11
4、哈夫曼树的操作运算
以上文的哈夫曼树作为具体实例，用详细的程序展示哈夫曼树的操作运算
运行结果：
上一篇：下一篇：
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：966次
排名：千里之外