哈夫曼树学习笔记-构建哈夫曼树

吃猫的鱼
2023-05-21 / 0 评论 / 138 阅读 / 正在检测是否收录...

什么是哈夫曼树?

哈夫曼树(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);
        }
    }
}

1

评论 (0)

取消
友情链接 文章阅读: 网站地图