最优二叉树的权怎么算？离散数学最优二叉树

一、求哈夫曼树的带权路径长度

树的带权路径长度＝所有叶子节点带权路径长度之和

即所有叶子节点的权值乘以该叶子节点所在的层次（第一层为0）之和

树的带权路径长度：为树中所有叶子节点的带权路径长度之和。

对某一个叶子节点他的带权路径长度就是从根节点到他之间连线的最短条数乘以他的权值。

一般的，我们是可以用常规的构造哈夫曼树求带权路径长度。

树的带权路径长度（WeightedPathLengthofTree，简记为WPL）

计算结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。

带权路径长度WPL（WeightedPathLength）最小的二叉树，也称为最优二又树。

构造哈夫曼树的办法是：在W中选出两个权小结点，并同时计算出它们的和，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。

二、最优二叉搜索树

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉搜索树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。