[C、C++]数据结构：哈夫曼树 & 字母表的哈夫曼编码_哈夫曼数加权构建,打印字符并编码

欢迎关注本人b站账号：Dr_四倍体果蝇

UID:12595237

一、哈夫曼树の重要概念

结点的权、结点的带权路径长度，树的带权路径长度。

哈夫曼树（最优二叉树）：含有某n个叶子结点的，带权路径长度最低的二叉树。

哈夫曼树不唯一。

二、哈夫曼树の构造

1.每次选择2个权值最低的结点（树）作为兄弟，形成新的树，根节点为两结点权值之和

2.新树加入树的集合

3.重复前两步直到剩下一棵树

一共结合n-1次。

哈夫曼树的结点数为n-1。

三、哈夫曼编码

往往结点的权重用其data的出现频率代替，为了让传递的二进制信息尽可能小。

例：根据ABCD的频率得到编码方案

左侧是固定长度编码，右侧是可变长度编码。

前缀编码：不存在某个元素的编码是另一个元素的前缀的情况。

非前缀编码：存在~

哈夫曼编码得到的一定是前缀编码。每一个元素作为叶子结点，把频度作为权值。一般左指针看成0，右指针看成1。

四、哈夫曼编码实现26字母表编码

已经将所有整理的思路放在了注释里。

#include <stdio.h>
#include <stdlib.h>
 
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0]) // 数组的大小:数组的总字节数/数组的第一个元素的字节数
#define MAX_TREE_HT 100 // 哈夫曼树的编码数组的最大长度
 
// MinHeapNode 结构体定义
struct MinHeapNode {
    char data;
    int freq;
    struct MinHeapNode* left, * right;
};
// MinHeapNode是最小堆的节点，包含字符数据和频率，以及左右子节点的指针
// 左右子节点指针为空的结点就是叶子结点，左右子节点指针不为空的结点就是内部结点
// 最小堆结点就是哈夫曼树的结点，哈夫曼树的叶子结点就是字符，哈夫曼树的非叶子结点就是内部结点
 
// MinHeap 结构体定义
struct MinHeap {
    int size;
    int capacity;
    struct MinHeapNode** array;
};
// MinHeap是最小堆，包含堆的大小，容量，以及节点指针数组
// 最小堆就是哈夫曼树的结点数组，哈夫曼树的叶子结点就是字符，哈夫曼树的非叶子结点就是内部结点
// 用二级指针是因为MinHeapNode之间互相以left,right指针连接，而最小栈MinHeap的array指针只负责指向堆的结点，
// 在最小栈弹出元素时，不影响结点之间的相互连接   
 
// 创建并初始化一个新的 MinHeapNode
struct MinHeapNode* newNode(char data, int freq) {
    struct MinHeapNode* node = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));
    node->data = data;
    node->freq = freq;
    node->left = node->right = NULL; // 叶子结点的左右子节点指针为空，用作判断是否是叶子结点的标准
    return node;
}
 
// 创建并初始化一个新的 MinHeap
struct MinHeap* createMinHeap(int capacity) {
    struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap)); // 给最小堆分配内存
    minHeap->size = 0;
    minHeap->capacity = capacity; // 堆的容量就是哈夫曼树的结点个数
    minHeap->array = (struct MinHeapNode**)malloc(capacity * sizeof(struct MinHeapNode*)); // 给堆的结点指针数组分配内存
    return minHeap;
}
 
// 交换两个 MinHeapNode 指针
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) {
    struct MinHeapNode* t = *a;
    *a = *b;
    *b = t;
}
// 交换指针会交换指针指向的内容，也就是交换指向的最小堆结点（因为指针就是地址，交换指针就是交换地址，交换地址就是交换指针指向的内容）
// 因为最小堆结点指针数组的元素是指向最小堆结点的指针，所以交换指针就是交换指针指向的最小堆结点
 
// 最小堆调整
void minHeapify(struct MinHeap* minHeap, int idx) {
    int smallest = idx; // 初始化最小值为根结点
    int left = 2 * idx + 1; // 左子节点
    int right = 2 * idx + 2; // 右子节点
 
    if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)
        smallest = left; // 如果左子节点的频率小于根结点的频率，那么最小值就是左子节点
    if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)
        smallest = right; // 如果右子节点的频率小于最小值，那么最小值就是右子节点
    if (smallest != idx) {
        swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]); // 如果最小值不是根结点，那么交换最小值和根结点
        minHeapify(minHeap, smallest); // 递归调整，直到最小值是根结点
    }
}
// 这个函数的作用是调整最小堆，使得最小堆的根结点是最小值,也就是哈夫曼树的根结点是最小频率的结点,其他结点的顺序不变
 
// 检查 MinHeap 的大小是否为1
int checkSizeOne(struct MinHeap* minHeap) {
    return (minHeap->size == 1);
}
// 这个函数的作用是检查最小堆的大小是否为1，如果是1，那么最小堆就是哈夫曼树
// 这个结点就是哈夫曼树的根结点，也就是最小频率的结点
 
// 从最小堆中提取最小值节点
struct MinHeapNode* extractMin(struct MinHeap* minHeap) {
    struct MinHeapNode* temp = minHeap->array[0]; // 最小值就是根结点，minHeap->array[0]是根结点
    minHeap->array[0] = minHeap->array[minHeap->size - 1]; // 把最后一个结点放到根结点
    --minHeap->size; // 最小堆的大小减1
    minHeapify(minHeap, 0); // 调整最小堆
    return temp; // 返回最小值节点
}
// 这个函数的作用是从最小堆中提取最小值节点，也就是从哈夫曼树中提取最小值节点，也就是从哈夫曼树中提取最小频率的节点
 
