关于哈夫曼树的基本概念
1.在一棵树中，从一个结点往下可以达到的结点之间的通路，称为路径。
2.某一路径所经过的“边”的数量，称为该路径的路径长度。
3.若将树中结点赋给一个带有某种含义的数值，则该数值称为该结点的权。
4.从根结点到该结点之间的路径长度与该结点的权的乘积，称为该结点的带权路径长度。
5.树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
6.给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，则称该二叉树为哈夫曼树，也被称为最优二叉树。
根据树的带权路径长度的计算规则，我们应该尽可能地让权值大的叶子结点靠近根结点，让权值小的叶子结点远离根结点，这样便能使得这棵二叉树的带权路径长度达到最小。
哈夫曼树的构建过程
给定n个权值分别为w1,w2,…wn的结点，哈夫曼树的构造过程如下：
- 将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。
- 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，新结点的权值为左、右子树上的权值之和。
- 从F中删除刚刚选择的两棵树，同时将新得到的树加入到F中。
- 重复步骤2、3，直到F中只剩下一棵树为止。
哈夫曼树的特点
- 每个初始结点最后都变成了叶结点，且权值越小的叶结点的路径长度越大。
- 构建过程中共构建了
n-1个结点，因此哈夫曼树的总结点数为2n-1. - 每次构造都选择两个结点，因此哈夫曼树不存在度为1的结点。
代码展示
由于普通的C语言实现的代码在大多数地方都能找到，这里就只展示C++改进的代码
#include<iostream> #include<string> #include<string.h> #include<vector> using namespace std; typedef int ElemType; typedef vector<string> HuffmanCode; //哈夫曼编码 vector<int> w; //输入的权值 int n; //结点总数 /*哈夫曼树结点类*/ class HTNode{ public: ElemType weight; //权值 int parent; //父节点 int lChild, rChild; //左右孩子 //构造函数 HTNode(){ weight = parent = lChild = rChild = 0; } HTNode(int weight){ this->weight = weight; parent = lChild = rChild = 0; } //输出运算符重载 friend std::ostream &operator << (std::ostream &output, HTNode &h){ output << h.weight; return output; } }; /*哈夫曼树操作类*/ class Huff{ private: vector<HTNode> T; //内部维护一棵哈夫曼树 int m; //哈夫曼树结点总数 void Select(int n, int &s1, int &s2){ int min; for(int i = 1; i <= n; i++){ //找到第一个还没有双亲的叶子结点 if(T[i].parent == 0){ min = i; break; } } for(int i = min+1; i <= n; i++){//向后迭代找到最小的 if(T[i].parent == 0 && T[i].weight < T[min].weight) min = i; } s1 = min; //第一个最小值给s1 for(int i = 1; i <= n; i++){ //同上，找到第二小的 if(T[i].parent == 0 && i != s1){ min = i; break; } } for(int i = min+1; i <= n; i++){ if(T[i].parent == 0 && T[i].weight < T[min].weight && i != s1) min = i; } s2 = min; //第二个最小值给s2 } public: //构造函数 Huff(){ m = 2*n-1; T.resize(m+1);//初始化数组长度 for(int i = 0; i < m; i++) T[i] = 0; } /*构建哈夫曼树*/ void CreateHuff(){ for(int i = 1; i <= n; i++){ HTNode ht(w[i-1]); T[i] = ht; //赋权值给n个叶子结点 } for(int i = n+1; i <= m; i++){ //每次选择权值最小的结点s1,s2 int s1, s2; Select(i-1, s1, s2); T[i].weight = T[s1].weight+T[s2].weight; T[s1].parent = i; T[s2].parent = i; T[i].lChild = s1; T[i].rChild = s2; // cout << s1 << " " << s2 << "\t" << T[s1].parent << " " << T[s2].parent << endl; // HTNode ht = T[i]; // cout << ht << endl; } } /*生成哈夫曼编码*/ void HuffCoding(HuffmanCode &HC){ string code; for(int i = 1; i <= n; i++){ int c = i; //正在进行的第i个数据的编码 int p = T[c].parent; //找到该数据的父结点 while(p){ //直到父结点为0，即父结点为根结点时，停止 //如果该结点是其父结点的左孩子，则编码为0，否则为1 if(T[p].lChild == c) code = '0'+code; else code = '1'+code; c = p; //继续往上进行编码 p = T[c].parent; //c的父结点 } HC.push_back(code); //将编码插入到数组中 code.clear(); } for(int i = 1; i <= n; i++){ cout << "数据" << T[i].weight << "的编码为:" << HC[i-1] << endl; } } void disp(){ cout << "哈夫曼树为:" << endl; cout << "下标 权值 父结点 左孩子 右孩子" << endl; cout << "0 " << endl; for (int i = 1; i <= m; i++){ cout << i << '\t' << T[i].weight << '\t' << T[i].parent << '\t' << T[i].lChild << '\t' << T[i].rChild << endl; } cout << endl; } }; int main(){ int x; cout << "请输入数据的个数："; cin >> n; cout << "请输入数据："; for(int i = 0; i < n; i++) { cin >> x; w.push_back(x); } Huff h; h.CreateHuff(); h.disp(); HuffmanCode HC; h.HuffCoding(HC); return 0; } /* 测试集 5 23 4 5 51 16 运行效果： 请输入数据的个数：5 请输入数据：23 4 5 51 16 哈夫曼树为: 下标 权值 父结点 左孩子 右孩子 0 1 23 8 0 0 2 4 6 0 0 3 5 6 0 0 4 51 9 0 0 5 16 7 0 0 6 9 7 2 3 7 25 8 6 5 8 48 9 1 7 9 99 0 8 4 数据23的编码为:00 数据4的编码为:0100 数据5的编码为:0101 数据51的编码为:1 数据16的编码为:011 */
