數(shù)據(jù)結(jié)構(gòu)——樹的概念和二叉樹PPT學習教案

1、會計學1 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)樹的概念和二叉樹樹的概念和二叉樹 第1頁/共87頁 第2頁/共87頁 A E C D B IHG F 第3頁/共87頁 第4頁/共87頁 第5頁/共87頁 第6頁/共87頁 第7頁/共87頁 第8頁/共87頁 第9頁/共87頁 第10頁/共87頁 第11頁/共87頁 第12頁/共87頁 A (a) (b) (c) (d) (e) A C B A C B C B A C B A C B 含有3個結(jié)點的不同二叉樹 第13頁/共87頁 第14頁/共87頁 第15頁/共87頁 第16頁/共87頁 第17頁/共87頁 1 564 3 7 2 98101311121415 第18

2、頁/共87頁 第19頁/共87頁 564 3 7 2 9810 1 第20頁/共87頁 第21頁/共87頁 第22頁/共87頁 第23頁/共87頁 第24頁/共87頁 31 23 12 66 94 17 5 70 62 49 17 12 5 23 627049 31 66 94 第25頁/共87頁 C B A 2 5 7 3 1 a1a2a3a4a5 A B a6 a7 C 第26頁/共87頁 leftright data 第27頁/共87頁 A DC B EF G A C B E F D G root 第28頁/共87頁 第29頁/共87頁 leftdataparentright 第30頁/

3、共87頁 遍歷方式 先根遍歷： DLR 中根遍歷： LDR 后根遍歷： LRD D RL 第31頁/共87頁 A B D FC E 第32頁/共87頁 第33頁/共87頁 A B D FC E 第34頁/共87頁 第35頁/共87頁 A B D FC E 第36頁/共87頁 第37頁/共87頁 第38頁/共87頁 第39頁/共87頁 第40頁/共87頁 第41頁/共87頁 結(jié)點 結(jié)點狀態(tài) i 第42頁/共87頁 第43頁/共87頁 第44頁/共87頁 第45頁/共87頁 A B D FC E 第46頁/共87頁 A B D FC E 第47頁/共87頁 第48頁/共87頁 第49頁/共87頁

4、A B C K D E H F A B E D C K F H A B D C K E H F 第50頁/共87頁 A C B E D F G H A B C D E F G H A B C G D E H F 第51頁/共87頁 第52頁/共87頁 第53頁/共87頁 第54頁/共87頁 第55頁/共87頁 A B EC D 第56頁/共87頁 第57頁/共87頁 第58頁/共87頁 第59頁/共87頁 第60頁/共87頁 第61頁/共87頁 第62頁/共87頁 第63頁/共87頁 第64頁/共87頁 第65頁/共87頁 第66頁/共87頁 c l i i n i 1 第67頁/共87頁 第

5、68頁/共87頁 第69頁/共87頁 外通路長度為 3 3 2 3 4 4 3 3=25 內(nèi)通路長度為 2 1 0 2 3 12=11. 第70頁/共87頁 其中，n表示外結(jié)點的個數(shù)，wi和Li分別表示 外結(jié)點ki的權值和根到ki之間的路徑長度。 第71頁/共87頁 第72頁/共87頁 第73頁/共87頁 第74頁/共87頁 第75頁/共87頁 例: F=7,5,2,4 24 7 5 11 6 18 7524 75 2 6 4 7 5 24 11 6 第76頁/共87頁 第77頁/共87頁 第78頁/共87頁 第79頁/共87頁 編碼 A (0) T (10) C (110) S (111) 7 5 42 6 11 1 8 總編碼長度： 1*7+2*5+3*2+3*4=3 5 第80頁/共87頁 第81頁