数据结构之霍夫曼树_数据结构霍夫曼树

1.相关概念
霍夫曼树是所有与树有关的结构中最优美的，也叫做哈夫曼树。在学习霍夫曼树之前必须了解几个概念：

①路径：从树中的一个节点到另一个节点之间的分支结构通路
②路径长度：路径上的分支数目
③树的路径长度：从树根到每一个节点的路径长度之和
④节点的带权路径长度：从该节点开始到树根之间的路径长度与节点上的权重的乘积
⑤树的带权路径长度：是树中所有叶子结点的带权路径长度的和

所谓的霍夫曼树，假设有 n 个权值{a1,a2,…,an}，可以构造出一棵具有 n 个叶子节点的二叉树，每个叶子结点的权值为ni，则其中的带权路径长度最短的二叉树称作霍夫曼树，也叫最优二叉树。

2.构造霍夫曼树的过程
①：将 n 个给定的权值作为根节点创建n个树，{T1，T2,…,Tn}，即组成了一个森林
②：然后，从上面的森林中选择两棵权值最小的二叉树作为左右子节点合并成一个二叉树，新的二叉树的权值为两个子树的权值之和
③：剔除上面的两个子树，将新生成的二叉树加入森林中
④：重复②和③，直至森林中只有一棵二叉树为止

3.霍夫曼编码
以字符出现的频率为权构造霍夫曼树，在霍夫曼树中从根节点开始往左子树走记为0，往右子树走记为1，知道走到叶子结点，则得到的0，1 符号串即为该字符的霍夫曼编码

④.基本代码

#include <stdint.h>
#include <afxres.h>

typedef struct {
    int weight; //权值 
    int parent; //父结点序号 
    int left; //左子树序号
    int right; //右子树序号 
} HuffmanTree;

typedef char *HuffmanCode;  //Huffman编码 

void SelectNode(HuffmanTree *ht, int n, int *bt1, int *bt2)
//从1~x个结点选择parent结点为0,权重最小的两个结点 
{
    int i;
    HuffmanTree *ht1, *ht2, *t;
    ht1 = ht2 = NULL; //初始化两个结点为空
    for (i = 1; i <= n; ++i) //循环处理1~n个结点（包括叶结点和非叶结点）
    {
        if (!ht[i].parent) //父结点为空(结点的parent=0)
        {
            if (ht1 == NULL) //结点指针1为空
            {
                ht1 = ht + i; //指向第i个结点
                continue; //继续循环
            }
            if (ht2 == NULL) //结点指针2为空
            {
                ht2 = ht + i; //指向第i个结点
                
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