数据结构——HuffmanTree

Huffman tree

基本术语

• 路径和路径长度 - 路径：在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路。 - 结点的路径长度：从一个结点到另一个结点的路径上分支的数目。
• 结点的权及带权路径长度 - 结点的权:将树中结点赋予一个有着某种含义的数值。 - 结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。
• 树的带权路径长度 - 树中所有叶子结点的带权路径长度之和。
• 赫夫曼树（ Huffman tree ） - 带权路径长度达到最小的二叉树即为赫夫曼树。

在所有含 n 个叶子结点、并带相同权值的二叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优二叉树”。

构造 Huffman tree

基本思想：使权大的结点靠近根

• 根据给定的 n 个权值 {w1, w2, …, wn}，构造 n 棵二叉树的集合F = {T1, T2, … , Tn}，其中每棵二叉树中均只含一个带权值 为 wi 的根结点,其左、右子树为空树;
• 在 F 中选取其根结点的权值为最小的两棵二叉树，分别作为左、 右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;
• 从F中删去这两棵树，同时加入 刚生成的新树;
• 重复上述两步，直至 F 中只含一棵树为止。

哈夫曼构造算法实现

一棵有 n 个叶子结点的Huffman树有 2n-1 个结点

• 采用顺序存储结构---一维结构数组
• 结点类型定义 ```cpp typedef struct { ElemType elem; // 结点值 int weight; // 权值 int parent, lch, rch; }HTNode, *HuffmanTree; ```
• 构造HuffmanTree - 输入初始n个叶子结点：置HT1..n的weight值 - 进行以下n-1次合并，依次产生HTi，i=n+1..2n-1： - 在HT1..i-1中选两个未被选过的weight最小的两个结点HTs1和HTs2 - 修改HTs1和HTs2的parent值： parent=i - 置HTi：weight=HTs1.weight + HTs2.weight ,lch=s1, rch=s2```cpp Status CreatHuffmanTree(HuffmanTree HT, int n){ if (n <= 1) // 结点数量不合法 return ERROR; int m = 2 * n - 1; int i; int s1, s2; HT = new HTNode[m + 1]; // 0号单元未用，HT[m]表示根结点 for (i = 1;i <= m;++i) { HT[i].lch = 0; HT[i].rch = 0; HT[i].parent = 0; } for (i = 1;i <= n;++i) // 输入权值 cin >> HT[i].weight; for (i = n + 1;i <= m;++i) { // 构造Huffman树 Select(HT, i - 1, &s1, &s2); // 在HT[k](1≤k≤i-1)中选择两个其双亲域为0, 且权值最小的结点, 并返回它们在HT中的序号s1和s2 if (s1 != 0 && s2 != 0) { HT[s1].parent = i; HT[s2].parent = i; //表示从F中删除s1,s2 HT[i].lch = s1; HT[i].rch = s2; //s1,s2分别作为i的左右孩子 HT[i].weight = HT[s1].weight + HT[s2].weight; //i 的权值为左右孩子权值之和 } } return OK; } ```哈夫曼树的应用哈夫曼编码
• 算法实现 ```cpp Status CreatHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int n) { if (n <= 1) return ERROR; int start, i; int f = 0, c; HC = new char* [n + 1]; char* cd = new char[n]; cd[n - 1] = '0'; for (i = 1; i <= n; ++i) { while (f != 0) { // 从叶子结点开始向上回溯，直到根结点 start = n - 1; c = i; f = HT[i].parent; if (HT[f].lch == c) cd[start] = '0'; else cd[start] = '1'; c = f; f = HT[f].parent; } HC[i] = new char[n - start]; // 编码数组 strcpy(HC[i], &cd[start]); } delete cd; cd = NULL; return OK; } ```
• 重要结论 - 哈夫曼编码是不等长编码 - 哈夫曼编码是前缀编码，即任一字符的编码都不是另一字符编码的前缀 - 哈夫曼编码树中没有度为1的结点。若叶子结点的个数为n，则哈夫曼编码树的结点总数为 2n-1 - 发送过程：根据由哈夫曼树得到的编码表送出字符数据 - 接收过程：按左0、右1的规定，从根结点走到一个叶结点，完成一个字符的译码。反复此过程，直到接收数据结束