一、哈夫曼树介绍
在计算机资料处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现概率的方法得到的，出现概率高的字母使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
例如，在英文中，e的出现概率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文文章进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节，即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。
霍夫曼树又称最优二叉树，是一种带权路径长度最短二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明霍夫曼树的WPL是最小的。（来自维基百科）
二、哈夫曼树及哈夫曼编码构造方法
哈夫曼树的构造方法：
每次选出没被标记过的权重最小的两个结点，标记以后合并成一个新的结点
哈夫曼编码构造方法：
每次按照左右顺序标记01，向左为0，向右为1，将从根节点走到叶子结点的路径上的0和1按顺序组成这个结点的哈夫曼编码
总代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 100
typedef struct {int weight;int parent;int lchild, rchild;
}HTNode, * HuffmanTree;
bool flag[MAXSIZE] = { 0 };
typedef char** HuffmanCode;
void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC, int* w, int n);
void Select(HuffmanTree HT, int& s1, int& s2, int i);
int main()
{int n;int w[MAXSIZE] = { 0 };HuffmanTree HT;HuffmanCode HC;printf("请输入哈夫曼树中叶子结点的个数：");scanf("%d", &n);printf("\n请输入各个叶子结点的权重：");for (int i = 0; i < n; i++)scanf("%d", &w[i]);HuffmanCoding(HT, HC, w, n);printf("哈夫曼树中各节点的信息如下：\n");for (int i = 1; i <= 2 * n - 1; i++)printf("编号：%d \t权重：%d \t双亲：%d \t左孩子：%d \t右孩子：%d \n", i, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);printf("前%d个结点（叶子结点）的编码为：\n", n);for (int i = 1; i <= n; i++)printf("%d %s\n", i, HC[i]);free(HC);free(HT);return 0;
}
void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC, int* w, int n)
{if (n < 1)return;int m = n * 2 - 1;HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));HuffmanTree p;int i;for (p = HT + 1, i = 1; i <= n; i++, w++, p++)*p = { *w,0,0,0 };for (; i <= m; i++, p++)*p = { 0,0,0,0 };for (int i = n + 1; i <= m; i++){int s1, s2;Select(HT, s1, s2, i);HT[s1].parent = HT[s2].parent = i;HT[i].lchild = s1 > s2 ? s2 : s1;//此处修改是为了和书上的编码保持一致HT[i].rchild = s1 + s2 - HT[i].lchild;HT[i].weight = HT[s1].weight + HT[s2].weight;}HC = (HuffmanCode)malloc(sizeof(char*) * (n + 1));char* cd = (char*)malloc(n * sizeof(char));cd[n - 1] = 0;for (int i = 1; i <= n; i++){int start = n - 1;for (int c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)if (HT[f].lchild == c)cd[--start] = '0';else cd[--start] = '1';HC[i] = (char*)malloc((n - start) * sizeof(char));strcpy(HC[i], cd + start);}free(cd);
}
void Select(HuffmanTree HT, int& s1, int& s2,int i)
{int j, m;for (j = 1; j < i; j++)if (!flag[j]){m = j;break;}for (j = m; j < i; j++)if (!flag[j] && HT[m].weight > HT[j].weight)m = j;flag[m] = 1; s1 = m;for (int j = 1; j < i; j++)if (!flag[j]){m = j;break;}for (j = m; j < i; j++)if (!flag[j] && HT[m].weight > HT[j].weight)m = j;flag[m] = 1, s2 = m;
}
/*
8
5 29 7 8 14 23 3 11
*/运行结果：
本文链接：https://my.lmcjl.com/post/9817.html
展开阅读全文
4 评论