Huffman树的创建

思想概述

为求得最优二叉树，哈夫曼巧妙地涉及到哈夫曼算法。通过哈夫曼算法可以建立一棵哈夫曼树。现有n个结点，如果岸边每个结点都作为一棵二叉树的根结点，那么这个n个根结点就组成了一个森林。把结点在文件中出现的次数定义为该结点的权值。

1.在森林中取权值最小的两个根结点，合并成一棵二叉树，并生成一个新结点T，作为这两个结点的父亲，T的权值是它的两个子结点的权值之和。与此同时，森林中减少了一棵树。

2.对新森林重复上述操作，直至森林中只有唯一的根结点，最后的根结点便是所求的哈夫曼树的根。

注意：最优二叉树未必唯一，而哈夫曼树可能只是满足条件的所有最优二叉树中的一棵。

Huffman结点

假定哈夫曼树中每个结点的结构为：

LLINK/左链接

INFO/信息域

Weight/权值

RLINK/右链接

/*Huffman结点结构体*/
typedef struct HuffmanNode {char INFO;  //信息域int Weight;  //权重HuffmanNode* LLINK;  //左链接HuffmanNode* RLINK;  //右链接
}HuffmanNode;

Huffman树

假定与给定的m个权值结合的结点的地址存在于一维数组H[1:m+1]中，并且该数组按每个结点的Weight域已排序（从小到大）。

如Huffman树结点声明所示，其中H为存储Huffman结点的一维数组（Huffman结点内存储了结点权值Weight），且数组H已排序。

/*Huffman树结构体*/
typedef struct HuffmanTree {HuffmanNode** H;  //存储Huffman结点的数组int m;  //结点个数
}HuffmanTree;

构建Huffman树 

1.初始化

创建所有结点，把每个结点都作为一棵二叉树的根结点，所有结点组成一个森林 。

2.组合

在森林中选取两个最小的结点，合并成一棵二叉树，并并生成一个新结点T，作为这两个结点的父亲，T的权值是它的两个子结点的权值之和。

3.找位置

找到H数组中合适的位置插入新生成的二叉树，使数组保持递增。

4.循环

循环操作所有结点。

HuffmanTree* CreateHuffmanTree(char data[],int weight[],int n) {//初始化HuffmanTree* tree = new HuffmanTree;tree->m = n;//每个结点都作为一棵树的根结点，组成森林for (int i = 1; i <= tree->m; i++) {tree->H[i] = new HuffmanNode;tree->H[i]->INFO = data[i];tree->H[i]->Weight = weight[i];tree->H[i]->LLINK = NULL;tree->H[i]->RLINK = NULL;}//组合过程HuffmanNode* p1, * p2,* p,* t;int i, j;for (i = 1; i < tree->m; i++) {t = new HuffmanNode;p1 = tree->H[i];p2 = tree->H[i + 1];t->LLINK = p1;t->RLINK = p2;  //链接左右结点t->Weight = p1->Weight + p2->Weight;  //权重等于子结点权重之和p = t;j = i + 2;  //从下一棵结点开始比较if (j <= tree->m && p->Weight >= tree->H[j]->Weight) {  //寻找合适的位置，使森林保持递增tree->H[j - 1] = tree->H[j];  //小的结点前移，给p结点腾位置j++;}tree->H[j - 1] = p;}return tree;
}

Huffman编码 

对于所有的编码，哈夫曼编码是文件的总编码长度最短，字符集中的字符所在的结点均是哈夫曼树中的外结点。

将哈夫曼树每个分支结点的左分支标上0，右分支标上1，把从根结点到每个叶结点的路径上的标号连接起来，作为该叶结点所代表的字符的编码。

/*Huffman编码*/
#include <unordered_map>
#include <cstring>
//使用unordered_map,char标志字符，string对应的Huffman编码
typedef unordered_map<char, string> UMCS;
UMCS HuffmanCode;  //Huffman编码
void CreateHuffmanCode(HuffmanNode* t,string code) {if (t == NULL) return;//左右子结点为空，则为叶结点，为字符if (t->LLINK == NULL && t->RLINK == NULL) {HuffmanCode[t->INFO] = code;}//递归处理左右结点，进行Huffman编码CreateHuffmanCode(t->LLINK, code + "0");  //左结点，+"0"CreateHuffmanCode(t->RLINK, code + "1");  //右结点，+"1"
}

Huffman译码

对压缩后的数据文件进行解码的过程是，依次读入文件的二进制码，从哈夫曼树的根结点出发，若当前读入0，则走向其左儿子，否则走向其右儿子，到达某一叶结点时，便可以译出相应的字符。

/*Huffman译码*/
void TransHuffmanCode(HuffmanNode* root) {HuffmanNode* t=root;string ans="";  //存储最终译码结果string code;  cin >> code;  //读入二进制Huffman编码int n = code.size();  //二进制编码的长度for (int i = 0; i < n; i++) {char ch = code[i];  if (ch == '0') t = t->LLINK;  //读入'0'，则走左分支if (ch == '1') t = t->RLINK;  //读入'1'，则走右分支//若走到叶结点，当前阶段译码成功，可存入一个字符if (t->LLINK == NULL && t->RLINK == NULL) {  ans = ans + t->INFO;  //串入译码结果if (i != n - 1) t = root;  //若此时还剩二进制编码未译，回到根结点，继续译码}}//若二进制编码读入完全，此时却没有走到叶结点，证明译码不完全，译码错误if (!(t->LLINK == NULL && t->RLINK == NULL))cout << "INVALID" << endl;  //译码错误，输出"INVALID"elsecout << ans<<endl;  //译码成功，输出最终译码结果
}

---

《数据结构》刘大友||第5章 树与二叉树||5.4压缩与哈夫曼树