// 插入新节点到最小堆
void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) {
    ++minHeap->size; // 最小堆的大小加1
    int i = minHeap->size - 1; // 最后一个结点的下标是size-1
    while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {
        minHeap->array[i] = minHeap->array[(i - 1) / 2]; // 把父节点放到新节点的位置
        i = (i - 1) / 2; // 新节点的位置变成父节点的位置
    } // 如果新节点的频率小于父节点的频率，那么就把父节点放到新节点的位置，然后新节点的位置变成父节点的位置，直到新节点的频率大于父节点的频率
    minHeap->array[i] = minHeapNode; // 把新节点放到新节点的位置
}
 
// 构建最小堆
void buildMinHeap(struct MinHeap* minHeap) {
    int n = minHeap->size - 1; // 最后一个结点的下标是size-1
    int i;
    for (i = (n - 1) / 2; i >= 0; --i) // 从最后一个结点的父节点开始，直到根结点
        minHeapify(minHeap, i); // 调整最小堆
}
// 这个函数和minHeapify()函数的区别是，这个函数是从最后一个结点的父节点开始，调用minHeapify(),直到根结点，调整最小堆
 
// 判断是否是叶子结点
int isLeaf(struct MinHeapNode* root) {
    return !(root->left) && !(root->right); // 如果左右子节点指针都为空，那么就是叶子结点
}
 
// 打印哈夫曼树的编码
void printCodes(struct MinHeapNode* root, int arr[], int top) {
    if (root->left) { // 如果左子节点指针不为空
        arr[top] = 0; // 编码是0
        printCodes(root->left, arr, top + 1); // 递归打印左子树的编码，每次递归把编码数组的下标加1，也就是编码的位数加1
    }
    if (root->right) { // 如果右子节点指针不为空
        arr[top] = 1; // 编码是1
        printCodes(root->right, arr, top + 1); // 递归打印右子树的编码，每次递归把编码数组的下标加1，也就是编码的位数加1
    }
    if (isLeaf(root)) { // 如果是叶子结点
        printf("%c: ", root->data);
        int i;
        for (i = 0; i < top; ++i) // 对于编码数组的每一位，打印
            printf("%d", arr[i]);
        printf("\n");
    }
}
 
// 构建哈夫曼树
struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) {
    struct MinHeap* minHeap = createMinHeap(size); // 创建最小堆
    int i;
    for (i = 0; i < size; ++i)
        minHeap->array[i] = newNode(data[i], freq[i]); // 把哈夫曼树的结点放到最小堆的结点指针数组中
    minHeap->size = size; // 最小堆的大小是哈夫曼树的结点个数
    buildMinHeap(minHeap); // 构建最小堆
 
    // 最小堆的大小不是1，就继续把最小堆的最小值节点提取出来，然后把最小值节点的左右子节点放到最小堆中，直到最小堆的大小是1
    while (!checkSizeOne(minHeap)) { // 如果最小堆的大小不是1，那么就继续
        struct MinHeapNode* left = extractMin(minHeap); // 从最小堆中提取最小值节点，也就是从哈夫曼树中提取最小值节点
        struct MinHeapNode* right = extractMin(minHeap); // 从最小堆中提取最小值节点，也就是从哈夫曼树中提取最小值节点
 
        struct MinHeapNode* top = newNode('$', left->freq + right->freq); // 新建一个哈夫曼树的结点，字符是$，频率是左右子节点的频率之和
        top->left = left; // 左子节点是最小值节点
        top->right = right; // 右子节点是最小值节点
        insertMinHeap(minHeap, top); // 把新节点插入到最小堆
    }
    return extractMin(minHeap); // 从最小堆中提取最小值节点，也就是从哈夫曼树中提取最小值节点，也就是哈夫曼树的根结点
}
//在调用`buildHuffmanTree`函数时，虽然最后最小堆中只剩下一个节点，但这个节点实际上是哈夫曼树的根节点，
//它包含了整个哈夫曼树的所有信息。在构建哈夫曼树的过程中，我们不断地从最小堆中取出两个频率最小的节点，
//然后创建一个新的内部节点，这个内部节点的左右子节点就是这两个取出的节点。
//这样，新的内部节点就包含了它的左右子节点的所有信息。当最小堆中只剩下一个节点时，
//这个节点就是包含了所有字符和频率信息的哈夫曼树的根节点。
//因此，当我们调用`printCodes(root, arr_huff, top); `函数时，虽然传入的是哈夫曼树的根节点，
// 但通过遍历这个根节点，我们可以访问到哈夫曼树中的所有节点，从而打印出所有字符的哈夫曼编码。
// 具体来说，`printCodes`函数会递归地访问每一个节点的左右子节点，直到访问到叶子节点（即字符），
// 然后打印出从根节点到叶子节点的路径，这个路径就是字符的哈夫曼编码。
// 所以虽然看起来只有一个节点，但实际上这个节点包含了整棵哈夫曼树的所有信息。
 
int main() {
    char arr[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
                  'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
    int freq[] = { 819, 147, 383, 391, 1225, 226, 171, 457, 710, 14,
                  41, 377, 334, 706, 726, 289, 9, 685, 636, 941,
                  258, 109, 159, 21, 158, 8 };
    int size = ARRAY_SIZE(arr); // 哈夫曼树的结点个数
    struct MinHeapNode* root = buildHuffmanTree(arr, freq, size); // 构建哈夫曼树
    int arr_huff[MAX_TREE_HT], top = 0; // arr_huff是编码数组，top是编码数组的下标,MAX_TREE_HT是编码数组的最大长度
    printCodes(root, arr_huff, top); // 打印哈夫曼树的编码
    return 0;
}