哈夫曼树学习笔记

哈夫曼树学习笔记

hash070 499 2022-05-14

简介

哈夫曼树是一类带权路径最短的树。构造这种树的算法最早由哈夫曼提出，这种树在信息检索中很有用。如用于通讯及数据传送中构造传输效率最高的二进制编码（哈夫曼编码），用于编程中构造平均执行时间最短的最佳判断过程。

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，即WPL的值最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

基本概念：

  • 节点之间的路径长度：从一个节点到另一个节点之间的分支数目。如图，从根节点到节点c之间的长度为3

  • 树的路径长度：从树的根到树的每一个节点的路径长度之和

  • 节点的权：给每一个结点赋予一个新的数值，被称之为这个节点的权。例如，节点a的权为7，节点b的权为5.

  • 节点的带权路径长度：从该节点到树根之间的路径长度与节点上权的乘积。例如，节点b的带权路径长度为2*5=10

  • 树的带权路径长度(WPL)：树中所有叶子节点带权路径长度之和。如图所示的这棵树的带权路径长度为：WPL=17+25+32+34

img

构建哈夫曼树

对于给定的有各自权值的n个节点，构建哈夫曼树的方法：

  1. 在n个权值中挑选出两个最小的权值，对应的两个节点组成一个新的二叉树，且新二叉树的根节点的权值为左右孩子权值的和。对应图A到B
  2. 在原有的n个权值中删除那两个最小的权值，同时新的权值加入到n-2个权值的行列中，以此类推。对应图B到C，即cd删掉了，添加了新的权值——6
  3. 重复1和2，直到所有节点构成了一颗二叉树为止，这棵树就是最有二叉树，即哈夫曼树。对应图C到D

img

节点结构

从上面的示例我们可以知道，哈夫曼树是从下向上构建的。需要每次根据各个节点的权重值，筛选出其权值最小的两个节点，然后构建二叉树。

查找权值最小的两个节点思想和最基础的三个数比大小思想差不多，先找俩节点，假设它们俩是最小的，然后如果找到更小的就删掉稍大的，直到遍历完成即可。

示例Demo

//
// Created by hash070 on 2022/5/10.
//
#include<bits/stdc++.h>

using namespace std;
struct tree {
    int data;
    struct tree *left;
    struct tree *right;
    string str;
};
typedef struct tree *link;
vector<link> root;

void update(link &t, string s) {
    link t1 = t;
    if (t1 != nullptr) {
        t1->str.insert(0, s);
        update(t->left, s);
        update(t->right, s);
    }
}

void preorderPrint(link t) {
    link t1 = t;
    if (t1 != nullptr) {
        if (t1->data != 0) {
            cout << t1->data << "的编码是：" << t1->str << endl;
        }
        preorderPrint(t1->left);
        preorderPrint(t1->right);
    }
}

void gen(vector<link> &root, vector<int> worth) {
    while (worth.size() >= 2) {
        int mid = worth[worth.size() - 1] + worth[worth.size() - 2];
        link t = new tree;
        t->data = 0;
        t->left = root[root.size() - 1];
        update(t->left, "0");
        t->right = root[root.size() - 2];
        update(t->right, "1");
        worth.erase(worth.end() - 2, worth.end());
        root.erase(root.end() - 2, root.end());
        for (int i = 0; i < worth.size(); i++) {
            if (worth[i] <= mid) {
                worth.insert(worth.begin() + i, mid);
                root.insert(root.begin() + i, t);
                break;
            } else if (i == (worth.size() - 1)) {
                worth.push_back(mid);
                root.push_back(t);
                break;
            }
        }
        if (worth.size() == 0) {
            worth.push_back(mid);
            root.push_back(t);
        }
    }
    preorderPrint(root[0]);
}

int main() {
    cout << "请输入节点的个数" << endl;
    int n = 0, tmp;
    cin >> n;
    vector<int> val;
    cout << "请输入各节点的权值" << endl;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        val.push_back(tmp);
    }
    if (n == 1) {
        cout << val[0] << "的编码是：" << 0 << endl;
        return 0;
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++)
            if (val[i] < val[j]) {
                tmp = val[i];
                val[i] = val[j];
                val[j] = tmp;
            }
    }
    //For now val中的value是从大到小排列的
    //vector<link> root;
    for (int i = 0; i < n; i++) {
        link r = new tree;
        r->data = val[i];
        r->left = nullptr;
        r->right = nullptr;
        root.push_back(r);
    }//创建一个初始的指针向量tree
    gen(root, val);//生成并打印哈夫曼树编码
}