构建haffman 树以及代码实现

因为最近在做一个微课，讲的是哈夫曼树，就分享下学习经历。

haffman树又称最优二叉树，是带权路径长度(WPL)最短的二叉树。

如下图所示，ABCD四个字母其自身所带的权值分别为7 5 2 4。那么这棵二叉树的WPL值就等于

           WPL=     2x7+2x5+2x2+2x4=36

同时这个二叉树还有另外两种构建方法。 

  ​​​​ WPL = 46                     WPL = 35

haffman树就是由n个带权叶子结点构成的所有二叉树中带权路径长度WPL最短的二叉树。

haffuman树的创建需要给定n个权值对应的n个结点。

结点：可以为1234，或者学生不同成绩的ABCD等级划分。

字符权值：结点赋予一个具有某种实际意义的实数。比如学生成绩不同等级的人数，类似于一种比重。

创建步骤为：

1、 用给定的n个权值{w1, w2，... , wn}对应的n个结点构成n棵二叉树的森林F={T1,T2，...,Tn},其中每一棵二叉树Ti(1≤i≤n)都只有一个权值为wi的根结点，其左、右子树为空。

2、在森林F中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、右子树，标记新二叉树的根结点权值为其左右子树的根结点权值之和。

3、从F中删除被选中的那两棵二叉树，同时把新构成的二叉树加入到森林F中。

4、重复2、3 *** 作，直到森林中只含有一棵二叉树为止，此时得到的这棵二叉树就是哈夫曼树。

上述步骤过于抽象，直接看例子。

例如一个字符串 deed in need

在这串字符串中 d出现了3次，e出现了4次，那么i，n就是1和2。这里我们先不算空格。

下面为创建步骤

1、通过字符串，设结点d，e，i，n。权值分别为3，4，1，2。

2、找出权值最小的两个结点。i和n，构建二叉树，此时二叉树F1的根结点权值为3。

                                                                此时拥有的二叉树为F1,F2,F3

 

 3、重复第2步骤

4、得到最后的唯一二叉树，也就是哈夫曼树。

 

 

 

 

哈夫曼树创建代码如下：

#include 
#include 
#include
using namespace std;
 
typedef struct {
    int weight;         // 结点权值
    int parent, Lchild, Rchild; // 双亲结点和左右子结点
} HTNode, *HuffmanTree;
 
void Select(HuffmanTree &HT, int n, int &s1, int &s2); //找出权值最小的两个 
 
void Create_HuffmanTree(HuffmanTree &HT, int *w, int n);//创建哈夫曼树 
 
void Create_HuffmanTree(HuffmanTree &HT, int *w, int n)
{
    int m, s1, s2;
    m = n * 2 - 1;  // 总结点的个数
    HT=(HTNode*)malloc((m+1)* sizeof(HTNode)); // 分配空间
    for(int i=1; i<=n; i++) // 1 - n 存放叶子结点，初始化
    {
        HT[i].weight = w[i];
        HT[i].parent = 0;
        HT[i].Lchild = 0;
        HT[i].Rchild = 0;
    }
    for(int i=n+1; i<=m; i++)   // 非叶子结点的初始化
    {
        HT[i].weight = 0;
        HT[i].parent = 0;
        HT[i].Lchild = 0;
        HT[i].Rchild = 0;
    }
    
    printf("\n哈夫曼树: \n");
 
    for(int i = n+1; i<=m; i++)     // 创建非叶子结点，构建哈夫曼树
    {   // 在HT[1]~HT[i-1]的范围内选择两个parent为0且weight最小的两个结点，其序号分别赋值给 s1 s2
        Select(HT, i-1, s1, s2);
        HT[s1].parent = i;  	// 删除这两个结点
        HT[s2].parent = i;
        HT[i].Lchild = s1;      // 生成新的树，左右子结点是 s1和s2
        HT[i].Rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;   // 新树的权值 
        printf("父：%d 左右：%d %d)\n", HT[i].weight, HT[s1].weight, HT[s2].weight);
    }
    printf("\n");
}
 
void Select(HuffmanTree &HT, int n, int &s1, int &s2)	//	寻找最小权值的两个结点 
{
    int minnum;      // 定义一个临时变量保存最小值
    for(int i=1; i<=n; i++)     // 以下是找到第一个最小值
    {
        if(HT[i].parent == 0)
        {
            minnum = i;
            break;
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(HT[i].parent == 0)
            if(HT[i].weight < HT[minnum].weight)
                minnum = i;
    }
    s1 = minnum;
    // 以下是找到第二个最小值，且与第一个不同
    for(int i=1; i<=n; i++)     
    {
        if(HT[i].parent == 0 && i != s1)
        {
            minnum = i;
            break;
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(HT[i].parent == 0 && i != s1)
            if(HT[i].weight < HT[minnum].weight)
                minnum = i;
    }
    s2 = minnum;
}

int main()
{
    HuffmanTree HT;
    
    int  n, q;	//n结点个数，q临时值 
    printf("输入叶子结点个数\n");
    scanf("%d", &n);
    int w[n+1];//权值 
    printf("\n输入 %d 个叶子结点的权值\n", n);
 
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &q);
        w[i] = q;
    }
    Create_HuffmanTree(HT, w, n);
 
 
 
    return 0;
}