好资源导航 » 文章资讯 » C++实现哈夫曼树的方法

C++实现哈夫曼树的方法

2023-07-26 13:06:04 73

序言

对于哈夫曼编码，个人的浅薄理解就是在压缩存储空间用很大用处。
用一个很简单例子，存储一篇英文文章时候，可能A出现的概率较大，Z出现的记录较小，如果正常存储，可能A与Z存储使用的空间一样。但是用哈夫曼编码方式，A经常出现，所用编码长度就短。

构造哈夫曼树，生成哈夫曼编码

一、定义节点类型

structNode{
charC;
longkey;
Node*Left,*Right,*parent;
Node(){Left=Right=NULL;}
};

二、定义树类型（节点数组）

三要素：不定长数组，元素大小，有效元素个数

structRootA{
Node*NodeA;
constintSize;
intn;
RootA(intSize):Size(Size){n=0;NodeA=newNode[Size];}
~RootA(){delete[]NodeA;}
};

三、创建哈夫曼树

1.将每一个节点都当成一棵树，初始化数组大小，并进行赋值

RootARA(4);
//1.在RA.NodeA中存入字母和权值
for(RA.n=0;RA.n>RA.NodeA[RA.n].C;
cout<<"权值：";
cin>>RA.NodeA[RA.n].key;
}

2.将树按权值大小排序

voidSort(RootA*ra){
for(inti=0;in;i++){
boolESC=false;
for(intj=0;jn-i-1;j++){
if(ra->NodeA[j].key>ra->NodeA[j+1].key){
NodeT;T=ra->NodeA[j];ra->NodeA[j]=ra->NodeA[j+1];ra->NodeA[j+1]=T;
ESC=true;
}
}
if(!ESC)return;
}
}

3.(1)遍历数组，将RA.NodeA[0]和RA.Node[1]合并，其余向前移动，重新排序
(2)将RA.NodeA[0]，RA.NodeA[1]分别放在新合并的RA.NodeA[0]的左右子结点中

while(RA.n>1){
//1.将RA.NodeA[0]和RA.NodeA[1]合并，将其余向前移动
Node*NewNode0=newNode;
*NewNode0=RA.NodeA[0];
Node*NewNode1=newNode;
*NewNode1=RA.NodeA[1];
RA.NodeA[0].C='';
RA.NodeA[0].key=RA.NodeA[0].key+RA.NodeA[1].key;
RA.NodeA[0].Left=NewNode0;
NewNode0->parent=&RA.NodeA[0];
RA.NodeA[0].Right=NewNode1;
NewNode1->parent=&RA.NodeA[0];
for(inti=1;i
4.输出哈夫曼编码
递归，找到叶子节点，记录路径，左记录0，右记录1，直到输出所有叶子节点
voidCrateCode(Node*t,string&s){
//1.遍历节点，遍历左节点编码为0,右节点则为1，递归，直到输出所有叶子节
if(t->Left!=NULL&&t->Right!=NULL){
s.push_back('0');CrateCode(t->Left,s);
s.pop_back();
s.push_back('1');CrateCode(t->Right,s);
s.pop_back();
}
else{
cout<<"哈夫曼编码：";
cout<C<<":"<
以上是对构造哈夫曼树以及生成哈夫曼编码的总结，希望对你们有所帮助！
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

C++实现哈夫曼树的方法

热门推荐

随机推荐