以357911作为叶子结点的权值构造的哈夫曼树的带权路径长度为
带权路径长度(WPL)是指在哈夫曼树中,每个叶子结点的权值乘以其到根结点的路径长度之和。
给定叶子结点的权值为3, 5, 7, 9, 11。首先,将这些叶子结点按照权值从小到大进行排序,得到3, 5, 7, 9, 11。
接下来,构造哈夫曼树的过程如下:
-
从排序后的权值列表中,选择权值最小的两个结点作为左右子结点,构造一个新的结点作为它们的父结点。将新的父结点的权值设为左右子结点权值的和。
此时,选择3和5作为左右子结点,构造一个新的父结点,其权值为3+5=8。得到新的权值列表:7, 8, 9, 11。
-
将新的父结点插入到权值列表中,并重新排序。
插入新的父结点后,得到新的权值列表:7, 8, 8, 9, 11。
-
重复步骤1和步骤2,直到所有的结点都被合并为一个根结点。
最终得到的哈夫曼树如下:
38
/ \
18 20
/ \
8 10
/ \ / \
3 5 7 9
\
11
计算带权路径长度的公式为:WPL = 3 * 2 + 5 * 2 + 7 * 2 + 9 * 2 + 11 * 2 = 6 + 10 + 14 + 18 + 22 = 70。
所以,以3, 5, 7, 9, 11作为叶子结点的权值构造的哈夫曼树的带权路径长度为70。
原文地址: https://www.cveoy.top/t/topic/i59u 著作权归作者所有。请勿转载和采集!