c语言|哈夫曼树和哈夫曼编码 c语言|数据结构

什么是哈夫曼树哈夫曼树，又称最优二叉树，是带权路径长度最短的数，可用来构造最优编码，用于信息传输，数据压缩等方面，是一种应用广泛的二叉树。
首先介绍一些与哈夫曼树相关的基本概念：

路径：书中一个节点到另一个节点之间的分值序列，构成两个节点间的路径。
路径长度：路径上分支的条数称为“路径长度”。
树的路径长度：从树根到每个节点的路径长度之和成为“数的路径长度”。
节点的权：给树中节点赋予一个数值，该数值成为“节点的权”。
带权路径长度：节点到树根间的路径长度与节点的权的乘积，称为该节点的“带权路径长度”。
数的带权路径长度：树中所有叶子节点的带权路径长度之和，称为“树的带权路径长度”，通常记为WPL、

由于哈夫曼树是一颗二叉树，可以用前面介绍的二叉树的存储方法，但哈夫曼树有其自己的特点，因此一般采用如下介绍的静态三叉链表来存储
哈夫曼树的建立算法中，哈夫曼树没有度为1的结点，这类二叉树又称正则二叉树。对于n个叶子的哈夫曼树，算法中构建了n-1个度为2的结点，所以哈夫曼树共有2n-1个节点，可以存储在一个大小为2n-1的一位数组中。

文章图片

哈夫曼树的建立过程见上图：
由于每个节点急需要孩子的信息，又需要双亲的信息，因此每个节点可设计成如下所示的三叉链表节点结构：

Weight	Parent	Lchild	Rchild

其中，Weight为节点的权值，Parent为双亲节点在数组中的下标，Lchild为左孩子节点在数组中的下标，Rchild为右孩子节点在数组中的下标。
其中哈夫曼树的静态三叉链表存储结构，其类型定义如下：

#define N 30 #define M * N - 1 typedef struct { int Weight; int Parent, Lchild, Rchild; } HTNode, HuffmanTree[M +1];

静态三叉链表数组中，前n个元素存储叶子节点，后n-1个元素村塾不断生成的新节点即度为2的分支节点，最后一个元素将是哈夫曼树的根节点。
哈夫曼算法的实现如下可分为初始化和构建哈夫曼树两部分。

初始化所有节点
构造新节点
代码如下：

void CrdtdHuffmanTree (HuffmanTree ht, int w[], int n) { m = 2* n - 1; for (int i = 1; i < n; i++) { ht[i].Weight = w[i]; ht[i].Parent = 0; ht[i].Lchild = 0; ht[i].Rchild = 0; } for (int i = n + 1; i <= m; i++) { ht[i].Weight = 0; ht[i].Parent = 0; ht[i].Lchild = 0; ht[i].Rchild = 0; } for (int i = n +1; i <= m; i++) { //在ht的前i-1项中选双亲为0且权值最小的两节点s1, s2 select(ht, i - 1, &s1, &s2); ht[i].Weight = ht[s1].Weight + ht[s2].Weight; //创建新节点，赋权值 //赋新节点左右孩子指针 ht[i].Lchild = s1; ht[i].Rchild = s2; //改s1, s2的双亲指针 ht[s1].Parent = i; ht[s2].Parent = i; } }

哈夫曼编码是最优二进制前缀编码，其算法实现如下：

构造哈夫曼树
在哈夫曼树上求各叶子节点的编码

文章图片

例如，上图哈夫曼树中E的哈夫曼编码为：01，A的哈夫曼编码为：000， B的哈夫曼编码为：001， C的哈夫曼编码为100， D的哈夫曼编码为：101， F的哈夫曼编码为：11
代码如下：（下方代码是从叶子节点逆向走到根节点的方式获取哈夫曼编码）

void CrtHuffmanCodel (HuffmanTree ht, HuffmanCode hc, int n) { //从叶子到根，逆向求各叶子节点的编码 char *cd; int start; cd = (char *) malloc (n * sizeof(char)); //临时编码数组 cd[n - 1] = '\0'; //从后向前诸位求编码，首先放编码结束符 //从每个叶子开始，求相应的哈夫曼编码 for (int i = 1; i <= n; ++i) { start = n - 1; c = i; p = ht[i].Parent; //c为当前节点，p为其双亲 while (p != 0) { --start; if (ht[p].Lchild == c) cd[start] = '0'; //左分支得‘0’ else cd[start] = '1'; //上溯一层 c = p; p = ht[p].parent; } hc[i] = (char *) malloc ((n - start) * sizeof(char)); //动态申请编码串空间 strcpy(hc[i], &cd[start]); //复制编码 } free(cd); }

【c语言|哈夫曼树和哈夫曼编码】以上代码就可以从哈夫曼树中获取到哈夫曼编码了。