当前位置：首页 > news >正文

哈夫曼树译码函数（Decoding）该函数通过哈夫曼编码串和已构建的哈夫曼树，还原出原始字符序列

news 2026/5/12 18:08:33

一、哈夫曼树译码函数（Decoding）
该函数通过哈夫曼编码串和已构建的哈夫曼树，还原出原始字符序列。其核心逻辑如下：

初始状态：从哈夫曼树的根节点开始（在数组表示中，根节点下标通常为2*n - 1，其中n是叶子节点数量）。
遍历编码串：
- 对于编码串中的每一位：
  - 若为'0'，则跳转到当前节点的左孩子；
  - 若为'1'，则跳转到当前节点的右孩子。
判断是否到达叶子节点：
- 当前节点的左右孩子均为 0（或为空），说明是叶子节点；
- 此时输出该节点所代表的字符；
- 然后重新回到根节点，继续后续译码。
终止条件：编码串全部位处理完毕，译码结束。

示例代码（C语言风格结构体与数组实现）：

#include<stdio.h>#include<string.h>#defineMAX_NODE100typedefstruct{charch;// 存储字符intweight;// 权重intparent,lchild,rchild;// 双亲、左孩子、右孩子下标}HTNode;voidHuffmanDecode(HTNode ht[],introot,char*code,intn){inti=0;intcurrent=root;intlen=strlen(code);while(i<len){if(code[i]=='0'){current=ht[current].lchild;// 走左子树}elseif(code[i]=='1'){current=ht[current].rchild;// 走右子树}// 判断是否为叶子节点（左右孩子都为0）if(ht[current].lchild==0&&ht[current].rchild==0){printf("%c",ht[current].ch);// 输出对应字符current=root;// 回到根节点}i++;}printf("\n");}

二、树的存储结构

双亲表示法：
- 使用结构数组存储每个节点，每个节点包含数据、权重、双亲下标、左右孩子下标等信息。
- 优点：便于向上查找祖先节点，适合构造哈夫曼树；
- 缺点：查找孩子节点效率低，需遍历整个数组。
孩子表示法：
- 每个节点保存一个链表或动态数组，记录所有孩子节点的下标或指针；
- 适用于多叉树，如文件系统目录结构；
- 查找孩子高效，但空间开销较大。
孩子兄弟表示法（左孩子-右兄弟表示法）：
- 每个节点包含两个指针：“第一个孩子” 和 “右兄弟”；
- 可将任意树转化为二叉树形式进行存储和操作；
- 特别适合递归遍历和森林转换为二叉树的应用场景。

这些存储方式广泛应用于数据压缩（如哈夫曼编码）、操作系统目录管理、编译器语法树构建等领域。
构建哈夫曼树并生成编码表是数据压缩中的核心步骤，主要包括两个阶段：建树和编码生成。以下是详细过程与实现方法。

一、构建哈夫曼树（Huffman Tree）

基本思想：

采用贪心算法，每次从所有节点中选取权值最小的两个节点，合并成一个新的内部节点，其权值为两者之和，直到只剩一棵树。

步骤：

给定 n 个字符及其出现频率（或权重），每个字符作为叶子节点。
构造一个优先队列（最小堆），按权值排序。
重复以下操作 (n-1) 次：
- 取出权值最小的两个节点 A 和 B；
- 创建新节点 C，C 的权值 = A.权值 + B.权值；
- 将 A 设为 C 的左孩子，B 为右孩子（或反之）；
- 将 C 插入优先队列。
最后剩下的节点即为哈夫曼树的根。

存储结构（双亲表示法数组）：

使用结构体数组HTNode ht[2*n]，索引从 1 开始：

typedefstruct{charch;// 字符intweight;// 权重intparent;// 双亲下标intlchild;// 左孩子下标intrchild;// 右孩子下标}HTNode;

初始化时，前 n 个节点为叶子节点（字符+权重），parent 初始为 0；后续 n-1 个节点用于存储合并后的非叶节点。

示例代码（C语言风格）：

voidCreateHuffmanTree(HTNode ht[],intn){intm=2*n-1;for(inti=1;i<=m;i++){ht[i].parent=ht[i].lchild=ht[i].rchild=0;}for(intk=n+1;k<=m;k++){intmin1=9999,min2=9999;intx1=0,x2=0;// 找两个无父节点且权值最小的节点for(intj=1;j<k;j++){if(ht[j].parent==0&&ht[j].weight<min1){min2=min1;x2=x1;min1=ht[j].weight;x1=j;}elseif(ht[j].parent==0&&ht[j].weight<min2){min2=ht[j].weight;x2=j;}}// 合并两个节点ht[k].weight=min1+min2;ht[k].lchild=x1;ht[k].rchild=x2;ht[x1].parent=k;ht[x2].parent=k;}}

二、生成哈夫曼编码表

原理：

从每个叶子节点出发，逆向回溯到根节点，路径上每一步：

走左分支记为'0'；
走右分支记为'1'；
由于是从下往上生成，需将结果反转得到正确编码。

方法：逐个叶子节点遍历

#include<string.h>voidGenerateHuffmanCode(HTNode ht[],charhcode[][20],intn){chartemp[20];inttop=0;for(inti=1;i<=n;i++){intcurrent=i;intparent=ht[i].parent;top=0;// 从叶子向上遍历至根while(parent!=0){if(ht[parent].lchild==current)temp[top++]='0';elsetemp[top++]='1';current=parent;parent=ht[parent].parent;}// 反转字符串并存入编码表temp[top]='\0';for(intj=0;j<top;j++){hcode[i][j]=temp[top-1-j];}hcode[i][top]='\0';}}