哈夫曼编码与二叉树实现详解

哈夫曼编码与二叉树实现详解

引用

CSDN

1.

https://m.blog.csdn.net/qq_74047911/article/details/141109912

哈夫曼编码是一种广泛应用于数据压缩的编码方式，通过构建哈夫曼树来实现字符的最优编码。本文将从哈夫曼编码的基本概念出发，详细介绍其在数据压缩中的应用原理，并通过代码实现来展示具体步骤。

一.哈夫曼编码是什么?

哈夫曼编码主要是用在数据压缩中。打个比方我们正常的一个字符占8位,那么我们可以编码少于8位。一个文本文件,如果我们想要节省空间,那么我们可以将里面出现次数较多的字符用少于8位的编码进行声明,那么我们可以大大的节省空间。

假如"we will we will r u"这个字符串。每个字符原本占8位,那么一个19个字符就占152位,包括空格。如果我们对出现的频率进行计算:空格出现5,w出现4,l出现4,e出现2,i出现2,r出现1,u出现1。我们就可以对其进行编码,l:00 w:01 空格:10 e:110 i:1111 u:11100 r:11101

出现频率越高的字符,我们用越短的位进行编码。为什么是这样编码的了,为了防止重复,检测到00那就是l,不可能出现001。那么刚好就像我们树的叶子,我们只需要将这些字符放在树的叶上,就能保证每一个字符的编码都不一样,从根节点向左我们记作0,向右我们记作1。

二.哈夫曼二叉树的构建过程

我们可以看成,树的层次越多,那么编码的位数就越大,那么出现的频率就越低。所以我们重出现频率最低的开始构建树。红色为该字符出现的次数频率,从频率最低的开始作为叶子节点,他们的频率之和作为父节点。然后每次都是频率最低的两个结合。以此类推,我们就可以实现哈夫曼编码二叉树。

三.哈夫曼二叉树的实现

1.优先级队列

因为我们需要根据出现的次数来进行树的建立,所以我们考虑到了优先级队列。出现次数越少的我们的优先级越高,先来构建。

①优先级队列的结构

一个头节点,包含首尾指针和长度。指向的是队列节点。节点的数据是数。

队列里面装的是树。树包含值就是字符,还有权重就是出现次数,还有父节点,左孩子,右孩子节点

②.优先级队列的初始化

③.优先级队列判断是否为空或满

④.入队

因为是优先级队列,不用在乎插入在什么位置,这里是用的前插法,是为了新结合的节点与频率相同节点先进行结合。

⑤.出队

int popQueue(LinkQueue* LQ, DataType* data)
{
    QNode** prev = NULL, * prev_node = NULL;
    QNode* last = NULL, * tmp = NULL;
    if (!LQ || isEmpty(LQ))
    {
        cout << "队列为空!" << endl;
        return 0;
    }
    if (!data)return 0;
    prev = &(LQ->front);
    last = LQ->front;
    tmp = last->next;
    while (tmp)
    {
        if (tmp->priority < (*prev)->priority)
        {
            prev = &(last->next);
            prev_node = last;
        }
        last = tmp;
        tmp = tmp->next;
    }
    *data = (*prev)->data;
    tmp = *prev;
    (*prev) = tmp->next;
    delete tmp;
    LQ->length--;
    if (LQ->length == 0)
    {
        LQ->rear = NULL;
    }
    if (prev_node&& prev_node->next == NULL)
    {
        LQ->rear = prev_node;
    }
    return 1;
}

优先级队列那节讲过就不多讲了,这里是优先级值越小的先出去。

⑥.遍历队列

⑦.其他小接口

2.具体实现

创建一个队列,然后树节点赋值,再插入到队列中,优先级就是树节点的权重。现在就相当于得到了这个:

然后先出列两个最小的作为子节点,然后其和作为父节点,然后父节点又去和其他节点比较。直到最后队列为空。判断一开始队列为不为空,不为空就先出一个。然后再出一个队列,然后结合出的两个节点,作为父节点再入队列。如果队列为空,就将最后一个结合的节点作为根节点。我们传入的参数是指针引用,所以这个树就被保存了下来。

3.运行结果

树的遍历。运行结果(假设s是空格):

四.完整代码

#include "Huff.h"
#include <iostream>
using namespace std;
void HuffmanTree(Btree*& huff, int n)
{
    LinkQueue* LQ = new LinkQueue;
    int i = 0;
    initQueue(LQ);
    for (i = 0; i < n; i++)
    {
        Bnode* node = new Bnode;
        cout << "请输入第" << i + 1 << "个字符和出现概率:" << endl;
        cin >> node->value;
        cin >> node->weight;
        node->parent = NULL;
        node->rchild = NULL;
        node->lchild = NULL;
        
        EnterQueue(LQ, node, node->weight);
    }
    printQueue(LQ);
    while (1)
    {
        Bnode* node1 = NULL;
        Bnode* node2 = NULL;
        if (!isEmpty(LQ))
        {
            popQueue(LQ, &node1);
        }
        else//一开始队列为空
        {
            break;
        }
        if (!isEmpty(LQ))
        {
            Bnode* node3 = new Bnode;
            popQueue(LQ, &node2);
            node3->lchild = node1;
            node3->rchild = node2;
            //node1->parent = node3;
            //node2->parent = node3;
            node3->value = 0;
            node3->weight = node1->weight + node2->weight;
            EnterQueue(LQ, node3,node3->weight);
        }
        else
        {
            huff = node1;
            break;
        }
    }
}
void PreOrderRec(Btree* root)
{
    if (root == NULL)
    {
        return;
    }
    cout << "- " << root->value << " -";
    PreOrderRec(root->lchild);
    PreOrderRec(root->rchild);
}
int main()
{
    Btree* tree = NULL;
    HuffmanTree(tree, 7);
    PreOrderRec(tree);
    system("pause");
    return 0;
}

haff.h就是队列的实现。