Penney's Blogs

言必行，行必果

0%

树结构_哈夫曼树

发表于 分类于 Valine：
本文字数： 887 阅读时长 ≈ 1 分钟

结构 HTNode - PtrToHTNode - HuffmanTree

  1. 权重
  2. 左哈夫曼树
  3. 右哈夫曼树

从最小堆构造哈夫曼树

  1. 假设H->Size个权值已经存在H->Elements[]->Weight里
  2. 将H->Elements[]按权值调整为最小堆
  3. 遍历所有元素
  4. 创建树结点,从小顶堆中最小值为左子树，再从堆取最小值为右子树
  5. 将左子树的权重加右子树的权重为根结点的权重
  6. 重新将新创建的根结点插入回小顶堆中

编码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdlib.h>
typedef struct HTNode *HuffmanTree;

struct HTNode {
    // 1.权重
    int Weight;
    // 2.左哈夫曼树
    HuffmanTree Left;
    // 3.右哈夫曼树
    HuffmanTree Right;
};

/**
 * 从最小堆构造哈夫曼树
 */
HuffmanTree HuffMan(MinHeap H) {
    // 1.假设H->Size个权值已经存在H->Elements[]->Weight里
    int i;
    HuffmanTree T;
    // 2.将H->Elements[]按权值调整为最小堆
    BuildMinHeap(H);
    // 3.遍历所有元素
    for (i = 1; i < H->Size; i++) {
        // 4.创建树结点,从小顶堆中最小值为左子树，再从堆取最小值为右子树
        T = malloc(sizeof(struct HTNode));
        T->Left = DeleteMin(H);
        T->Right = DeleteMin(H);
        // 5.将左子树的权重加右子树的权重为根结点的权重
        T->Weight = T->Left->Weight + T->Right->Weight;
        // 6.重新将新创建的根结点插入回小顶堆中
        Insert(H, T);
    }
    T = DeleteMin(H);
    return T;
}