构造哈夫曼树

构造huffman树的算法:

算法思想：
哈夫曼算法采用自底向上逐步合并的方法，构造哈夫曼树：
步骤1）构造n颗单叶结点的二叉树，形成初始森林。
步骤2）执行三个操作，反复将森林中的两棵树合并成一棵树，直到森林中只有一棵树。

• ① 选择森林中根权值最小的两棵树：T1和T2
• ② 将T1和T2合并称为一颗树T，使T1和T2作为T的左右子树，并且T的根权值为T1，T2根权值之和。
• ③ 将合并后的树T，放回森林中。

//构造哈夫曼树的函数，默认已有序
Hfptr createHftree(Hfptr head)
{
    int i;
    Hfptr p,q,r,t1,t2;         //p，q是后面给合并树排序用的
                               //t1和t2是待合并的两个权值最小二叉树
    for(i=1;i<n;i++)
    {
        r =new Hfnode; //r=malloc(sizeof(Hfnode));
        t1=head->next;  //权值最小的就是第一棵树
        t2=t1->next;    //权值最小的第二棵树
        r->data=t1->data + t2->data; //r的权值为t1和t2的和
        r->Lson=t1;     //t1作为左儿子
        r->Rson=t2;     //t2作为右儿子
        head->next=t2->next; //从森林中删去t1和t2
        q=head;         //准备进行有序插入
        p=head->next;   //p是搜索指针，q是p的前驱
        while(1)            //定位合并树的有序位置
            if(p->data<r->data)  //如果合并树权值比p所指树权值大
            {
                q=p;             //将当前所指位置赋给q
                p=p->next;       //并且p指针后移
            }else{          //否则？也就是找到了比合并树权值大的结点
                r->next=p;      //将那个结点作为p的后继结点
                q->next=r;      //将刚刚q作为p的前驱结点
                break;
            }
    }                        //终止for循环
    p=head->next;        //将头结点作为监督元；
    delete head;            //删去监督元
    return (p);                //返回huffman树的根
}                    //构造完毕