赫夫曼树与赫夫曼编码
创新互联建站主营吉林网站建设的网络公司,主营网站建设方案,
成都App定制开发,吉林h5成都微信小程序搭建,吉林网站营销推广欢迎吉林等地区企业咨询前言
（概念）
路径：从一个节点到另一个节点的分支
路径长度：从一个节点到另一个节点的分支总数
节点的带权路径：该节点到根节点之间路径长度与权值的乘积
树的带权路径长度(WPL)：所有叶子节点的带权路径长度之和
赫夫曼树
存储结构
赫夫曼树采取静态存储的方式，以下面为例：
初始化树
所需头文件：
#includeusing namespace std;
#include#include#include
初始化树：
const int n = 8; //叶子个数（权值个数）
const int m = 2 * n; //树节点个数+1（第0下标不放值，是标记位）
typedef unsigned int WeightType; //权值类型
typedef unsigned int NodeType; //节点类型
typedef struct //树节点
{WeightType weight;
NodeType parent, leftchild, rightchild;
}HtNode;
typedef HtNode HuffmanTree[m]; //赫夫曼树
void InitHuffmanTree(HuffmanTree hft,const WeightType w[])
{for (int i = 0; i< n; i++)
{hft[i + 1].weight = w[i];
}
}
打印树：
void PrintHuffmanTree(HuffmanTree hft)
{cout<< "（赫夫曼树：）"<< endl;
for (int i = 1; i< m; i++)
{cout<< " index: "<< i<< "\tweight: "<< hft[i].weight<< "\tparent: "<< hft[i].parent<< "\tLchild: "<< hft[i].leftchild<< "\tRchild: "<< hft[i].rightchild<< endl;
}
cout<< endl<< endl;
}
主函数：
int main()
{WeightType w[n] = {5,29,7,8,14,23,3,11 };
HuffmanTree hft = {0 };
InitHuffmanTree(hft, w);
PrintHuffmanTree(hft);
return 0;
}
初始化结果：
构建树
使用优先级队列来存放存有下标和权值的结构体，使用greater：将数据大的下沉（形成小顶堆），使用less：将小数据下沉（形成大顶堆）
代码实现：
struct IndexWeight
{int index; //下标
WeightType weight; //权值
operator WeightType() const {return weight; } //重载（当用此结构体作比较时，用weight来进行比较）
};
void CreateHuffmanTree(HuffmanTree hft)
{std::priority_queue, std::greater>qu; //优先级队列（小顶堆）
for (int i = 1; i<= n; i++)
{qu.push(IndexWeight{i,hft[i].weight });
}
int k = n + 1;
while (!qu.empty())
{if (qu.empty()) {break; }
IndexWeight left = qu.top();
qu.pop();
if (qu.empty()) {break; }
IndexWeight right = qu.top();
qu.pop();
hft[k].weight = left.weight + right.weight;
hft[k].leftchild = left.index;
hft[k].rightchild = right.index;
hft[left.index].parent = k;
hft[right.index].parent = k;
qu.push(IndexWeight{k,hft[k].weight });
k++;
}
}
打印树：
void PrintHuffmanTree(HuffmanTree hft)
{cout<< "（赫夫曼树：）"<< endl;
for (int i = 1; i< m; i++)
{cout<< " index: "<< i<< "\tweight: "<< hft[i].weight<< "\tparent: "<< hft[i].parent<< "\tLchild: "<< hft[i].leftchild<< "\tRchild: "<< hft[i].rightchild<< endl;
}
cout<< endl<< endl;
}
主函数：
int main()
{WeightType w[n] = {5,29,7,8,14,23,3,11 };
HuffmanTree hft = {0 };
InitHuffmanTree(hft, w);
CreateHuffmanTree(hft);
PrintHuffmanTree(hft);
return 0;
}
构建结果：
赫夫曼编码
以此赫夫曼树为例：
原本发送"ABCDEFGH"这些字符时，每个字符都是8个二进制位（char 1字节）总共要发：8*8=64位二进制，但通过赫夫曼编码后总共要发：27位二进制，因此赫夫曼编码在文件传输时有巨大作用
初始化编码
代码实现：
typedef struct
{char ch; //节点对应的数据
char code[n+1]; //该节点的赫夫曼编码
}HuffmanCode;
typedef HuffmanCode HuffmanCoding[n];
void InitHuffmanCode(HuffmanCoding hfc,const char ch[])
{for(int i=0;ihfc[i].ch=ch[i];
hfc[i].code[n]={'\0'};
}
}
打印编码：
void PrinthuffmanCode(HuffmanCoding hfc)
{for (int i = 0; i< n; i++)
{cout<< " data: "<< hfc[i].ch<< " 的赫夫曼编码："<< hfc[i].code<< endl;
}
}
主函数：
int main()
{WeightType w[n] = {5,29,7,8,14,23,3,11 };
HuffmanTree hft = {0 };
InitHuffmanTree(hft, w);
CreateHuffmanTree(hft);
PrintHuffmanTree(hft);
const char ch[n + 1] = {"ABCDEFGH" }; //必须是n+1，双引号最后会有一个'\0'
HuffmanCoding hfc = {0 };
InitHuffmanCode(hfc, ch);
PrinthuffmanCode(hfc);
return 0;
}
初始化结果：
构建编码
从叶子节点向根节点走，如果是左孩子则为0，反之则为1
创建一个数组来存放0，1值，从后向前存放，这样读取的时候就是正着读取的
代码实现：
void CreateHuffmanCode(HuffmanTree hft, HuffmanCoding hfc)
{char code[n + 1] = {0 };
for (int i = 1; i<= 8; i++)
{int k = n;
int child = i;
int parent = hft[i].parent;
while (parent != 0)
{ if (child == hft[parent].leftchild)
{ code[--k] = {'0' };
}
else if (child == hft[parent].rightchild)
{ code[--k] = {'1' };
}
child = parent;
parent = hft[child].parent;
}
strcpy_s(hfc[i - 1].code, n, &code[k]);
}
}
打印编码：
void PrinthuffmanCode(HuffmanCoding hfc)
{for (int i = 0; i< n; i++)
{cout<< " data: "<< hfc[i].ch<< " 的赫夫曼编码："<< hfc[i].code<< endl;
}
}
主函数：
int main()
{WeightType w[n] = {5,29,7,8,14,23,3,11 };
HuffmanTree hft = {0 };
InitHuffmanTree(hft, w);
CreateHuffmanTree(hft);
PrintHuffmanTree(hft);
const char ch[n + 1] = {"ABCDEFGH" }; //必须是n+1，双引号最后会有一个'\0'
HuffmanCoding hfc = {0 };
InitHuffmanCode(hfc, ch);
CreateHuffmanCode(hft, hfc);
PrinthuffmanCode(hfc);
}
构建结果：
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
当前标题：【数据结构】赫夫曼树与编码-创新互联
当前URL：
http://cdkjz.cn/article/cddgps.html
