Question

二叉树 明天要考试了 求这题答案要过程

试构造一棵二叉树,包含权为1,4,9,16,25,36,49,64,81,100等10 个终端结点,且具有最小的加权路径长度WPL。

Answer 1

其实这就是最优二叉树的构建。1、首先从所有结点中选取权值最小的两个结点。2、然后新建一个结点，结点值为该两个结点值之和，并且将该两个结点分别作为新节点的左右子树、然后从原集合结点中删除该两个结点。3、将新节点添加到结点集合中。4、重复1—3过程，直到最后一次合并之后，集合中只剩下一个元素，即根节点。
上述步骤结束后即可得到一棵最优二叉树了。最小加权路径WPL=∑Wi*Ni；即构建的二叉树中，第i层的结点总数Ni和该层权重之积再求一个和。