怎样构造哈夫曼树及其带权路径的求法

{1}根据给入的N个权值{w1,w2wn}构成N颗二叉树的集合F={T1，T2TN}，其中每颗二叉树TI中只有一个带权WI的根节点，其左右子树为空。
(2)在F中选取两颗根节点的权值最小的树作为左右子树构造一颗新的二叉树，且置新的二叉树的根节点的权值为左右子树上根节点的权值之和。
（3)在F中删除这两颗树，同时将新得到的二叉树加入F中。
（4）重复（2）（3），直到F只含一棵树为止。这棵树就是哈弗曼树。
如果有N个叶子节点，则哈弗曼树有M=2N-1个节点。
核心代码
for(i=n+1;i<=m;++i)
{
Choose(i-1,s1,s2);//求出两个有最小权值的节点
HT[s1]parent=i;HT[s2]parent=i;
HT[i]lchild=s2;HT[i]rchild=s1;
HT[i]weight=HT[s1]weight+HT[s2]weight;
}

/
我也贴个现成的，这个是以前上课用的示范代码，有注释
另外，像<malloch>、<conioh>这种非标准头文件最好不要用
/
/ huffman树的构造方法/
#include<stdlibh>
#include<stdioh>
#define MAXINT 2147483647
#define MAXNUM 50 / 数组w中最多容纳的元素个数，注意 m<=MAXNUM /
#define MAXNODE 100 / 哈夫曼树中的最大结点数，注意 2m-1<MAXNODE /
struct HtNode { / 哈夫曼树结点的结构 /
int ww;
int parent,llink,rlink;
};
struct HtTree {
int root;/ 哈夫曼树根在数组中的下标/
struct HtNode ht[MAXNODE];
};
typedef struct HtTree PHtTree; / 哈夫曼树类型的指针类型 /
/ 构造具有m个叶结点的哈夫曼树/
PHtTree huffman(int m, int w) {
PHtTree pht;
int i, j, x1, x2, m1, m2;
pht = (PHtTree)malloc(sizeof(struct HtTree)); / 创建空哈夫曼树 /
if (pht == NULL) {
printf("Out of space!! \n");
return pht;
}
for (i = 0; i < 2m-1; i++) {/ 置初态 /
pht->ht[i]llink = -1;
pht->ht[i]rlink = -1;
pht->ht[i]parent = -1;
if (i < m)
pht->ht[i]ww = w[i];
else
pht->ht[i]ww = -1;
}
for ( i = 0; i < m-1; i++) {/ 每循环一次构造一个内部结点 /
m1 = MAXINT;
m2 = MAXINT;/ 相关变量赋初值 /
x1 = -1;
x2 = -1;
for (j = 0; j < m+i; j++) / 找两个最小权的无父结点的结点 /
if (pht->ht[j]ww < m1 && pht->ht[j]parent == -1) {
m2 = m1;
x2 = x1;
m1 = pht->ht[j]ww;
x1 = j;
}
else if (pht->ht[j]ww < m2 && pht->ht[j]parent == -1) {
m2 = pht->ht[j]ww;
x2 = j;
}
pht->ht[x1]parent = m+i; / 构造一个内部结点 /
pht->ht[x2]parent = m+i;
pht->ht[m+i]ww = m1+m2;
pht->ht[m+i]llink = x1;
pht->ht[m+i]rlink = x2;
pht->root = m+i;
}
return pht;
}
int main() {
int m = 0, j = 0, i = 0, parent = 0;
int w;
PHtTree pht;
printf("please input m = ");/输入外部结点个数/
scanf("%d", &m);
if (m < 1) {
printf("m is not reasonable!\n");
return 1;
}
w = (int )malloc(sizeof(int)m);
if (w == NULL) {
printf("overflow!\n");
return 1;
}
printf("please input the %d numbers：\n",m);/输入权值/
for (j = 0; j < m; j++)
scanf("%d", w+j);
pht = huffman(m, w);
for (j = 0; j < m; j++) {
printf("the Reverse code of the %d node is:", j+1);/得到的编码应倒过来/
i = j;
while (pht->ht[i]parent != -1) {
parent = pht->ht[i]parent;
if (pht->ht[parent]llink == i)
printf("0");
else
printf("1");
i = parent;
}
printf("\n");
}
return 0;
}

