由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树,该树的带权路径长度为
时间: 2023-04-28 15:03:34 浏览: 1251
霍夫曼树带权路径长度求值.cpp
56。
解释:
首先将四个叶子结点按照权值从小到大排序,得到2、5、7、9。
然后将权值最小的两个结点2和5合并,得到一个新的结点7,其权值为2+5=7。
接着将权值最小的两个结点7和7合并,得到一个新的结点14,其权值为7+7=14。
最后将权值最小的两个结点9和14合并,得到根节点,其权值为9+14=23。
根据哈夫曼树的定义,带权路径长度为每个叶子结点的权值乘以该结点到根节点的路径长度之和,因此:
2的路径长度为3,带权路径长度为2*3=6;
5的路径长度为2,带权路径长度为5*2=10;
7的路径长度为1,带权路径长度为7*1=7;
9的路径长度为2,带权路径长度为9*2=18。
将四个叶子结点的带权路径长度相加,得到56,即该哈夫曼树的带权路径长度为56。
阅读全文