第4章 樹與二叉樹

1、 A11 A21 A22 A31A32A33A34A35 A11 A21 A22 A31A32A33A34A35 A11 A21 A22 A31A32A33A34A35 A11 A21 A22 A31A32A33A34A35 共兩棵 共五棵 第 層 1=2 第 層 12=2 第i層 2i-1 20+21+22+2k-1=2k-1 1log 2 + +n 高度為k的滿二叉樹有2k-1個(gè)結(jié)點(diǎn)； 1 23 456 7 8 9 10111213 2/ i 2i2i+1 2/ i 根據(jù)性質(zhì)5，從編號(hào)51到100都是葉子。 共有50個(gè)葉子。 1 100 50 a)共有26-1+10=73個(gè)結(jié)點(diǎn)； b)37

2、到73都是葉子，共37個(gè)葉子結(jié)點(diǎn)； c)度為1的結(jié)點(diǎn)數(shù)為0。 1 73 36 A GFED CB HI 10 2 1 3 4 5 67 8 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 A C B 1 3 7 54 2 6 bnode lchild data rchild A G F E DC B A B E C D F G T n個(gè)結(jié)點(diǎn)的二叉鏈表共有2n個(gè)指針域。 其中n-1個(gè)不空，剩下2n-(n-1)=n+1個(gè)指針域?yàn)榭铡?(1)若T為，遍歷；否則轉(zhuǎn)(2) D LR (2) 設(shè)二叉樹的形態(tài)如右圖： 假設(shè)左右子樹能遍歷（用 L， R分別表示其遍歷），

3、則整個(gè)二叉樹 可有如下形式的遍歷： 先左后右：DLR LDR LRD 先右后左：DRL RDL RLD 根序 根序 根序 對(duì)于左右子樹的遍歷，可按照 與相同的方式遍歷（遞歸調(diào)用） (1) A _ _ AA (2) AB _ _ G _ _ GBBG (3) ABC_ _ D _ _ G H I C C DD 先序：ABCEDFGHI (4) ABC E D F G H I A G FE DC B HI 分別寫出右圖二叉樹的 先序、中序和后序序列。 中序：CEBDFAHGI (4) C E B D F A H G I (1) _A_ AA (2) _ B _ A _ G _ GBBG (3) _

4、C_ B_D_ A H G I CCDD A G FE DC B HI 分別寫出右圖二叉樹的 先序、中序和后序序列。 (4) E C F D B H I GA (1) _ _ A AA (2) _ _ B_ _GA GBBG (3) _ _ C _ _D B H I GA CCDD 后序：ECFDBHIGA A G FE DC B HI 分別寫出右圖二叉樹的 先序、中序和后序序列。 A B C E D F G H I 先序：ABCDEFGHI 中序：CBEDFAGIH 后序：CEFDBIHGA A CDBEGF E B A CDG F G F D C B A E A C B A ED G F

5、G F D C B A E 思考思考：只有先序和后序能否唯一還原二叉樹？ A B C E D F G H I n個(gè)結(jié)點(diǎn)的二叉鏈表共有2n個(gè)指針域。 其中n-1個(gè)不空，剩下2n-(n-1)=n+1個(gè)指針域?yàn)榭铡?A G F E DC B A B E C D F G T 中序線索二叉樹 A B C E D F G H I 先序線索二叉樹 A B C E D F G H I 左左 A G FE DCB H I A B C D E F G H I 1 2 3 4 5 6 7 8 9 data parents 0 1 1 2 3 0 8 1 2 BCD EF G I A B C D E F G H I

6、data firstchild A G FE DCB H I A B C D E F G I H A G FE DCB H I firstson data nextbrother 引用：tnode *T 稍變形后與二叉鏈表結(jié)構(gòu)相同 所以任意一棵樹（森林） 必然與的一棵二叉樹一一對(duì)應(yīng)。 A B C D E F G I H A B F G E C D I H firstson data nextbrother lchild data rchild A B I DGF H CE A GFE DCB H I K L K L A B CE D F G A B C E D F G A GFE DCB H

7、I K L 先序序列：ABEFCGDHIKL 后序序列：EFBGCIHDALK ：樹（森林）的后序遍歷序列 與對(duì)應(yīng)的二叉樹相同。 A GFE DCB H I K L = n i iil w 1 A B CE D K G H JI F0.05 0.6 0.1 0.10.10.05 WPL=0.6*4+0.1*4+0.05*3+0.05*2+0.1*2+0.1*2 66 34121085618T= 34 7 56 11 8 15 10 21 12 27 18 39 WPL= (3+4+5+6)* 4+(8+10)*3+(18+12)*2 =186 WPL=66+27+39+15+21+7+11=186 101 811 19 56 1115 26 20 39 36 62101+62+39+26+19+11 =258 WPL= 101 1511 26 56 118 1920 39 101+62+39+26+