数据结构考研分类复习真题 第六章 答案 (四)[30]

．首先确定是否需加虚权值（即权值为）对m个权值建k叉树若（m）%(k)=则不需要加虚权值否则第一次归并时需（m）%(k)+个权值归并建立k叉树的过程如下

（）将m个权值看作m棵只有根结点的k叉树的集合F={TT…Tm}

（）从F中选k（若需加虚权值则第一次选（m）%(k)+）个权值最小的树作子树构成一棵k叉树k叉树根结点的权值为所选的k个树根结点权值之和在F中删除这k棵子树并将新k叉树加入到F中

（）从F中选k个权值最小的树作子树构成一棵k叉树其根结点权值等于所选的k棵树根结点权值之和在F中删除这k棵树并将新得到的树加到F中

() 重复（）直到F中只有一棵树为止这就是最优的k叉树对本题个权值构造最优三叉树因（）%()=所以第一次用个权值合并

最小加权路径长度

（+）*+(+)*+(++++)*+*=

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []