由权值分别为1,26,5,9,12,16的叶子结点生成一棵哈夫曼树 1. 画出该哈夫曼树(要求左孩子权值尽可能小，哈夫曼树的高度尽可能小) 2. 求出该哈夫曼树的带权路径长度

1. 生成哈夫曼树的过程如下：
首先，将所有叶子结点按照权值从小到大排序，得到序列1,5,9,12,16,26。
取出权值最小的两个叶子结点1和5，将它们合并成一个新的结点，权值为1+5=6，得到序列6,9,12,16,26。
再次取出权值最小的两个叶子结点6和9，将它们合并成一个新的结点，权值为6+9=15，得到序列12,15,16,26。
继续取出权值最小的两个叶子结点12和15，将它们合并成一个新的结点，权值为12+15=27，得到序列16,26,27。
最后，取出权值最小的两个叶子结点16和26，将它们合并成一个新的结点，权值为16+26=42，得到哈夫曼树，如下图所示：

          42
        /    \
      16     26
      / \     
     6   9     
        / \    
       1   5    

2. 计算带权路径长度，即每个叶子结点的权值乘以路径长度之和，再将所有叶子结点的带权路径长度相加，得到结果：
$$(1\times3)+(5\times3)+(9\times2)+(12\times2)+(16\times1)+(26\times1)=3+15+18+24+16+26=102$$
因此，该哈夫曼树的带权路径长度为102。

相关问题

由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为

首先，我们需要将叶子节点按照权值从小到大排序，得到：2,3,5,6,8。

然后，我们需要不断地合并权值最小的两个节点，直到只剩下一个根节点。每次合并后，新生成的节点的权值为合并前两个节点的权值之和。因此，我们可以得到以下合并过程：

1. 合并2和3，得到一个新节点5，权值为2+3=5。
2. 合并5和5，得到一个新节点10，权值为5+5=10。
3. 合并6和8，得到一个新节点14，权值为6+8=14。
4. 合并10和14，得到一个新节点24，权值为10+14=24。

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

           24
         /    \
        10    14
       /  \
      5    5
     / \
    2   3

根据哈夫曼树的定义，带权路径长度是指每个叶子节点的权值乘以其到根节点的路径长度之和。因此，我们可以计算出每个叶子节点的带权路径长度：

- 权值为2的叶子节点，路径长度为3，带权路径长度为2*3=6；
- 权值为3的叶子节点，路径长度为2，带权路径长度为3*2=6；
- 权值为5的叶子节点，路径长度为2，带权路径长度为5*2=10；
- 权值为6的叶子节点，路径长度为2，带权路径长度为6*2=12；
- 权值为8的叶子节点，路径长度为1，带权路径长度为8*1=8。

最终，将每个叶子节点的带权路径长度相加，得到的结果为6+6+10+12+8=42。因此，这棵哈夫曼树的带权路径长度为42。

由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度头

生成哈夫曼树的步骤如下：
1. 将权值从小到大排列，得到 2,3,5,6,8。
2. 取出权值最小的两个节点，将它们合并成一个新节点，新节点的权值为两个节点的权值之和，并将新节点放回权值序列中。
3. 重复步骤 2，直到所有节点都被合并为一个根节点，得到哈夫曼树。

按照上述步骤，我们可以得到以下哈夫曼树：

        24
       /  \
      /    \
     11    13
    /  \   
   /    \  
  5      6  
 / \    
2   3   

根据哈夫曼树的定义，带权路径长度（WPL）是每个叶子节点的权值乘以到根节点的路径长度之和。因此，这棵哈夫曼树的带权路径长度为：

WPL = 2*3 + 3*3 + 5*2 + 6*2 + 8*2 = 46

因此，它的带权路径长度为46。