有数据WG={3,2,4,5,1}, (1)画出所构建的Huffman 树; (2)所建Huffman 树的树高是多少? (3)求所建Huffman 树的带权路径长度WPL。
时间: 2023-06-09 21:07:41 浏览: 65
好的,让我来回答你的问题。
1. 首先,在给定的数据WG={3,2,4,5,1}中,我们将每个数值看作一个节点,并按照节点的权值大小进行排序,即{1,2,3,4,5}。
2. 接下来,我们每次选择权值最小的两个节点进行合并,直到将所有节点合并为一个根节点,得到如下的Huffman树:
15
/ \
7 8
/ \ / \
3 4 2 3
/ \
1 1
其中,每个节点的权值在其下方标注,树的根节点权值为所有节点权值之和。
3. 所建Huffman树的树高为3,即从根节点到最远叶子节点的距离为3。
4. 最后,我们计算所建Huffman树的带权路径长度WPL。WPL是所有叶子节点的权值乘上其深度的和,即:
WPL = 1*3 + 1*4 + 2*2 + 3*2 + 4*1 = 20
所以,所建Huffman树的带权路径长度WPL为20。
相关问题
有数据WG={7,19,2,6,32,3,21,10}, (1)画出所构建的Huffman 树; (2)所建Huffman 树的树高是多少? (3)求所建Huffman 树的带权路径长度WPL。
好的,我明白了。以下是我的回答:
(1) 画出所构建的Huffman 树:
首先,我们需要根据数据WG中每个元素的权值构建Huffman 树。我们可以利用以下步骤:
1. 对数据WG中的每个元素创建一个叶节点,并将其与相应的权值绑定。
2. 将这些叶节点按照权值从小到大排序,选择两个权值最小的节点作为新节点的左右子节点,并将它们的权值相加得到新节点的权值。
3. 将新生成的节点放回到节点序列中,重复上述步骤直到只剩下一个节点。
4. 这个节点就是Huffman 树的根节点。
根据上述步骤,我们得到的Huffman 树如下所示:
96
/ \
53 43
/ \ / \
29 24 18 25
/ / \
9 7 11
\
4
(2) 所建Huffman 树的树高是4。
(3) 求所建Huffman 树的带权路径长度WPL。
由于带权路径长度WPL是指所有叶节点的权值乘以该叶节点的深度之和,因此我们需要计算每个叶节点的权值以及深度,然后进行加权求和。
我们可以将计算过程表示成以下的表格:
节点 权值 深度 权值 × 深度
WG[0] 7 4 28
WG[1] 19 3 57
WG[2] 2 5 10
WG[3] 6 4 24
WG[4] 32 2 64
WG[5] 3 5 15
WG[6] 21 3 63
WG[7] 10 4 40
总计 301
因此,所构建的Huffman 树的带权路径长度WPL为301。