最优二叉树—哈夫曼(huffman)树

哈夫曼树又称最优二叉树，是一类带权路径长度最短的二叉树，有着广泛的应用。

基本概念

权：将树中的结点赋上一个有着某种意义的数值

路径：从A结点道B结点所经过的分支序列

路径长度：从A结点道B结点所经过的分支数目

查找效率

平均查找长度(ASL)取决于树的高度

ASL=(1+2*2+3)/4=2            ASL=(1+2+3+4)/4=2.5

        O(log₂n)                               O(n)     

          二叉树                               单链表 

带权路径长度  

路径长度：路径上所经历边的个数

结点的权：结点被赋予的数值

树的带权路径长度    WPL树中所有叶结点的带权路径长度之和，记为

WPL=7*2+2*2+3*3=24                              WPL=7*1+2*2+3*2=17

哈夫曼树   也称最优二叉树，含有n个带权叶子节点带权路径长度最小的二叉树

带权路径长度：树的根节点A结点的路径长度与A结点上的权的乘积

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

树的带权路径长度：树中所有叶子节点的带权路径长度之和

WPL=2*2+2*4+2*5+2*8=38

WPL=4*2+5*3+8*3+2*1=49

WPL=8*1+5*2+4*3+2*3=36

哈夫曼树的构造算法

• 将n个结点作为n棵仅含有一个根结点的二叉树，构成森林F
• 生成一个新结点，井从F中找出根结点权值最小的两棵树作为它的左右子树，且新结点的权值为两棵子树根结点的权值之和
• 从F中删除这两个树，并将新生成的树加入到F中
• 重复2,3步骤，直到F中只有一棵树为止

哈夫曼树的性质

• 每个初始结点都会成为叶节点，双支结点都为新生成的结点
• 权值越大离根结点越近，反之权值越小离根结点越远
• 哈夫曼树中没有结点的度为1
• n个叶子结点的哈夫曼树的结点总数为2n-1，其中度为2的结点数为n-1

构造哈夫曼树的方法

哈夫曼树的形态不是唯一的，第二步中的左右子树位置并不一定是小在左大在右，但具有一组权值的哈夫曼树的WPL是唯一的

哈夫曼树的构造算法:

编码  对于一个字符串的序列，用二进制来表示字符

哈夫曼编码

构造一个哈夫曼树

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

#define MAX_N 1000

typedef struct _huff_node {
    int weight;
    int parent, lchild, rchild;
} HuffNode;

void huffman_tree(int n, int *weight, HuffNode *huff) {
    // 初始化哈夫曼树的n个叶子结点
    for (int i = 0; i < n; i++) {
        huff[i].weight = weight[i];
        huff[i].parent = -1;
        huff[i].lchild = -1;
        huff[i].rchild = -1;
    }

    // 构造哈夫曼树
    for (int i = n; i < 2 * n - 1; i++) {
        int min1 = -1, min2 = -1;
        for (int j = 0; j < i; j++) {
            if (huff[j].parent == -1) {
                if (min1 == -1 || huff[j].weight < huff[min1].weight) {
                    min2 = min1;
                    min1 = j;
                } else if (min2 == -1 || huff[j].weight < huff[min2].weight) {
                    min2 = j;
                }
            }
        }
        huff[min1].parent = i;
        huff[min2].parent = i;
        huff[i].lchild = min1;
        huff[i].rchild = min2;
        huff[i].weight = huff[min1].weight + huff[min2].weight;
    }
}

int main() {
    int n, weight[MAX_N];
    HuffNode huff[MAX_N * 2 - 1];

    // 读入叶子结点个数和权值数组
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &weight[i]);
    }

    // 构造哈夫曼树
    huffman_tree(n, weight, huff);

    // 输出哈夫曼树的结构
    for (int i = 0; i < 2 * n - 1; i++) {
        printf("Node %d: weight=%d, parent=%d, lchild=%d, rchild=%d\n",
                i, huff[i].weight, huff[i].parent, huff[i].lchild, huff[i].rchild);
    }

    return 0;
}

这个代码读入叶子结点个数和权值数组，然后构造哈夫曼树，并输出每个节点的权值、父节点、左子节点和右子节点。

代码解释：

1. #include <stdio.h> 和 #include <stdlib.h> 分别引入了标准输入输出库和标准库的头文件。
2. #define MAX_N 1000 定义了一个宏，表示叶子结点的最大数量。
3. typedef struct _huff_node {...} HuffNode; 定义了一个名为HuffNode的结构体，表示哈夫曼树中的节点。结构体包含了权值（weight）、父节点（parent）、左子节点（lchild）和右子节点（rchild）等字段。
4. void huffman_tree(int n, int *weight, HuffNode *huff) {...} 是构造哈夫曼树的函数。参数包括叶子结点个数n、权值数组weight[]和存储哈夫曼树的数组huff[]。
5. for (int i = 0; i < n; i++) {...} 初始化哈夫曼树的n个叶子结点。遍历每个叶子结点，设置其权值为weight[i]，并将父节点、左子节点和右子节点初始化为-1。
6. for (int i = n; i < 2 * n - 1; i++) {...} 构造哈夫曼树的非叶子结点。从第n个位置开始，遍历每个非叶子结点，选择权值最小的两个节点作为其左右子节点，并更新相关字段。
7. int main() {...} 是主函数。在主函数中，首先声明了叶子结点个数n和权值数组weight[MAX_N]，以及存储哈夫曼树的数组huff[MAX_N * 2 - 1]。
8. scanf("%d", &n); 读入叶子结点的个数n。
9. for (int i = 0; i < n; i++) {...} 通过循环读入叶子结点的权值数组weight[]。
10. huffman_tree(n, weight, huff); 调用huffman_tree函数构造哈夫曼树。
11. for (int i = 0; i < 2 * n - 1; i++) {...} 遍历哈夫曼树的所有结点，并输出每个结点的权值、父节点、左子节点和右子节点的信息。
12. return 0; 表示程序正常结束。

总体来说，通过构造函数的方式实现了构造哈夫曼树的功能，并提供了一个简单的演示程序来展示结果。使用了结构体来存储每个节点的信息，并通过循环来遍历和处理每个节点，最终输出了哈夫曼树的结构信息。