哈夫曼樹的定義微課

大數(shù)據(jù)技術(shù)與應(yīng)用資源庫主講人：李剛哈夫曼樹的定義數(shù)據(jù)結(jié)構(gòu)（C語言版）

路徑和路徑長度01

帶權(quán)路徑長度02

哈夫曼樹定義031.順序棧實例演示路徑和路徑長度1在一棵樹中，從一個結(jié)點(diǎn)往下可以達(dá)到的孩子或子孫結(jié)點(diǎn)之間的通路，稱為路徑。路徑定義eabcd根到結(jié)點(diǎn)c的路徑1.順序棧實例演示路徑和路徑長度1通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長度為L-1。路徑長度定義eabcd根到結(jié)點(diǎn)c的路徑長度為32

1.順序棧實例演示帶權(quán)路徑長度2若將樹中結(jié)點(diǎn)賦給一個有著某種含義的數(shù)值，則這個數(shù)值稱為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的權(quán)8

4

15

21

eabcd2

1.順序棧實例演示帶權(quán)路徑長度2結(jié)點(diǎn)的帶權(quán)路徑長度為從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)的權(quán)的乘積。結(jié)點(diǎn)帶權(quán)路徑長度8

4

15

21

eabcd結(jié)點(diǎn)c的帶權(quán)路徑長度為：3*4=122

1.順序棧實例演示帶權(quán)路徑長度2樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，記為WPL。樹的帶權(quán)路徑長度8

4

15

21

eabcd該樹的帶權(quán)路徑長度為：2*8+2*2+3*4+3*15+2*21=1191.順序棧實例演示哈夫曼樹定義3給定n個權(quán)值作為n個葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹。基本定義假設(shè)給定5個葉子結(jié)點(diǎn)a、b、c、d和e分別帶權(quán)8、2、4、15和21，構(gòu)建三棵不同的二叉樹，分別求WPL值。1.順序棧實例演示哈夫曼樹定義32

8

4

15

21

eabcd該樹的帶權(quán)路徑長度為：2*8+2*2+3*4+3*15+2*21=1191.順序棧實例演示哈夫曼樹定義34

8

2

15

21

eacbd該樹的帶權(quán)路徑長度為：2*8+3*2+2*4+3*15+2*21=1171.順序棧實例演示哈夫曼樹定義32

4

8

abc該樹的帶權(quán)路徑長度為：3*8+4*2+4*4+2*15+1*21=9915d21

e