给定一组数据{6,2,7,10,3,12}以它构造一棵哈夫曼树,则树高为 ,带权路径长度WPL的值为
时间: 2024-06-03 11:13:01 浏览: 180
霍夫曼树带权路径长度求值.cpp
首先,我们需要按照权值从小到大的顺序对数据进行排序,得到{2,3,6,7,10,12}。然后,我们可以按照哈夫曼树的构造方法,不断合并权值最小的两个节点,直到只剩下一个根节点为止。
首先,我们合并2和3,得到一个权值为5的节点。然后,我们合并5和6,得到一个权值为11的节点。接着,我们合并7和10,得到一个权值为17的节点。然后,我们合并11和12,得到一个权值为23的节点。最后,我们将17和23合并,得到一个权值为40的根节点。
这样,我们就构造出了一棵哈夫曼树,其树高为3。根据哈夫曼树的性质,每个叶子节点的深度即为其权值,因此每个节点的带权路径长度即为其深度乘以权值。将每个节点的带权路径长度相加,得到WPL的值为:
2×1 + 3×2 + 6×2 + 7×2 + 10×2 + 12×2 = 70
因此,树高为3,WPL的值为70。
阅读全文