哈夫曼树（最优二叉树）的构造【二叉树的应用】

╰半橙微兮° 2022-06-02 08:40 241阅读 0赞

对于给定一个长度为m序列，构造一颗以序列值为权的m个外部结点的扩充二叉树，使得带权的外部路径长度WPL最小，就称这颗扩充二叉树为 哈夫曼（Huffman）树（最优二叉树）。构造Huffman Tree 的算法也就是哈夫曼算法。

算法基本思想：

1）给定m个权值，首先构造m课扩充二叉树，每颗只有一个外部结点（根结点）。

2）在已经构造的所有扩充二叉树中，选择根结点权值最小的和次小的两颗，将它们作为左、右子树，构造一颗新的扩充二叉树，它的根结点的权值为其左右子树根结点的权值之和。

3）重复2），每次使得扩充二叉树的数目减一，当只剩下最后一颗扩充二叉树时，其便是所求的哈夫曼树。

代码实现：

#include <iostream>
    #define MAXINT 10000
    #define N 13                        //构建13个结点
    using namespace std;
    
    struct HtNode{
        int var,parent,llink,rlink;
    };
    struct HtTree{
        int m,root;                     //外部结点个数、根结点在ht数组中的下标
        struct  HtNode *ht;
    };
    typedef struct HtTree * PHtTree;
    
    void print(PHtTree p)
    {
        cout<<"index var parent lchild rchild\n";
        for(int i=0;i<2*N-1;i++)
            cout<<i<<"\t"<<p->ht[i].var<<"   "<<p->ht[i].parent<<"     "
                <<p->ht[i].llink<<"     "<<p->ht[i].rlink<<endl;
    }
    
    PHtTree huffman(int m,int *seq)
    {
        PHtTree pht=new struct HtTree;  //分配空间
        pht->ht=new HtNode[2*m-1];      //外部结点为m，则内部结点为m-1，则总共点数为2m-1
        for(int i=0;i<2*m-1;i++){       //置ht数组初态
            pht->ht[i].llink=pht->ht[i].rlink=pht->ht[i].parent=-1;
            pht->ht[i].var= i<m?seq[i]:-1;
        }
        cout<<"数组ht的初态：\n";
        print(pht);
        for(int i=0;i<m-1;i++){         //每次循环构造一个内部结点
            int m1=MAXINT,m2=MAXINT;
            int x1=-1,x2=-1;
            for(int j=0;j<m+i;j++){
                                        //找最小权的无父节点的结点
                if(pht->ht[j].var<m1 && pht->ht[j].parent==-1){
                    m2=m1;x2=x1;
                    m1=pht->ht[j].var; x1=j;
                }                       //找次最小权的无父节点的结点
                else if(pht->ht[j].var<m2 && pht->ht[j].parent==-1){
                    m2=pht->ht[j].var;x2=j;
                }
            }
                                        //构造内部结点
            pht->ht[x1].parent=pht->ht[x2].parent=m+i;
            pht->ht[m+i].var=m1+m2;
            pht->ht[m+i].llink=x1;
            pht->ht[m+i].rlink=x2;
        }
        pht->root=2*m-2;
        return pht;
    }
    int main()
    {
        int sequence[N];
        for(int i=0;i<N;i++)
            cin>>sequence[i];
        PHtTree p=huffman(N,sequence);
        cout<<"数组ht的终态：\n";
        print(p);
        return 0;
    }

时间复杂度为O(n^2)。

Input

2 3 5 7 11 13 17 19 23 29 31 37 41

Output

数组ht的初态：
    index var parent lchild rchild
    0       2   -1     -1     -1
    1       3   -1     -1     -1
    2       5   -1     -1     -1
    3       7   -1     -1     -1
    4       11   -1     -1     -1
    5       13   -1     -1     -1
    6       17   -1     -1     -1
    7       19   -1     -1     -1
    8       23   -1     -1     -1
    9       29   -1     -1     -1
    10      31   -1     -1     -1
    11      37   -1     -1     -1
    12      41   -1     -1     -1
    13      -1   -1     -1     -1
    14      -1   -1     -1     -1
    15      -1   -1     -1     -1
    16      -1   -1     -1     -1
    17      -1   -1     -1     -1
    18      -1   -1     -1     -1
    19      -1   -1     -1     -1
    20      -1   -1     -1     -1
    21      -1   -1     -1     -1
    22      -1   -1     -1     -1
    23      -1   -1     -1     -1
    24      -1   -1     -1     -1
    数组ht的终态：
    index var parent lchild rchild
    0       2   13     -1     -1
    1       3   13     -1     -1
    2       5   14     -1     -1
    3       7   15     -1     -1
    4       11   16     -1     -1
    5       13   16     -1     -1
    6       17   17     -1     -1
    7       19   18     -1     -1
    8       23   18     -1     -1
    9       29   19     -1     -1
    10      31   20     -1     -1
    11      37   21     -1     -1
    12      41   21     -1     -1
    13      5   14     0     1
    14      10   15     2     13
    15      17   17     3     14
    16      24   19     4     5
    17      34   20     6     15
    18      42   22     7     8
    19      53   22     16     9
    20      65   23     10     17
    21      78   23     11     12
    22      95   24     18     19
    23      143   24     20     21
    24      238   -1     22     23

注意，结果中index表示数组ht的下标，意味着各节点之间的关系，例如（下标为0的）结点2和（下标为1的）结点3的父节点（下标为13）为5，再看下标的13的结点5，它的左孩子是（下标为0的）结点2，右孩子为（下标为1的）结点3。

构造的哈夫曼树如下，

![Image 1][]

[Image 1]: