数据结构--哈夫曼树与哈夫曼编码

填坑系列之哈夫曼树

刚开始看哈夫曼树时有点懵懵的，加权是啥子玩意，后面查阅资料后才明白，哈夫曼树以及哈夫曼编码多用在压缩编码中，再配合二倍速食用B站大学的网课，算是把整个算法过了一遍

the main structure

const int Max = 1000;
char **HuffmanCode;

typedef struct Node {
    int weight;
    int parent, left, right;
} HTNode, *HuffmanTree;

Select

select是来选择剩余结点中权值最小的两颗二叉树(包括新构造的树)的左右子树来构建一个新的二叉树，新根节点权值为其左右子树根节点的权值之和

void Select(HuffmanTree ht, int k, int& id1, int& id2) {
    long min1, min2;
    min1 = min2 = 99999; // 不能太小
    for (int i = 0;i < k;i++) {
        if (ht[i].parent == -1 && min1 > ht[i].weight) {
            // 选择无双亲的结点
            if (min1 < min2) { 
                // 这里是比大小的操作，规定min1为小
                min2 = min1;
                id2 = id1;
            }
            min1 = ht[i].weight; // 这个操作可以把这k个数据都遍历一遍，可以选出两个最小的结点
            id1 = i;
        } else if (ht[i].parent == -1 && min2 > ht[i].weight) {
            min2 = ht[i].weight;
            id2 = i;
        }
    }
}

Create a Huffman Tree

void HuffmanTree(huffTree &ht, int n) {
    int m = n * 2 - 1;
    int id1, id2;
    int i;
    if (n < 0) // 创建空树
        return;
    ht = new Node[m];
    for (i = 0;i < m;i++) {
        ht[i].parent = ht[i].left = ht[i].right = -1;
        // 初始化各节点
    }
    for (i = 0;i < n;i++) {
        cin >> ht[i].weight; // 输入各个结点的权值
    }
    for (i = n;i < m;i++) {
        Select(ht, i, id1, id2);
        // 在n个结点中选择俩无双亲的结点且权值最小的结点
        ht[id1].parent = ht[id2].parent = i;
        // 获得id1，id2，把第i个结点设为它俩的双亲
        ht[i].left = id1;
        ht[i].right = id2; // 设第i个结点的左右孩子为id1，id2
        ht[i].weight = ht[id1].weight + ht[id2].weight;
    }
}

destroy a Huffman Tree

void Destroy(HuffmanTree &ht) {
    delete[] ht;
    ht = NULL;
}

create the Huffman Code

void createHuffmanCode(HuffmanTree ht, HuffmanCode &hc, int n) {
    int start;
    int cur, f;
    hc = new char *[n + 1];
    char *cd = new char[n];
    cd[n - 1] = '\0';
    for (i = 0;i < n;i++) {
        start = n - 1; 
        cur = i; // 当前结点在数组中的位置
        f = hf[i].parent; // 当前结点的父节点在数组的位置
        while (f != 0) {
            // 如果该结点是父节点的左孩子则对应编码为0，否则右孩子为1
            start--;
            if (hf[f].left == cur)
                cd[start] = '0';
            else 
                cd[start] = '1';
            // 以父节点为孩子结点，继续朝树根的方向遍历
            cur = f;
            f = hf[f].parent;
        }
        // 跳出循环后，cd数组中从下标start开始，存放的就是该结点的哈夫曼编码
        hc[i] = new char[n - start];
        strcpy(hc[i], &cd[start]);
    }
    delete cd;
}

the code

#include <bits/stdc++.h>
using namespace std;
const int Max = 9999;
typedef char **HuffmanCode;
typedef struct Node {
    int weight;
    int parent, left, right;
} HTNode, *HuffmanTree;

void Select(HuffmanTree ht, int k, int id1, int id2) {
    int min1 = min2 = 9999;
	for (int i = 0;i < k;i++) {
        if (ht[i].parent == -1 && min1 < ht[i].weight) {
            if (min1 < min2) {
                min2 = min1;
                id2 = id1;
            }
            id1 = i;
            min1 = ht[i].weight;
        } else if (ht[i].parent == -1 && min2 > ht[i].weight) {
            min2 = ht[i].weight;
            id2 = i;
        }
    }
}

void createHuffmanTree(HuffmanTree ht, int n) {
    int id1, id2;
    if (n <= 0) 
        return;
    for (int i = 0; i < n; i++) {
        ht[i].left = ht[i].right = ht[i].parent = 0;
    }
    for (int i = 0;i < n;i++) {
        cin >> ht[i].weight;
    }
    for (int i = 0;i < n;i++) {
        Select(ht, i, id1, id2);
        ht[id1].parent = ht[id2].parent = i;
        ht[i].left = id1;
        ht[i].right = id2;
        ht[weight] = ht[id1].weight + ht[id2].weight;
    }
}

void createHuffmanTreeCode(HuffmanTree ht, HuffmanCode &hc, int n) {
    int start, cur f;
    hc = new char*[n + 1];
    char* cd = new char[n];
    cd[n - 1] = '\0';
    for (int i = 0;i < n;i++) {
        start = n - 1;
        cur = i;
        f = ht[i].parent;
        while (f != 0) {
            start--;
            if (ht[f].left == cur) {
                cd[start] = '0';
            } else {
                cd[start] = '1';
            }
            cur = f;
            f = ht[i].parent;
        }
        hc[i] = cd[n - start];
        strcpy(hc[i], &cd[start]);
    }
    delete cd;
}

int main() {
    int n;
    cin >> n;
    HuffmanTree ht;
    HuffmanCode hc;
    int sum = 0;
    HuffmanTree(ht, n);
    createHuffmanCode(ht, hc, n);
    for (int i = 0;i < 2 * n - 1;i++) {
        cout << ht[i].weight << ' '; // 测试，输出所有结点，包括非原有结点
    }
    cout << endl;
    for (int i = 0;i < n;i++) {
        cout << hc[i] << ' '; // 输出每个结点的HuffmanCode
    }
}

参考链接

数据结构：哈夫曼树与哈夫曼编码 - 乌漆WhiteMoon - 博客园 (cnblogs.com)

数据结构与算法基础--第09周04--5.7哈夫曼树及其应用4-5.7.2哈夫曼树的构造算法2-哈夫曼树算法实现_哔哩哔哩_bilibili(共6p)