原教材《数据结构教程》(第5版)李春葆 主编(武汉大学数据结构课程教材)

《算法笔记》那本书上并没有直接给出哈夫曼树的构造代码,特此记录一下。

核心代码:


typedef struct{
    char data;
    double weight;//权重
    int parent;
    int lchild;
    int rchild;
}HTNode;
void CreateHT(HTNode ht[],int no)//no个叶子结点
{
    int i,k,lnode,rnode;
    double min1,min2;
    for(i=0;i<2*no-1;i++)//no个叶子结点的哈夫曼树有2*no-1个结点,初始化
        ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
    for(i=no;i<=2*no-2;i++)//构造no-1个分支结点
    {
        min1=min2=32767;//设为较大的数
        lnode=rnode=-1;//lnode和rnode为最小权重的两个结点位置
        for(k=0;k<=i-1;k++)
        {
            if(ht[k].parent==-1)
            {
                if(ht[k].weight<minl)
                {
                    min2=min1;
                    rnode=lnode;
                    min1=ht[k].weight;
                    lnode=k;
                }
                else if(ht[k].weight<min2)
                {
                    min2=ht[k].weight;
                    rnode=k;
                }
            }
        }
        ht[i].weight=ht[lnode].weight+ht[rnode].weight;
        ht[i].lchild=lnode;
        ht[i].rchild=rnode;
        ht[lnode].parent=i;
        ht[rnode].parent=i;
    }
}

举个栗子叭~(直接纸上模拟,来说明如何在尚未构造二叉树的结点中寻找权值最小的两个结点)

如初始结点为 1 7 3 5 

在纸上写了一些关键的代码,emmmm我知道既不简洁也不美观(还字丑)哈哈哈

(皮毛的ps技术学以致用hhh)

自己举个例子手动模拟一下就能明白啦:

min1,lnode是分别记录权值最小的结点的大小和下标

min2,rnode是记录权值第二小的结点的大小和下标

且如果有比当前min1小的结点,那么min2就会继承之前记录的那个min1的值(包括对应的lnode),再更新min1和lnode。

就酱~结束·