哈夫曼编码
哈夫曼树
哈夫曼树
介绍
目的
找出存放一串字符所需的最少的二进制编码
哈夫曼树的构造
- 第1步：创建森林，森林包括5棵树，这5棵树的权值分别是5,6,7,8,15。
- 第2步：在森林中，选择根节点权值最小的两棵树(5和6)来进行合并，将它们作为一颗新树的左右孩子(谁左谁右无关紧要，这里，我们选择较小的作为左孩子)，并且新树的权值是左右孩子的权值之和。即，新树的权值是11。 然后，将”树5”和”树6”从森林中删除，并将新的树(树11)添加到森林中。
- 第三步：重复第二步。
哈夫曼编码
构建好哈夫曼树，左0右1，从上到下进行编码代码演示
存储哈夫曼树
typedef struct
{
int weight;//存储权值
int partent,LChild,RChild;//指向双亲和子节点
}HTCode，*HuffmanTree;//动态分配数组，用来存储哈夫曼树 HTCode和*HuffmanTree是一样的，只是来增加代码的可读性
存储哈夫曼编码
typedef char **HuffmanCode; //动态分布数组，指向字符指针的指针，存储哈夫曼编码
select函数
void select(HuffmanTree ht,int n,int *s1,int *s2)
{
//在ht[1]~ht[n]范围内选择两个parent为0 且weight最小的结点，其序号分别赋值给s1、s2
int i;
*s1=*s2=1;
int main1=100000;
int min2=min1;
for(i=1;i<=n;i++)
{
if(ht[i].parent==0)
{
if(ht[i].weight<min1)
{
*s2=*s1;
*s1=i;
min2=min1;
min1=ht[i].weight;
}
if(ht[i].weight<min2)
{
*s2=i;
min2=ht[i].weight;
}
}
}
}
构造哈夫曼树
void CrtHuffmanTree(HffmanTree ht,int *w,int n)
{//构造哈夫曼树ht[m+1], w[]存放已知的n个权值
int i,m,s1,s2;
for(i=1;i<=n;i++) //1~n号单元存放叶子结点，初始化
{
ht[i].weight=w[i];
ht[i].parent=ht[i].LChild=ht[i].RChild=0;
}
m=2*n-1;
// 初始化完毕！以下创建非叶子结点，建哈夫曼树
for(i=n+1;i<=m;i++)
{
select(ht,i-1;&s1,&s2);
ht[i].weight=ht[s1].weight + ht[s2].weight;
ht[s1].parent=h[s2].parent=i;
ht[i].LChild = s1; ht[i].RChild = s2;
}
}
先序遍历哈夫曼树
void PreOrderHuffman(HuffmanTree ht,int m)
{
//先序遍历哈夫曼树
int l,r;
printf("%5d",ht[m].weight);
l=ht[m].LChlid;
if(k!=0)
{
PreOrderHuffman(ht,l);
}
r=ht[m].RChild;
if(r!=0)
{
PreOrderHuffman(ht,r);
}
}
求每个叶结点的哈夫曼编码
void CrtHuffmanCode(HuffmanTree ht, HuffmanCode hc, int n)
{//从叶子结点到根，逆向求每个节点所对应的哈夫曼编码
char *cd;
int i,start,p,c;
cd=(char *)malloc(n*sizeof(char));// 分配求当前编码的工作空间
cd[n-1]='\0';// 从右向左逐位存放编码，首先存放编码结束符
for(i=1;i<=;i++) // 求n个叶子结点对应的哈夫曼编码
{
start=n-1;//初始化编码起始指针
for(c=i,p=ht[i].parent;p!=0;c=p,p=ht[p].parent) //从叶子到根结点求编码
cd=[--start]=((ht[p].LChild==c)? '0':'1');//左分支标0，右分支标1
hc[i]=(char*)malloc((n-start)*sizeof(char)); // 为第i个编码分配空间
strcpy(hc[i],&cd[start]);
}
free(cd);
}
主函数
int main(){
HuffmanTree HT; HuffmanCode HC;
int 1,n,m; int *w;
char ch;
n=0;
//输入叶子结点数及权重
printf("Input the number of total leaf of Huffman Tree:");
scanf("%d",&n);
m=2*n-1;
HT=(HuffmanTree )malloc((m+1)*sizeof(HTNode));
HC=(HuffmanCode)malloc((n)*sizeof(HTNode));
w=(int *)malloc((n+1)*sizeof(int)); // 0号单元未使用
for (i=1; i<=n; i++)
{
printf("Input the %d element's weight:",i);
scanf("%d",&w[i]); // 依次输入5 7 3 2 8
}
// 生成哈夫曼树并输出
CrtHuffmanTree( HT,w, n);
for (i=1; i<=m; i++)
{
printf("\n%5d%5d%5d%5d", HT[i].weight, HT[i].parent,HT[i].LChild, HT[i].RChild);}
}
printf("\n\n");
// 先序遍历哈夫曼树
PreOrderHuffman(HT,m); printf("\n\n");
// 生成哈夫曼编码并输出
CrtHuffmanCode(HT, HC, n);
for (i=1; i<=n; i++)
printf("%d编码为%s\n", HT[i].weight,HC[i]);
getchar(); getchar();
return 0;
}
相关问题
1. 为什么要保证长编码不与短编码冲突？
冲突情况：如果我们已经确定D，E，F，G 用 01 ，010 ，10，001的2进制编码来传输了。那么想传送FED时，我需要传送 1001001，接收方可以把它解析为FDG（10 01 001），当然也能解析为FED（10 010 01），他两编码一样的，这就是编码冲突，（这里编码冲突的原因，也是因为编码时，D的编码是E的编码的左起子串了）显然这是不行的，就像我说压脉带，你如果是日本人会理解为 （你懂得），这就是发出同一种语，得出不同的意的情况。所以不能让一个字母的二进制代表数，为另一个字母的二进制代表数的子串。但为什么实际情况只要求编码时，一个编码不是另一编码的左起子串呢而不是绝对意义上的非子串呢，因为计算机从数字串的左边开始读，如果从右边读，那么可以要求是非右起（无奈）。你又可以问了为什么编码要求是非左起或非右起不直接规定不能是子串呢（也行，不过=>），比如说原文中B就是C，F，G的子串，那这不就不符合规则了么。这里是为了哈夫曼的根本目的，优化编码位占用问题，如果完全不能有任何子串那么编码将会非常庞大。但这里计算机是一位一位的·读取编码的，只需要保证计算机在读取中不会误判就行。并且编码占用最少。
code：0110101001110
左起子串：011
右起子串：110
绝对非子串：1110111 此串在code中完全找不到
2. 那么哈夫曼树怎么避免左起子串问题呢？
因为哈夫曼是从叶子节点开始构造，构造到根节点的，而且构造时，都是计算两个权值的节点的和再与其他叶子节点再生成一个父节点来组成一个新的树。并且不允许任何带有权值的节点作为他们的父节点。这也保证了所有带有权值的节点都被构造为了叶子节点。然后最后编码的时候是从根节点开始走到叶子节点而得出的编码。在有权值的节点又不会出现在任何一条路的路途中的情况，只会出现在终点的情况下，因此不会出现01代表一个字母011又代表一个字母。
又如原文ABC编码为10010011的情况，当计算机读到10时，由于有左起子串不冲突的原则。那么计算机完全可以保证当前的10就是A字母，然后再往下读010011的部分，然后当读到01时，也完全能确定B，C同理，而不用说因为会出现冲突的编码而接着继续读取之后的编码来确定前面的编码。这样对信息的判断和效率是相当的不利的，也不是说不可以。即使你ABCD,分别用01,011,0111,01111来代替也行，传输后也能精确识别，但是数据量极大呢，想代替整个中文编码呢，那0后面得多少个1才能代表完。因此哈夫曼就是为了获得最少编码量代替最多字符串，并且不冲突，系统不会误判而产生的。
3. 这里要提一下同权不同构
这里要说一下哈夫曼树的构造并不是唯一的。但是他们构成的哈夫曼树的带权路径长度是相同的。
参考链接：https://blog.csdn.net/qq_29519041/article/details/81428934