【数据结构】——哈夫曼树

速通回忆

这里是完整的代码和运行结果，可以直接选择看下面代码的思路去快速回忆哈夫曼树，或从下面理论部分开始学习

#include "stdio.h"
#include "stdlib.h"

/* 哈夫曼树结点的结构体 */
typedef struct {
    int weight; /* 权重 */
    int parent; /* 父母结点下标 */
    int lchild; /* 左孩子结点下标 */
    int rchild; /* 右孩子结点下标 */
} node;

/* 树结构体 */
typedef struct {
    node *htnode;
    int length;
} HFTree;

/* 哈夫曼树初始化 */
HFTree *Init_HuffmanTree(int *num, int num_length) {
    /* 分配动态内存 */
    HFTree *tree_temp = (HFTree *)malloc(sizeof(HFTree));
    tree_temp->htnode = (node *)malloc(sizeof(node) * (2 * num_length - 1));
    tree_temp->length = num_length;

    /* 初始化每个结点结构体的内容 */
    for (int i = 0; i < 2 * num_length - 1; i++) {
        if (i < num_length) {
            tree_temp->htnode[i].weight = num[i];
        } else {
            tree_temp->htnode[i].weight = 0;
        }
        tree_temp->htnode[i].parent = -1;
        tree_temp->htnode[i].lchild = -1;
        tree_temp->htnode[i].rchild = -1;
    }
    return tree_temp;
}

/* 哈夫曼树提取最小的两位数 */
void GetMinSecond(HFTree *hftree, int *min1, int *min2) {
    *min1 = -1;
    *min2 = -1;

    /* 找到两个最小的节点 */
    for (int i = 0; i < hftree->length; i++) {
        if (hftree->htnode[i].parent != -1) continue; // 跳过已经有父节点的节点

        if (*min1 == -1 || hftree->htnode[i].weight < hftree->htnode[*min1].weight) {
            *min2 = *min1;
            *min1 = i;
        } else if (*min2 == -1 || hftree->htnode[i].weight < hftree->htnode[*min2].weight) {
            *min2 = i;
        }
    }
}

/* 构建哈夫曼树 */
void Create_HFTree(HFTree *hftree) {
    int tree_length = 2 * hftree->length - 1;
    int min1, min2;

    /* 填充父母结点 */
    for (int i = hftree->length; i < tree_length; i++) {
        GetMinSecond(hftree, &min1, &min2);

        /* 父母结点的值为左右孩子结点的权重和 */
        hftree->htnode[i].weight = hftree->htnode[min1].weight + hftree->htnode[min2].weight;
        hftree->htnode[i].lchild = min1;
        hftree->htnode[i].rchild = min2;

        /* 左右孩子的父母结点都为i */
        hftree->htnode[min1].parent = i;
        hftree->htnode[min2].parent = i;

        /* 更新树的长度 */
        hftree->length++;
    }
}

/* 遍历 */
void Show_HFTree(HFTree *hftree, int index) {
    if (index != -1) {
        printf("%d  ", hftree->htnode[index].weight);
        Show_HFTree(hftree, hftree->htnode[index].lchild);
        Show_HFTree(hftree, hftree->htnode[index].rchild);
    }
}

int main() {
    int num_temp[5] = {1, 2, 3, 4, 5};
    HFTree *hftree = Init_HuffmanTree(num_temp, 5);

    Create_HFTree(hftree);
    printf("哈夫曼树的节点权重（前序遍历）：\n");
    Show_HFTree(hftree, hftree->length - 1); // 从根节点开始遍历
    printf("\n");
    return 0;
}

认识哈夫曼树

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

• 路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径

• 路径长度：在一条路径中，每经过一个结点，路径长度都要加 1

• 结点的权：给每一个结点赋予一个新的数值

• 结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积

• 树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL”

构建哈夫曼树（理论）

构建过程中，只需要遵循一个原则，那就是权重越大的结点距离树根越近

首先，选出我们数据中最小的两个数据，构建成二叉树的左孩子和右孩子，而根的数据为两者之和

其次，将刚才合成的数据作为孩子结点，其兄弟结点从未处理的数据中选出最小的一个，与当前合成结点比较，他们的根同样为左右孩子的权值和

这颗哈夫曼树的WPL值为：7*2 + 6*2 + 9 * 2 + 3 * 3 + 2 * 3

哈夫曼树的结点结构

//哈夫曼树结点结构
typedef struct {
    int weight; //结点权重
    int parent, left, right;    //父结点、左孩子、右孩子在数组中的位置下标
} HTNode, *HuffmanTree;

构建哈夫曼树

//HT为地址传递的存储哈夫曼树的数组，w为存储结点权重值的数组，n为结点个数
void CreateHuffmanTree(HuffmanTree *HT, int *w, int n) {
    if(n <= 1)
        return; // 如果只有一个编码就相当于0
    int m = 2*n-1; // 哈夫曼树总节点数，n就是叶子结点
    *HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号位置不用
    HuffmanTree p = *HT;
// 初始化哈夫曼树中的所有结点
    for(int i = 1; i <= n; i++) {
        (p+i)->weight = *(w+i-1);
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
    }
//从树组的下标 n+1 开始初始化哈夫曼树中除叶子结点外的结点
    for(int i = n+1; i <= m; i++) {
        (p+i)->weight = 0;
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
    }
//构建哈夫曼树
    for(int i = n+1; i <= m; i++) {
        int s1, s2;
        Select(*HT, i-1, &s1, &s2);    //查找内容，需要用到查找算法
        (*HT)[s1].parent = (*HT)[s2].parent = i;
        (*HT)[i].left = s1;
        (*HT)[i].right = s2;
        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
    }
}

哈夫曼树查找算法

//HT数组中存放的哈夫曼树，end表示HT数组中存放结点的最终位置，s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置
void Select(HuffmanTree HT, int end, int *s1, int *s2) {
    int min1, min2;
//遍历数组初始下标为 1
    int i = 1;
//找到还没构建树的结点
    while(HT[i].parent != 0 && i <= end) {
        i++;
    }
    min1 = HT[i].weight;
    *s1 = i;
    i++;
    while(HT[i].parent != 0 && i <= end) {
        i++;
    }
//对找到的两个结点比较大小，min2为大的，min1为小的
    if(HT[i].weight < min1) {
        min2 = min1;
        *s2 = *s1;
        min1 = HT[i].weight;
        *s1 = i;
    } else {
        min2 = HT[i].weight;
        *s2 = i;
    }
//两个结点和后续的所有未构建成树的结点做比较
    for(int j=i+1; j <= end; j++) {
//如果有父结点，直接跳过，进行下一个
        if(HT[j].parent != 0) {
            continue;
        }
//如果比最小的还小，将min2=min1，min1赋值新的结点的下标
        if(HT[j].weight < min1) {
            min2 = min1;
            min1 = HT[j].weight;
            *s2 = *s1;
            *s1 = j;
        }
//如果介于两者之间，min2赋值为新的结点的位置下标
        else if(HT[j].weight >= min1 && HT[j].weight < min2) {
            min2 = HT[j].weight;
            *s2 = j;
        }
    }
}