什么是哈夫曼树?
哈夫曼树(Huffman Tree)是一种用于数据压缩的树形数据结构,由David A. Huffman在1952年发明。哈夫曼树通常用于无损数据压缩中,将出现频率高的字符编码成较短的二进制序列,从而减少数据的存储空间。
哈夫曼树的构建过程是基于贪心算法,即每次选择出现频率最低的两个节点合并为一个新的节点,并将它们的权值相加作为新节点的权值,直到最终只剩下一个节点为止。在构建过程中,需要保证所有节点的左子树的权值总和小于右子树的权值总和。
最终生成的哈夫曼树是一棵带权路径长度最小的二叉树,可以根据哈夫曼树来生成每个字符的编码,从而实现数据压缩。
哈夫曼树构建过程
从数组中选择权值最小的两个结点,作为子结点,生成一棵树。
他们父结点的权值是他们两结点的权值之和。
然后再以此类推,重复两步,当数组中只剩下一棵树的时候,就已经构建好哈夫曼树了。
构建哈夫曼树代码(C++)
下面是使用c++实现的构建哈夫曼树的代码
//哈夫曼树构建
BTreeNode *CreateHuffman(ElemType a[],int n) {
BTreeNode **b,*q;
b=new BTreeNode*[n];
int i,j;
for(i=0; i<n; i++) {
b[i]=new BTreeNode;
b[i]->data=a[i];
b[i]->left=b[i]->right=NULL;
}
for(i=1; i<n; i++) {
int k1=-1,k2;
for(j=0; j<n; j++) {
if(b[j]!=NULL&&k1==-1) {
k1=j;
continue;
}
if(b[j]!=NULL) {
k2=j;
break;
}
}
for(j=k2; j<n; j++) {
if(b[j]!=NULL) {
if(b[j]->data.weight<b[k1]->data.weight) {
k2=k1;
k1=j;
} else if(b[j]->data.weight<b[k2]->data.weight) {
k2=j;
}
}
}
q=new BTreeNode;
q->data.weight=b[k1]->data.weight+b[k2]->data.weight;
q->left=b[k1];
q->right=b[k2];
b[k1]=q;
b[k2]=NULL;
}
delete []b;
return q;
}
哈夫曼前中后、层次遍历
这里和二叉树是一样的,就不过多赘述了。都是采用了递归的算法。
c++实现:
//前序遍历
void PreOrder(BTreeNode* BT) {
if(BT==NULL){
return;
}
cout<<BT->data.letter<<' ';
PreOrder(BT->left);
PreOrder(BT->right);
}
//中序遍历
void InOrder(BTreeNode* BT) {
if(BT==NULL){
return;
}
InOrder(BT->left);
cout<<BT->data.letter<<' ';
InOrder(BT->right);
}
//后序遍历
void PostOrder(BTreeNode* BT) {
if(BT==NULL){
return;
}
PostOrder(BT->left);
PostOrder(BT->right);
cout<<BT->data.letter<<' ';
}
层次遍历:
需要使用队列,首先根节点入队列,只要队列不是空的时候,头结点出队,并且访问出队结点,然后出队结点的左右孩子结点入队列。
一直重复上述步骤,最终即可实现层次遍历。
//层次遍历
void LevelOrder(BTreeNode* BT) {
const int MaxSize=30;
BTreeNode* q[MaxSize];
int front=0,rear=0;
BTreeNode* p;
if(BT!=NULL) {
rear = (rear+1)%MaxSize;
q[rear] = BT;
}
while(front!=rear) {
front=(front+1)%MaxSize;
p=q[front];
cout<<p->data<<' ';
if(p->left!=NULL) {
rear=(rear+1)%MaxSize;
q[rear]=p->left;
}
if(p->right!=NULL) {
rear=(rear+1)%MaxSize;
q[rear]=p->right;
}
}
}
哈夫曼树编码
很多时候,再通讯的时候会使用到,需要对信息进行编码,这个时候哈夫曼树就可以对这些通讯实现最优的编码。
下面是哈夫曼树编码的实现算法:
通过递归调用实现哈夫曼编码,函数首先判断当前结点是否由孩子结点,如果没有孩子结点,就直接遍历静态数组,输出,此时数组就是当前结点的哈夫曼编码。如果有孩子结点,就继续递归,左孩子结点就给数组赋值为0,右孩子结点就给结点赋值为1。
c++:
//哈夫曼树编码,len传入的时候是0,因为根节点的是0
void HuffManCoding(BTreeNode *FBT,int len){
static int a[10];
if(FBT!=NULL){
if(FBT->left==NULL&&FBT->right==NULL){ //这里证明已经到了叶子结点,可以开始将a数组进行遍历输出即可形成编码
cout<<FBT->data.letter<<"的编码为:";
for(int i=0;i<len;i++){
cout<<a[i];
}
cout<<endl;
}else{ //还不是叶子结点,递归调用继续往下走
a[len]=0;
HuffManCoding(FBT->left,len+1);
a[len]=1;
HuffManCoding(FBT->right,len+1);
}
}
}
评论 (0)