- 定义:按照字符的频率(频数)构建最优树,即把频率小的树尽可能放在深层节点,频率大的树放在浅层节点,从而使得所有叶子节点的带权路径和最小。这样做的好处是依照路径重新对叶子节点的字符进行01编码,从而使高频率的字符编码短,低频率字符的编码长,这种不定长的编码可以使得最终文本长度减小,实现数据压缩;
-
// 树节点数据结构 typedef struct tnode{char c;int weight;struct tnode *left, *right; //此时为链表// unsigned int left, right; //也可以为 int,此时为数组 }
- 哈夫曼树的构造:由于哈夫曼树是最优树,即节点的度为 0 或 2,因此具有 n 个叶子节点的树的总结点个数为 2n-1 个,对于具有 n 个字符的数据进行建树:
- 开辟长度为 2n+1 的数组空间arr, 1~n为叶子节点,n+1~2n 是非叶子节点,0 空间不使用;
-
int m = n*2 - 1 for(int i = n+1; i <= m; i++){select(arr, i-1, left, right); // 从 [1,i]间选择最小的两个子节点//令 left, right 分别为 i 的子节点//令 i 为 left, right 的父节点,权值为其和 } // 即可完成树的构建,其中 arr[m]存放的是根节点
- 获取字符的哈夫曼编码
-
// 先序遍历树结构,路径即为结果 char path[MAX_SIZE]; char code[SIZE][MAX_SIZE]; // 存放所有字符的编码 traversalHuffmanTree(&root, path, 0); // 获取编码void traversalHuffmanTree(tnode *root, char* path, int len){if(root == NULL) return ;if(root->left == NULL && root->right == NULL){path[len] = ' '; //叶子节点,结束符strcpy(code[root->c], path]); // 将编码赋值到 root 的字符对应编码位置return ;}// 左子树路径为 0path[len] = '0';traversalHuffmanTree(root->left, path, len+1);// 右子树路径为 1path[len] = 1;traversalHuffmanTree(root->right, path, len+1); } -
文件压缩:依照编码依次对相应字符进行重新编码组成字符串,将每 8 位的字符串转化为 unsigned char 类型压缩存储










