最優(yōu)二叉搜索樹(shù)？給定n個(gè)權(quán)重作為n個(gè)葉節(jié)點(diǎn)，構(gòu)造一棵二叉樹(shù)。如果樹(shù)的加權(quán)路徑長(zhǎng)度達(dá)到最小值，這樣的二叉樹(shù)稱為最優(yōu)二叉搜索樹(shù)，也稱為哈夫曼樹(shù)。哈夫曼樹(shù)是路徑長(zhǎng)度最短的樹(shù)，權(quán)重越大的節(jié)點(diǎn)越靠近根。設(shè)二叉排

最優(yōu)二叉搜索樹(shù)？

給定n個(gè)權(quán)重作為n個(gè)葉節(jié)點(diǎn)，構(gòu)造一棵二叉樹(shù)。如果樹(shù)的加權(quán)路徑長(zhǎng)度達(dá)到最小值，這樣的二叉樹(shù)稱為最優(yōu)二叉搜索樹(shù)，也稱為哈夫曼樹(shù)。哈夫曼樹(shù)是路徑長(zhǎng)度最短的樹(shù)，權(quán)重越大的節(jié)點(diǎn)越靠近根。

設(shè)二叉排序樹(shù)中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)的平均查找長(zhǎng)度為？

最壞的情況是深度為n的單棵樹(shù)是（n1）/2

最好的情況是形狀均勻，半搜索約為log2n

PS:如果構(gòu)造完成，例如：

則平均搜索長(zhǎng)度為：（1×12×23×44×3）/10=2.9