有5个结点A,B,C,D,E,权值为7,9,5,6,18，构造一颗哈夫曼树(包含过程)

首先，将所有结点按照权值从小到大排序，得到序列A(7), C(5), D(6), B(9), E(18)。

接着，取出权值最小的两个结点C(5)和D(6)，将它们合并成一个新结点CD(11)，并将CD插入到序列中。现在序列为A(7), CD(11), B(9), E(18)。

再次取出权值最小的两个结点A(7)和CD(11)，将它们合并成一个新结点ACD(18)，并将ACD插入到序列中。现在序列为ACD(18), B(9), E(18)。

接下来，取出权值最小的两个结点B(9)和ACD(18)，将它们合并成一个新结点BACD(27)，并将BACD插入到序列中。现在序列为BACD(27), E(18)。

最后，取出权值最小的两个结点BACD(27)和E(18)，将它们合并成一个新结点根节点(45)。这就是哈夫曼树的构造过程。哈夫曼树如下图所示：

        45
      /    \
     /      \
    27      18
   /  \     
  /    \    
  9   ACD
      /  \
     /    \
    7     11
   / \    
  /   \   
 C    D 

相关问题

给出权值是2、4、5、7、9的叶子结点，请构造一颗二叉树

好的，我可以为您构造一个权值为2、4、5、7、9的叶子结点的二叉树。

27
/ \
/ \
11 16
/ \ / \
/ \ / \
4 7 5 9

其中，27为根节点，其左子树由11作为根节点，左右节点分别为4和7；右子树由16作为根节点，左右节点分别为5和9。

已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8、11，试填写出其对应赫夫曼树HT存储结构的初态和终态，并利用权值构造一颗哈夫曼树（约定左孩子权值小于右子树权值），并对其进行赫夫曼编码，并计算WPH。

初态：将每个字符看作一个权值为其权值的树，共有7棵树。

终态：哈夫曼树HT存储结构中，每个非叶子结点有两个指针域，分别指向其左右孩子。

构造哈夫曼树的过程如下：

1.将所有权值从小到大排序，得到{E, A, D, C, F, G, B}。

2.将权值最小的E和次小的A合并，得到一棵新树，其权值为E和A的权值之和15，中间节点为权值为15的根节点，E、A为其左右孩子。

3.将权值为15的树（包含E、A）和权值第三小的D合并，得到一棵新树，其权值为15+4=19，中间节点为权值为19的根节点，15为其左孩子，D为其右孩子。

4.将权值为19的树（包含E、A、D）和权值第四小的C合并，得到一颗新树，其权值为19+7=26，中间节点为权值为26的根节点，19为其左孩子，C为其右孩子。

5.将权值为26的树和权值为第五小的F合并，得到一颗新树，其权值为26+2=28，中间节点为权值为28的根节点，26为其左孩子，F为其右孩子。

6.将权值为28的树和权值为第六小的G合并，得到一颗新树，其权值为28+11=39，中间节点为权值为39的根节点，28为其左孩子，G为其右孩子。

7.将权值为39的树和权值为最大的B合并，得到一颗新树，其权值为39+12=51，中间节点为权值为51的根节点，39为其左孩子，B为其右孩子。

最终得到的哈夫曼树如下：

      51
     /  \
    39   B
   /  \
  28   G
 /  \
26   F
  \
  19
 /  \
15   D
   /  \
  A    E

利用得到的哈夫曼树，可以求出字符A、B、C、D、E、F、G的编码：

A：从根节点到A的路径为左左，编码为00

B：从根节点到B的路径为右，编码为1

C：从根节点到C的路径为左右右，编码为011

D：从根节点到D的路径为左右左，编码为010

E：从根节点到E的路径为左左右，编码为001

F：从根节点到F的路径为左右右右，编码为0111

G：从根节点到G的路径为左右左右，编码为0101

WPH = 3*2 + 12*1 + 7*3 + 4*2 + 2*3 + 8*2 + 11*2 = 87。