数据结构 —— 哈夫曼树

到达叶子节点的路径都是不一样的，没有一个到达叶子节点时经过其它的叶子节点，因此每个叶子节点的编码不可能是其它叶节点编码的前缀，保证了哈夫曼编码是前缀编码。传送字符为ABACCDA，A—00，B—01，C—10，D—11，编码后为：00010010101100。5%需要判断1次，15%需要判断2次，40%需要判断3次，30%需要判断4次，10%需要判断4次、5%需要判断3次，15%需要判断3次，4

腿毛常常长长

2077人浏览 · 2023-07-17 15:52:55

腿毛常常长长 · 2023-07-17 15:52:55 发布

文章目录

- 哈夫曼树数据结构

哈夫曼树数据结构

哈夫曼树的引入

判断树：用于描述判断分类的过程的二叉树

在这里插入图片描述
例如成绩等级的判断，若每次输入量很大：

右边判断树的比较次数

5%需要判断1次，15%需要判断2次，40%需要判断3次，30%需要判断4次，10%需要判断4次、

10000个同学需要一共判断500 + 1500 * 2 + 4000 * 3 + 3000 * 4 + 1000 * 4 = 31500次
左边判断树的比较次数

5%需要判断3次，15%需要判断3次，40%需要判断2次，30%需要判断2次，10%需要判断2次

10000个同学需要一共判断500 * 3 + 1500 * 3 + 4000 * 2 + 3000 * 2 + 1000 * 2 = 22000次

如何找到效率最高，最优判断次数的判断树呢？—— 哈夫曼树(最优二叉树)

哈夫曼树的基本概念

路径，从树中一个节点到另一个节点的分支构成的两个节点的路径；
权重，树中节点赋权值；节点的带权路径长度
无权：
- 节点的路径长度，是两节点路径上的分支数
- 树的路径长度，从树根到每一个节点的路径长度之和
  
  节点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树
有权：
- 节点的路径长度，从根节点到该节点之间路径长度与该节点的权重乘积
- 树的路径长度，树中所有叶子节点的带权路径长度之和 WPL(weighted path length)

哈夫曼树：带权路径WPL最短的树，最优树（前提度都相同。

带权路径最短的二叉树 -> 最优二叉树，构造哈夫曼树的算法被称为哈夫曼算法

如何构造哈夫曼树？

使用到了贪心算法：构造哈夫曼树时优先选择权值最小的叶子节点去构造树

根据给定的N个权重，构造N棵二叉树的森林，构造森林全部都是根
选择两个根节点权值最小的数作为左右子树，构造一颗新的二叉树；且设置新二叉树根节点的权值为两个根节点的权值和。删除原来的两棵树，并将新的二叉树添加到森林中
重复上面的步骤，直到森林中只有一颗树，这颗树即为哈夫曼树

初始有n棵二叉树，经过n-1次合并后最终形成哈夫曼树

经过n-1次合并产生 n-1个新节点，这些新节点都是具有两个孩子的分支结点

因此：

哈夫曼树的结点的度数为0或者为2，没有度为 1 的结点

包含N个叶子结点的哈夫曼二叉树中共有N + N - 1 = 2N-1个结点

哈夫曼树数据结构的实现：顺序存储结构(一维结构数组)

步骤：
- 初始化有权值的结点，权值/左孩子/右孩子/自己，并把结点加入到优先队列中去
- 只要优先队列不为空，弹出优先队列中两个权值最小的节点生成新节点
  
  更新新节点的权值(两个节点的权值和)/左孩子/右孩子/自己，然后把新节点加入到优先队列中
- 加入最后队列中只剩下一个节点，则说明队列中的节点是生成哈夫曼树的根节点

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

struct HTNode{
    int w;                // 权重
    HTNode* self = nullptr;
    HTNode* parent = nullptr;
    HTNode* lch = nullptr;
    HTNode* rch = nullptr;
    bool operator < (const HTNode &b) const{
        return w > b.w;
    }
};

vector<int> weights;
priority_queue<HTNode> pq;
HTNode root;

void build(){
    while(!pq.empty()){
        HTNode tmp1 = pq.top();
        pq.pop();
        if(!pq.empty()){
            HTNode tmp2 = pq.top();
            pq.pop();
            HTNode* newNode = new HTNode;
            newNode->w = tmp1.w + tmp2.w;
            newNode->self = newNode;
            newNode->lch = tmp1.self;
            newNode->rch = tmp2.self;
            pq.push(*newNode);
        }else root = tmp1;
    }
}

//先序遍历
void pre(HTNode *root){
	if(root){
		cout<<root->w<<" ";
		pre(root->lch), pre(root->rch);
	}
} 

int main(){
    int n, w;
    cin >> n;
    if(n <= 1) return 0;
    // 1. 输入权值，并进行初始化操作(结点的权值，入优先队列)
    for(int i = 0; i < n; i++){
        cin >> w;
        weights.push_back(w);
        HTNode* s = new HTNode;
        s->w = w, s->self = s;
        pq.push(*s);
    }
    // 2. 构造哈夫曼树
    build();

    // 3. 输出
    cout<<"********************"<<endl; 
	pre(root.self);
    return 0;
}

哈夫曼树的应用

哈夫曼编码

传送字符为ABACCDA，A—00，B—01，C—10，D—11，编码后为：00010010101100

定长编码方式：浪费空间，希望对该编码方式进行压缩

改进优化为不等长的字符串，即让字符串中出现较多的字符采取尽可能短的编码

A—0，B—00，C—1，D—01，编码后为000011010

问题：解码的时候发生重码，例如前面的0000 可以代表三个不同的意思：

AAAA/ ABA / BB 发生重码，因此需要继续改进，任意字符的编码不能是另一字符编码的前缀
使用哈夫曼编码设计前缀码
- 统计字符集中每个字符在电文中出现的平均概率（概率越大，要求编码越短）
- 利用哈夫曼树的特点：权重越大的叶子离根越近；将每个字符的概率值作为权值，构造哈夫曼树，则概率越大的节点，路径越短。
- 节点的左分支标0，右分支标1，从根到每个叶子的路径上的标号连接，作为该叶子代表的字符编码
为什么哈夫曼编码能够保证是前缀码？

到达叶子节点的路径都是不一样的，没有一个到达叶子节点时经过其它的叶子节点，因此每个叶子节点的编码不可能是其它叶节点编码的前缀，保证了哈夫曼编码是前缀编码

为什么哈夫曼编码能够保证字符编码总长最短？

因为哈夫曼树就是带权路径长度最短的树，因此字符编码的总长最短
哈夫曼编码的实现过程：

已经得到2n-1个节点前0_{n-1个节点是叶子节点，后面n}2n-1是非叶子节点

左分支标号0，右分支标号1，拿到哈夫曼树后，如何表示哈夫曼编码？
- 从叶子节点往上，找叶子节点的parent节点看该叶子节点是parent的lch还是rch，是lch则标注0，并把遍历的指针更新到parent节点上
- 不断循环，直到parent节点为0（根节点），反转后即为从根到叶子节点的哈夫曼节点
以上过程需要n次，每个叶子节点都需要进行一次编码