首页 > 代码库 > 算法基础（九）：超详细最优二叉树构建（2）求编码
算法基础（九）：超详细最优二叉树构建（2）求编码
从叶子到跟逆向求每个字符的赫夫曼编码：
void GetHuffmanCode(HuffmanTree &HT,HuffmanCode &HC,int n)
{
char* cd;
int c;
int f;
int start;
int i = 0;
//从叶子到根逆向求每个字符的哈夫曼编码
printf("\n进入求编码函数...");
HC = (HuffmanCode)malloc( (n+1) * sizeof(char*)); //分配n个字符编码的头指针向量
cd = (char*)malloc(n*sizeof(char)); //分配求编码的工作空间,n个，因为有n个叶子节点
cd[n - 1] = ‘\0‘; //编码结束符
for(i = 1;i <= n;++i) //逐个字符求哈弗曼编码
{
start = n - 1; //编码结束符位置
for(c = i,f = HT[i].parent;f != 0;c = f,f = HT[f].parent) //f!=0保证一直朝上走，走到根节点
{
if(HT[f].lchild == c) //判断是否为左孩子
cd[--start] = ‘0‘;
else cd[--start] = ‘1‘; //右孩子
}
//退出循环，第i个叶子节点的huffmancode求出，开辟空间，然后赋值，因为HC是char**类型
HC[i] = (char*)malloc( (n - start) * sizeof(char));
strcpy(HC[i],cd+start);
printf("\n编号为:%d，权值为：%d的哈弗曼编码为：",i,HT[i].weight);
puts(HC[i]);
}
free(cd); //释放工作空间这段代码加到上一篇文章的头文件里或者main.cpp里面都可以，main.cpp如下：
#include"stdafx.h"
//#include"BasicGraph2.h"
#include "HuffmanCode.h"
void main()
{
HuffmanTree HT;
HuffmanCode code;
int n = 8;
int m = 15;
int arr[] = {5,29,7,8,14,23,3,11};
if(HuffmanCoding(HT,arr,n)) //构建哈弗曼树
ShowHT(HT,n); //测试是否正确
GetHuffmanCode(HT,code,n); //求哈弗曼编码，结果保存在code中
}运行结果：
结构图：
注意：8号和11号和我最初画的位置相反。
算法基础（九）：超详细最优二叉树构建（2）求编码
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。