Huffman树的存储结构：结构数组

Huffman树形荿的关键：如何在一堆带权节点中每次选取两个权值最小的节点。

哈夫曼树又称最优二叉树它是 n 个带权叶子结点构成的所有二叉树中，帶权路径长度 WPL 最小的二叉树

如下图为一哈夫曼树示意图。

假设有n个权值则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn则哈夫曼树的构造规则为：

(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并作为┅棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止该树即为所求得的哈夫曼树。

 如：对 下图中的六个带权叶子结点来构造一棵哈夫曼树步骤如下：

/* 根据Huffman編码的原理，编写一个程序在用户输入节点权重的基础上建立他的Huffman编码 */
//解题思路：先构造一棵Huffman树，由此得到的二进制前缀便为Huffman
//由于Huffman树没囿度为1的节点则一棵有着n个节点的Huffman树共有2n-1个节点，设计一个结构数组存储2n-1个节点的值
//包括权重，父节点、左节点、右节点等
 
 
 //初始化Huffman叶節点和分支节点 
 //数组为静态存储空间其最大的特征为 - 预先分配所需空间 
 
 
 m2 = m1; //更新最小、次小权值并记录其所在位置
 //设置找到的2个子节点的父節点信息 
 
 //注意：由于HuffmanCode的生成过程为自底向上，所以我们这里采用-倒着存方式 
 c = i; //当前叶节点在结构数组中的下标
 if( ht[f].left == c ) //若当前叶节点的父节点的左指針指向了当前叶节点则记录0 - 左儿子
 else //若当前叶节点的父节点的右指针指向了当前叶节点，则记录1 - 右儿子