数据结构—基础知识：哈夫曼树

本文介绍: 主要讲解了哈夫曼树的概念和如何构造一棵哈夫曼树，WPL等

哈夫曼（Huffman）树又称最优树，是一类带权路径长度最短的树，在实际中有广泛的用途。哈夫曼树的定义，涉及路径、路径长度、权等概念，下面先给出这些概念的定义，然后再介绍哈夫曼树

例如，下图中所示的3棵二叉树，都含4个叶子结点a、b、c、d，分别带权7、5、2、4，他们的带权路径长度分别为

在构造哈夫曼树时，首先选择权小的，这样保证权大的离根较近，这样一来，在计算树的带权路径长度时，自然会得到最小带权路径长度，这种生成算法是一种典型的贪心法。

注：哈夫曼树的结点的度数为0或2，没有度为1的结点。

//-------哈夫曼树的存储表示-------
typedef struct{
    int weight;//结点的权值
    int parent,lchild,rchild;//结点的双亲、左孩子、右孩子的下标
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树

权值	双亲	左孩子	右孩子
weight	parent	lchild	rchild

void CreateHuffmanTree(HuffmanTree &HT,int n)
{
    if(n<=1) return;
    m=2*n-1;
    HT=new HTNode[m+1];//0号单元未用，所以需要动态分配m+1个单元，HT[m]表示根结点
    for(i=1;i<=m,++1)//将1~m号单元中的双亲、左孩子，右孩子的下标都初始化为0
    {
        HT[i].parnt=0;HT[i].lchild=0;HT[i].rchild=0;
    }
    for(i=1;i<=n,++1)//输入前n个单元中叶子结点的权值
        cin>>HT[i].weight;
/*-----------初始化工作结束，下面开始创建哈夫曼树-----------*/
    for(i=n+1;i<=n;++1)
    {//通过n-1次的选择、删除、合并来创建哈夫曼树
        Select(HT,i-1,s1,s2);
        //在HT[k]（1≤k≤i-1）中选择两个其双亲域0且权值最小的结点，并返回它们在HT中的序号s1和s2（最小结点下标）
        HT[s1].parent=i;HT[s2].parent=i;//修改HT[s1][s2]的parent值
        HT[i].lchild=s1;HT[i].rchild=s2;//s1,s2分别作为i的左右孩子
        HT[i].weight=HT[s1].weight+HT[s2].weight;//i的权值为左右孩子之和
    }
}