第一步：排序 2 4 5 9\x0d\第二步：挑出2个最小的 2 4 为叶子构造出\x0d\ 6\x0d\2 4\x0d\第三步：判断 6 不大于 5或9（剩余叶子中最小的2个）=》 同方向生长，得出：\x0d\ 11\x0d\ 6 5\x0d\2 4\x0d\第四步：继续生长\x0d\ 20 \x0d\ 11 9\x0d\ 6 5\x0d\ 2 4\x0d\权值为 23+43+52+91=37\x0d\也可以20+11+6=37\x0d\\x0d\例题：6、13、18、30、7、16\x0d\排序 6 7 13 16 18 30\x0d\ 13\x0d\ 6 7\x0d\ 26 26大于16或18 =》分支生长 \x0d\ 13 13\x0d\ 6 7 \x0d\ 26 34\x0d\ 13 13 16 18\x0d\ 6 7\x0d\此时最小的2个数为 26 30 得出\x0d\ 56 34\x0d\ 26 30 16 18\x0d\ 13 13\x0d\6 7\x0d\最后得出 90\x0d\ 56 34\x0d\ 26 30 16 18\x0d\ 13 13\x0d\ 6 7 权值 219\x0d\90+56+26+13+34 or 64+74+133+302+162+182

哈夫曼树不一定是唯一的，选出最小和次小之后哪个放左边都行的，哈弗曼编码唯一只是说得到的码是唯一，但是可以有许多种码，只是它能够唯一地编码和解码。所以，上面两个图应该都是正确的。如果你习惯按照左小右大的规则来构造的话，那只能选择第二幅图了。

给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

编码：
1输入字符串，通过getWeight()获取其权重即每个字符出现的次数并利用权重及字符生成Node结点，组成sourceData列表。
2调用makeHuffman()方法，通过getmin2()函数可获得最小权重的两个字符，再让其形成父亲结点，并赋予左子结点右子结点，遍历sourceData完生成huffman结点，即哈夫曼树的根结点。
3调用traverse()方法，将以huffman为根结点的树遍历形成列表。
4调用strToHuffmanCode()方法，会去调用getCode()方法，会去根据huffman形成路径表route2，再跟原字符串一个一个字符进行比对，找到就添加其路径最终生成huffmancode
5获取二进制表示的哈夫曼编码后，调用huffmanCodeBytes函数可以将二进制树转为带符号的十进制树，以八位二进制数为一组例如11010110,第一位为符号位，1表示负转为十进制数应将其余位取反并加1，再转为十进制数再-1，就可以得到最终的十进制数。
解码：
调用decimalToBinary()函数将带符号的十进制数转为二进制数，再调用byteToBitString()比对route路径表 得到字符

设某信源产生有五种符号u1、u2、u3、u4和u5，对应概率P1=04，P2=01，P3=P4=02，P5=01。

首先，将符号按照概率由大到小排队，如图所示。编码时，从最小概率的两个符号开始，可选其中一个支路为0，另一支路为1。这里，我们选上支路为0，下支路为1。再将已编码的两支路的概率合并，并重新排队。多次重复使用上述方法直至合并概率归一时为止。

从图（a）和（b）可以看出，两者虽平均码长相等，但同一符号可以有不同的码长，即编码方法并不唯一，其原因是两支路概率合并后重新排队时，可能出现几个支路概率相等，造成排队方法不唯一。

一般，若将新合并后的支路排到等概率的最上支路，将有利于缩短码长方差，且编出的码更接近于等长码。这里图（a）的编码比（b）好。

扩展资料

发展历史

哈夫曼编码(Huffman Coding)，又称霍夫曼编码。

1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M Fano给他们的学期报告的题目是，寻找最有效的二进制编码。

由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。

由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。哈夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。

1952年，David A Huffman在麻省理工攻读博士时发表了《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文，它一般就叫做Huffman编码。

参考资料来源：百度百科-哈夫曼编码

---