有7个带权结点,其权值分别为4,7,8,2,5,16,30,试以它们为叶子结点构造一棵赫夫曼树,并计算其WPL。
时间: 2024-05-04 12:21:35 浏览: 17
赫夫曼树的构造过程如下:
1. 将所有结点按权值从小到大排序,得到{2,4,5,7,8,16,30}。
2. 取出权值最小的两个结点2和4,构建一棵树,其根结点权值为2+4=6,左子树为权值为2的叶子结点,右子树为权值为4的叶子结点。
3. 将根结点权值6插入到排序后的序列中,得到{5,6,7,8,16,30}。
4. 取出权值最小的两个结点5和6,构建一棵树,其根结点权值为5+6=11,左子树为之前的树,右子树为权值为5的叶子结点。
5. 将根结点权值11插入到序列中,得到{7,8,11,16,30}。
6. 重复上述步骤,直到所有结点都被构建为一棵树。最终得到的赫夫曼树如下所示:
```
76
/ \
30 46
/ \
16 30
/ \
13 17
/ \
5 8
/ \
2 3
```
其中,每个非叶子结点都是左右子树根结点权值之和。
树的WPL为:2x2 + 3x2 + 5x2 + 8x2 + 13x2 + 16x1 + 17x1 = 96。
相关问题
有7个带权结点,其权值分别为4,7,8,2,5,16,30,试以它们为叶子结点构造一棵赫夫曼树
赫夫曼树的构建过程如下:
1. 将结点按照权值从小到大排序,得到 2,4,5,7,8,16,30。
2. 从中选取权值最小的两个结点 2 和 4,构造一棵二叉树,其根节点的权值为 2 + 4 = 6,将这棵树看作一个结点,权值为 6。
3. 将上一步构造的结点和权值为 5 的结点组成新的二叉树,其根节点的权值为 5 + 6 = 11,将这棵树看作一个结点,权值为 11。
4. 将上一步构造的结点和权值为 7 的结点组成新的二叉树,其根节点的权值为 7 + 11 = 18,将这棵树看作一个结点,权值为 18。
5. 将上一步构造的结点和权值为 8 的结点组成新的二叉树,其根节点的权值为 8 + 18 = 26,将这棵树看作一个结点,权值为 26。
6. 将上一步构造的结点和权值为 16 的结点组成新的二叉树,其根节点的权值为 16 + 26 = 42,将这棵树看作一个结点,权值为 42。
7. 将上一步构造的结点和权值为 30 的结点组成新的二叉树,其根节点的权值为 30 + 42 = 72,将这棵树看作一个结点,权值为 72。
8. 构造完成,得到一棵赫夫曼树,其根节点的权值为 72。树的形态如下所示:
```
72
/ \
42 30
/ \
18 16
/ \
7 11
/ \
5 6
/ \
2 4
```
有七个带权结点,其权值分别为3,5,7,2,6,12,15.构造哈夫曼树,计算带权路径长度
好的,让我帮你计算一下。根据哈夫曼树的构造规则,我们先将权值从小到大排序,得到:2,3,5,6,7,12,15。然后,将权值最小的两个节点合并,得到一个新节点,权值为它们之和。依次类推,直到只剩下一个节点,构成哈夫曼树。在这个过程中,每次新节点的权值都是合并的两个节点的权值之和。最后,将每个叶子节点到根节点的距离乘以它的权值,再把所有叶子节点的结果相加,就是带权路径长度。所以,这道题的带权路径长度是:2*3 + 2*5 + 3*6 + 3*7 + 4*12 + 4*15 = 138。