数据结构与算法专题1

以下是理论:

1)根据给定的n个权值{{w1，w2，…，wn}，Wn}，构造一组n棵二叉树f = {T1，T2，...，TN}，其中

每棵二叉树只包含一个加权值为wi的根节点，其左右子树为空；

(2)在F中，选择两个其根节点权重最小的二叉树作为左右子树，构造一个新的二叉树，这个新二叉树的根节点的权重是其左右子树节点的权重之和；

(3)从F中删除这两棵树，加上新生成的新树；

(4)重复步骤(2)和(3)，直到F只包含一棵树。

简单来说，寻路方法是这样的。首先，从这组权重中选择最小的两个节点，如5和6，形成一棵新树。父节点W=11，权重加上11，去掉5和6，W = {11，8，8。组成一棵新树，父节点值为19，加上权重再去掉11和8，w={19，12}，直到最后的根节点W=31。

此时，所有叶节点乘以其路径长度，然后累加。

所以是5 * 3+6 * 3+8 * 2+12 * 1 = 61。