什么是带权最优二元树

Question

什么是带权最优二元树

Answer 1

一棵带权二元树的代价就是树中所有根结点权之和.代价最小的带权二元树称为最优二元树.问题转化为求最优带权二元树.
那么,什么是最优带权二元树呢?
最优二叉树,又称哈夫曼树,是一类带权路径长度最短的树,有着广泛的应用.
我们首先给出路径和路径长度的概念.从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称做路径长度.树的路径长度是从树根到每一结点的路径长度之和.这种路径长度最短的二叉树是.
若将上述概念推广到一般情况,考虑带权的结点.结点的带权路径长度为从该结点树根之间的路径长度与结点上权的乘积.树的带权路径长度为树中所有叶子结点的带路径长度之和,通常记作
WPL=∑W(k)L(k) k=1...n
假设有n个权值W(1),W(2),.,W(n),试构造一棵有n个叶子结点的二叉树,每个叶子结点带权为W(k),则其中带权路径长度WPL最小的二叉树称做最优二又树或哈夫显树.