数据结构和算法|哈夫曼树及其编码数据结构和算法|哈夫曼树

1、定义

树的带权路径长度（WPL）

将树的每一个节点附加一个权值，树中所有叶子节点的带权路径长度之和成为该树的带权路径长度。其计算公式如下：

文章图片

哈夫曼树

带权路径长度WPL最小的二叉树成为哈夫曼树（或最优二叉树）。

哈夫曼编码

规定哈夫曼树种左分支为0，右分支为1，则从根节点到每个叶子节点所经过的分支对应的0和1组成的序列便为该节点对应字符的编码，这样的编码成为哈夫曼编码。
详细定义可查看博客：https://blog.csdn.net/l494926429/article/details/52494926
2、应用
哈夫曼树主要用于哈夫曼编码，可以起到压缩作用。
3、实现
（1）哈夫曼树的类型定义

typedef struct HTNode { char data; double weight; int parent, left, right; }HTNode;

（2）哈夫曼树的构造算法

//returns the huffman tree HTNode* CreateHTNode(char* src, double* weight, int n) { int h_n = 2 * n - 1; //init the huffman tree HTNode* h = new HTNode[h_n]; for (int i = 0; i < n; i++) { h[i].data = https://www.it610.com/article/src[i]; h[i].weight = weight[i]; h[i].parent = h[i].left = h[i].right = -1; } for (int i = n; i < h_n; i++) h[i].parent = -1; //create the huffman tree int min1_index, min2_index; //the index of the least two weight for(int i = n ; i < h_n; i++) { min1_index = min2_index = -1; for (int j = 0; j < i; j++) { if (h[j].parent == -1) { if (min1_index == -1 || h[j].weight < h[min1_index].weight) { min2_index = min1_index; min1_index = j; } else if (min2_index == -1 || h[j].weight < h[min2_index].weight) { min2_index = j; } } } h[i].weight = h[min1_index].weight + h[min2_index].weight; h[i].left = min1_index; h[i].right = min2_index; h[min1_index].parent = h[min2_index].parent = i; } return h; }

（3）哈夫曼编码

//returns the huffman code of the huffman tree map* CreateHCode(HTNode* h, int n) { map* m = new map; for (int i = 0; i < n; i++) { string t = ""; int k = i; while (h[k].parent != -1) { if (h[h[k].parent].left == k) t += '0'; else t += '1'; k = h[k].parent; } reverse(t.begin(), t.end()); (*m)[h[i].data] = t; } return m; }

4、测试
【数据结构和算法|哈夫曼树及其编码】假设用于通信的电文仅由 8 个字母组成,字母在电文中出现的频率分别为 0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这 8 个字母设计哈夫曼编码。

#include #include #include using namespace std; typedef struct HTNode { char data; double weight; int parent, left, right; }HTNode; //returns the huffman tree HTNode* CreateHTNode(char* src, double* weight, int n) { int h_n = 2 * n - 1; //init the huffman tree HTNode* h = new HTNode[h_n]; for (int i = 0; i < n; i++) { h[i].data = https://www.it610.com/article/src[i]; h[i].weight = weight[i]; h[i].parent = h[i].left = h[i].right = -1; } for (int i = n; i < h_n; i++) h[i].parent = -1; //create the huffman tree int min1_index, min2_index; //the index of the least two weight for(int i = n ; i < h_n; i++) { min1_index = min2_index = -1; for (int j = 0; j < i; j++) { if (h[j].parent == -1) { if (min1_index == -1 || h[j].weight < h[min1_index].weight) { min2_index = min1_index; min1_index = j; } else if (min2_index == -1 || h[j].weight < h[min2_index].weight) { min2_index = j; } } } h[i].weight = h[min1_index].weight + h[min2_index].weight; h[i].left = min1_index; h[i].right = min2_index; h[min1_index].parent = h[min2_index].parent = i; } return h; }//returns the huffman code of the huffman tree map* CreateHCode(HTNode* h, int n) { map* m = new map; for (int i = 0; i < n; i++) { string t = ""; int k = i; while (h[k].parent != -1) { if (h[h[k].parent].left == k) t += '0'; else t += '1'; k = h[k].parent; } reverse(t.begin(), t.end()); (*m)[h[i].data] = t; } return m; }int main() { const char data[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h' }; const double weight[] = {0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10}; const int n = 8; HTNode* h = CreateHTNode(const_cast(data), const_cast(weight), n); map* m = CreateHCode(h, n); for (map::iterator iter = m->begin(); iter != m->end(); iter++) { cout << iter->first << " : " << iter->second << endl; } delete []h, m; system("pause"); return 0; }