什么是全圖的最優(yōu)樹

最優(yōu)樹指哈夫曼樹。哈夫曼樹：給定N個權(quán)值作為N個葉子結(jié)點，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點離根較近。

哈夫曼樹介紹

1、路徑和路徑長度

在一棵樹中，從一個結(jié)點往下可以達到的孩子或?qū)O子結(jié)點之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點的層數(shù)為1，則從根結(jié)點到第L層結(jié)點的路徑長度為L-1。

2、結(jié)點的權(quán)及帶權(quán)路徑長度

若將樹中結(jié)點賦給一個有著某種含義的數(shù)值，則這個數(shù)值稱為該結(jié)點的權(quán)。結(jié)點的帶權(quán)路徑長度為：從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。