什么是哈夫曼树 哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1L1+W2L2+W3L3+…+ WnLn)，N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,…n)。可以证明哈夫曼树的WPL是最小的。 构造哈夫曼树的算法如下： 1）对给定的n个权值{W1,W2,W3,…,Wi,…,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,…,Ti,…, Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。 2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 4）重复2）和3），直到集合F中只有一棵二叉树为止。 例如，对于4个权值为1、3、5、7的节点构造一棵哈夫曼树，其构造过程如下图所示： 哈夫曼树的算法实现 #include<iostream>#include<iomanip>#include<cfloat>using namespace std; const int n=5; const int m=2*n-1; typedef struct{ float weight; int parent,lchild,rchild; }nodetype; typedef nodetype hftree[m]; hftree T; void huffman(hftree T){ int p1,p2,i,j; float small1,small2; for(i=0;i<n;i++){ T[i].parent=T[i].lchild=T[i].rchild=-1; } for(i=0;i<n;i++){ cin>>T[i].weight; } for(i=n;i<m;i++){ p1=p2=-1; small1=small2=FLT_MAX; for(j=0;j<=i-1;j++){ if(T[j].parent!=-1)continue; if(T[j].weight<small1){ small2=small1; small1=T[j].weight; p2=p1; p1=j; } else if(T[j].weight<small2){ small2=T[j].weight; p2=j; } } T[p1].parent=T[p2].parent=i; T[i].parent=-1; T[i].lchild=p1; T[i].rchild=p2; T[i].weight=small1+small2; } } 输出哈夫曼树 这里用到了头文件，主要是运用setw()控制一下输出的格式……

阅读全文