5-樹及二叉樹

《5-樹及二叉樹》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、1.樹的定義和術語2.二叉樹:定義、性質(zhì)、存儲3.二叉樹的遍歷4.二叉樹遍歷的迭代器類*5.中序穿線樹6.最優(yōu)二叉樹及其應用7.樹和森林第五章樹及二叉樹樹和森林樹：n>0個結點的集合，根+其余結點分為m>=0個集合，每一個集合本身又是一棵樹（子樹）結點的度：該結點的子樹數(shù)目樹的度：樹中各結點度數(shù)的最大值葉子、父結點、兒子結點、兄弟結點祖先結點：從根結點到該結點的路徑上所有結點層次、高度：根為1,依次往下數(shù)有序樹：規(guī)定所有結點的兒子結點次序，否則為無序樹森林：m>=0棵互不相交樹的集合其它表示方法：1.(A(B(L,E),C(F),D(G(I),H))2.類似于

2、書籍的目錄表示法。高度定義為層數(shù)或?qū)訑?shù)－1，都可以；本書定義為層數(shù)。ABCDEFGHIL高度為4、度為3的樹樹和森林ADT5.1:樹的ADT數(shù)據(jù)及關系:具有相同數(shù)據(jù)類型的數(shù)據(jù)元素或結點的有限集合。樹T的二元組形式為：T＝（D，R）其中D為樹T中結點的集合，R為樹中結點之間關系的集合。D＝{Root}∪DF其中，Root為樹T的根結點，DF為樹T的根Root的子樹集合。R＝{，i＝1，2，…，m}其中，ri是樹T的根結點Root的子樹Ti的根結點。操作:Constructor：前提：已知根結點的數(shù)據(jù)元素之值。結果：創(chuàng)建一棵樹。Getroot:前

3、提：已知一棵樹。.結果：得到樹的根結點。FirstChild：前提：已知樹中的某一指定結點p。結果：得到結點p的第一個兒子結點。NextChild：前提：已知樹中的某一指定結點p和它的一個兒子結點u。結果：得到結點p的兒子結點u的下一個兄弟結點v。例：結點總數(shù)為3時的所有二叉樹的樹的形狀二叉樹的定義空或有一個根，根有左子樹、右子樹；而左右子樹本身又是二叉樹。和樹的區(qū)別：可為空左右子樹有序，不可顛倒BCDEFL例：二叉樹二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有2i-1個結點BCDEFLA1層：結點個數(shù)21-1=20個2層：結點個數(shù)22-1=21個3層：結點個

4、數(shù)23-1=22個證：k=1時成立，設k=i-1時成立則當k=i時在二叉樹的第i層上至多有2i-1-1*2=2i-1個結點性質(zhì)2：高度為k的二叉樹至多有2k-1個結點證：利用性質(zhì)1，將第1層至第k層的最多的結點數(shù)進行相加：1+2+22+…………+2k-2+2k-1=2k-1性質(zhì)3：二叉樹的葉子結點數(shù)n0等于度為2的結點數(shù)n2+1證：設度為1的結點數(shù)為n1，樹枝的總數(shù)為B則：B=n-1=n0+n1+n2-1又B=n1+2×n2；原命題得證。CEFLA完全二叉樹BCDEFLAPSQRUBCDEFLAPSQRXUWV滿二叉樹:每層結點數(shù)最多完全二叉樹:1、滿二叉樹2

5、、從滿二叉樹最底層從右向左依次去掉若干結點形成的性質(zhì)4：具有n個結點的完全二叉樹高度為log2n+1證：根據(jù)性質(zhì)2和完全二叉樹的定義：設其高度為k2k-1-1

6、n)。2：對任何一個編號為j的結點而言，它的父親結點的的編號為j/2。根結點無父結點。證：對編號歸納121110987654321二叉樹的順序存儲一般情況：ABCDEFGHILA1-1B92C53D6-1E-1-1F-1-1G87H-1-1I-1-1L-140123456789rightleftdata應用范圍：適用于二叉樹上的結點個數(shù)已知，或不支持動態(tài)存儲分配的高級語言。二叉樹的順序存儲特殊情況：完全二叉樹A23B45C67D89E100F00G00H00I00L00012345678910rightleftdata應用范圍：適用于完全二叉樹，且結點個數(shù)已知

7、。DCGEFBAHILABCDEFGHI0123456789L二叉樹的順序存儲特殊情況：若不是完全二叉樹，許多數(shù)據(jù)場為空，不合算。如下例所示：考慮浪費空間最多的情況，是一種什么情況？浪費2^k-1–k個單元AB∧D∧∧∧HI0123456789DBAHI二叉樹的鏈接存儲僅定義結點的類型即可。結點之間的關系通過指針實現(xiàn)。ABCDEFGHILdataleftright標準形式：（二叉鏈表）廣義標準形式：（三叉鏈表）dataleftrightParent二叉樹的鏈接存儲例：A∧B/∧∧∧∧∧∧CDEFGGFDCBAE二叉樹的ADTtemplate

8、e>classBinaryTree;/