6.1 哈夫曼树

• 带权路径长度的概念

  • 结点的权：

    有某种现实含义的数值（如：表示结点的重要性等）

  • 结点的带权路径长度：

    从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积。

    $结点的带权路径长度=从根到该节点的路径长度\times 该结点上权值的乘积$

  • 树的带权路径长度：

    树中所有叶结点的带权路径长度之和。如：

    

• 哈夫曼树定义

  给定n个带权叶结点，要构造出二叉树，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称为最优二叉树。

• 哈夫曼树的构造

  给定n个权值分别为$w_1,w_2,...,w_n$的结点，构造哈夫曼树的算法描述如下：

  （1）将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F；

  （2）构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左右子树，并且将新结点的权值置为左右子树上根结点的权值之和；

  （3）从F中删除刚才选出的两棵树，同时将新得到的树加入F中。

  （4）重复第2和第3步，直至F中只剩下一棵树为止。

  

• 哈夫曼树的性质

  1.每个初始结点最终都会成为叶结点，且权值越小的结点到根结点的路径长度越大；

  2.哈夫曼树的结点总数为2n-1；

  3.哈夫曼树中不存在度为1的结点；

  4.哈夫曼树不唯一，但WPL必然相同且最优。

• 哈夫曼编码的定义

  • 固定长度编码：每个字符用相等长度的二进制位表示。
  • 可变长度编码：允许对不同字符用不等长的二进制位表示。
  • 前缀编码：没有一个编码是另一个编码的前缀。
  • 由哈夫曼树得到哈夫曼编码——将字符频次作为字符结点权值，构造哈夫曼树，即可得哈夫曼编码，可用于数据压缩。

*完整代码 哈夫曼树

#include <stdio.h>
#include <stdlib.h>

// 定义哈夫曼树节点结构
typedef struct HuffmanNode {
    char data;              // 字符
    int freq;               // 频率
    struct HuffmanNode *left, *right;   // 左右子节点
} HuffmanNode;

// 定义优先级队列结构
typedef struct PriorityQueue {
    int size;               // 队列当前大小
    int capacity;           // 队列容量
    HuffmanNode **array;    // 存储哈夫曼树节点的数组指针
} PriorityQueue;

// 创建哈夫曼树节点
HuffmanNode* createNode(char data, int freq) {
    HuffmanNode* node = (HuffmanNode*)malloc(sizeof(HuffmanNode));  // 分配内存空间
    node->data = data;  // 设置节点字符
    node->freq = freq;  // 设置节点频率
    node->left = node->right = NULL;   // 初始化左右子节点为空
    return node;  // 返回节点指针
}

// 创建优先级队列
PriorityQueue* createPriorityQueue(int capacity) {
    PriorityQueue* queue = (PriorityQueue*)malloc(sizeof(PriorityQueue));  // 分配内存空间
    queue->size = 0;  // 初始化队列大小为0
    queue->capacity = capacity;  // 设置队列容量
    queue->array = (HuffmanNode**)malloc(queue->capacity * sizeof(HuffmanNode*));  // 分配内存空间
    return queue;  // 返回队列指针
}

// 交换两个节点
void swapNodes(HuffmanNode** a, HuffmanNode** b) {
    HuffmanNode* temp = *a;
    *a = *b;
    *b = temp;
}

// 向下堆化
void minHeapify(PriorityQueue* queue, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;  // 计算左子节点索引
    int right = 2 * idx + 2;  // 计算右子节点索引

    // 找出三个节点中最小的节点
    if (left < queue->size && queue->array[left]->freq < queue->array[smallest]->freq) {
        smallest = left;
    }
    if (right < queue->size && queue->array[right]->freq < queue->array[smallest]->freq) {
        smallest = right;
    }

    // 如果最小节点不是当前节点，交换节点并递归向下堆化
    if (smallest != idx) {
        swapNodes(&queue->array[idx], &queue->array[smallest]);
        minHeapify(queue, smallest);
    }
}

// 插入节点
void insertNode(PriorityQueue* queue, HuffmanNode* node) {
    queue->size++;  // 队列大小加1
    int i = queue->size - 1;  // 获取最后一个位置的索引

    queue->array[i] = node;  // 将节点插入最后一个位置

    // 如果插入节点的频率小于父节点的频率，向上调整
    while (i && queue->array[i]->freq < queue->array[(i - 1) / 2]->freq) {
        swapNodes(&queue->array[i], &queue->array[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

// 提取最小节点
HuffmanNode* extractMin(PriorityQueue* queue) {
    if (queue->size == 0) return NULL;  // 如果队列为空，返回空指针

    HuffmanNode* root = queue->array[0];  // 获取根节点
    queue->array[0] = queue->array[queue->size - 1];  // 将最后一个节点移到根节点位置
    queue->size--;  // 队列大小减1

    minHeapify(queue, 0);  // 向下堆化

    return root;  // 返回根节点
}

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(char data[], int freq[], int size) {
    PriorityQueue* queue = createPriorityQueue(size);  // 创建优先级队列

    // 将字符和频率构建成哈夫曼树节点，并插入优先级队列中
    for (int i = 0; i < size; i++) {
        insertNode(queue, createNode(data[i], freq[i]));
    }

    // 从优先级队列中不断取出最小的两个节点，构建哈夫曼树，直到队列中只剩一个节点
    while (queue->size != 1) {
        HuffmanNode* left = extractMin(queue);
        HuffmanNode* right = extractMin(queue);

        // 创建新节点作为父节点，频率为左右子节点频率之和
        HuffmanNode* top = createNode('\0', left->freq + right->freq);
        top->left = left;
        top->right = right;

        // 插入新节点到队列中
        insertNode(queue, top);
    }

    // 返回根节点
    return extractMin(queue);
}

// 打印哈夫曼编码
void printHuffmanCodes(HuffmanNode* root, int arr[], int top) {
    // 遍历树，生成编码
    if (root->left) {
        arr[top] = 0;
        printHuffmanCodes(root->left, arr, top + 1);
    }

    if (root->right) {
        arr[top] = 1;
        printHuffmanCodes(root->right, arr, top + 1);
    }

    // 当遍历到叶子节点时，打印字符及其编码
    if (!root->left && !root->right) {
        printf("%c: ", root->data);
        for (int i = 0; i < top; i++) {
            printf("%d", arr[i]);
        }
        printf("\n");
    }
}

// 主函数
int main() {
    char data[] = { 'a', 'b', 'c', 'd', 'e', 'f' };  // 字符集合
    int freq[] = { 5, 9, 12, 13, 16, 45 };           // 字符频率
    int size = sizeof(data) / sizeof(data[0]);       // 字符集合大小

    // 构建哈夫曼树
    HuffmanNode* root = buildHuffmanTree(data, freq, size);

    int arr[100];  // 存储编码的数组
    int top = 0;   // 记录编码
    // 打印哈夫曼编码
    printf("哈夫曼编码:\n");
    printHuffmanCodes(root, arr, top);

    return 0;
}