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

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

接下来进行哈夫曼树的构造：

1. 选择权值最小的两个结点，即 A(7) 和 C(5)，将它们合并成一个新的结点 AC(12)。

2. 接着选择权值次小的两个结点，即 D(6) 和 AC(12)，将它们合并成一个新的结点 DAC(18)。

3. 然后选择权值次次小的两个结点，即 B(9) 和 E(18)，将它们合并成一个新的结点 BE(27)。

4. 最后选择 DAC(18) 和 BE(27)，将它们合并成一个新的根结点。

构造完成后，得到的哈夫曼树如下图所示：

            45
           /  \
         18    27
        /  \   / \
       7   5  9  18
           / \
          6   7

相关问题

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

好的，这是一道经典的二叉树构建问题。

首先，我们要找到权值最小的两个叶子节点，然后将它们合并成一个父节点，并将该父节点的权值设置为两个子节点权值之和。然后，我们将新的父节点插入到剩余的叶子节点中，重复上述步骤，直到最后只剩下一个节点为止。

按照上述步骤，我们可以构建出一棵二叉树，如下所示：

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 23
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 / 　 　 \
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　 　　11　　　　　　12
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　 / 　 　 　 　 / 　　|　 　 　 \
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　2　　　　4　　　　5　　　　7　　　9

其中，根节点的权值为23，代表整棵树的权值之和。

希望以上回答可以帮助到你。

已知下列字符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。