數(shù)據(jù)結(jié)構(gòu)樹和二叉樹演示文稿

數(shù)據(jù)結(jié)構(gòu)PPT樹和二叉樹演示文稿目前一頁\總數(shù)一百零一頁\編于十四點數(shù)據(jù)結(jié)構(gòu)PPT樹和二叉樹目前二頁\總數(shù)一百零一頁\編于十四點6.1樹的定義和基本術(shù)語

什么是樹？樹是由n(n≥0)個結(jié)點的有限集合。如果n=0，稱為空樹；如果n>0，則

有且僅有一個特定的稱之為根(Root)的結(jié)點，它只有直接后繼，但沒有直接前驅(qū)；當n>1，除根以外的其它結(jié)點劃分為m(m>0)個互不相交的有限集T1,T2,…,Tm，其中每個集合本身又是一棵樹，并且稱為根的子樹(SubTree)。目前三頁\總數(shù)一百零一頁\編于十四點T={A，B，C，D，E，F(xiàn)，G，H，I，J，K，L，M}A是根，其余結(jié)點可以劃分為3個互不相交的集合：T1={B，E，F(xiàn)，K，L}T2={C，G}T3={D，H，I，J，M}這些集合中的每一集合都本身又是一棵樹，它們是A的子樹。對于T1，B是根，其余結(jié)點可以劃分為2個互不相交的集合：T11={E，K，L}T12={F}T11，T12是B的子樹。HBAJFEDKLCMIG樹的示例目前四頁\總數(shù)一百零一頁\編于十四點1.樹中只有根結(jié)點沒有前趨；

2.除根外，其余結(jié)點都有且僅一個前趨；3.樹的結(jié)點，可以有零個或多個后繼；

4.除根外的其它結(jié)點，都存在唯一條從根到該結(jié)點的路徑；5.樹是一種分支結(jié)構(gòu)。HBAJFEDKLCMIG樹的邏輯結(jié)構(gòu)特點目前五頁\總數(shù)一百零一頁\編于十四點樹可表示具有分支結(jié)構(gòu)關(guān)系的對象例1.家族族譜設(shè)某家庭有13個成員A、B、C、D、E、F、G、H、I、J、K、L、M，他們之間的關(guān)系可如圖所示的樹表示。例2.單位行政機構(gòu)的組織關(guān)系HBAJFEDKLCMIG樹的應(yīng)用目前六頁\總數(shù)一百零一頁\編于十四點樹是常用的數(shù)據(jù)組織形式

有些應(yīng)用中數(shù)據(jù)元素之間并不存在分支結(jié)構(gòu)關(guān)系，但是為了便于管理和使用數(shù)據(jù)，將它們用樹的形式來組織。

例3.計算機的文件系統(tǒng)

不論是DOS文件系統(tǒng)還是window文件系統(tǒng)，所有的文件是用樹的形式來組織的。文件夾1文件夾2文件1文件2文件夾11文件夾11文件11文件12C樹的應(yīng)用目前七頁\總數(shù)一百零一頁\編于十四點樹的結(jié)點：包含一個數(shù)據(jù)元素的內(nèi)容及若干指向子樹的分支。孩子結(jié)點：結(jié)點的子樹的根稱為該結(jié)點的孩子；如E是B的孩子。雙親結(jié)點：B結(jié)點是A結(jié)點的孩子，則A結(jié)點是B結(jié)點的雙親；如B是E的雙親。兄弟結(jié)點：同一雙親的孩子結(jié)點；如H、I、J互為兄弟。堂兄結(jié)點：同一層上結(jié)點；如G與E、F、H、I、J互為堂兄。祖先結(jié)點：結(jié)點的祖先是從根到該結(jié)點所經(jīng)分支上的所有結(jié)點；如H的祖先為A、D。子孫結(jié)點：以某結(jié)點為根的子樹中的任一結(jié)點稱為該結(jié)點的子孫；如A的子孫為B、C、D、E、F、G、H、I、J、K、L、M。HBAJFEDKLCMIG基本術(shù)語目前八頁\總數(shù)一百零一頁\編于十四點結(jié)點的度：結(jié)點子樹的個數(shù)；如D的度為3。葉子結(jié)點：也叫終端結(jié)點，是度為0的結(jié)點；如K、L、F、G、M、I、J。分支結(jié)點：度不為0的結(jié)點；如A、B、C、D結(jié)點層次：根結(jié)點的層定義為1，根的孩子為第二層結(jié)點，依此類推。樹的高度：樹中結(jié)點的最大層次；如圖所示樹的高度為4。樹的度：樹中各結(jié)點的度的最大值；如圖所示樹的度為3。森林：m(m>=0)棵互不相交的樹的集合；HBAJFEDKLCMIG基本術(shù)語目前九頁\總數(shù)一百零一頁\編于十四點線性結(jié)構(gòu)第一個數(shù)據(jù)元素（無前驅(qū)）；最后一個數(shù)據(jù)元素（無后繼）；其它數(shù)據(jù)元素（一個前驅(qū)、一個后繼）。樹型結(jié)構(gòu)根結(jié)點（無前驅(qū)）；多個葉子結(jié)點（無后繼）；其它數(shù)據(jù)元素（一個前驅(qū)、多個后繼）。樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點對比目前十頁\總數(shù)一百零一頁\編于十四點6.2.1二叉樹的定義或為空樹，或由根及至多兩棵互不相交的左子樹、右子樹構(gòu)成(即不存在度大于2的結(jié)點)，并且左、右子樹本身也是二叉樹。說明：1.二叉樹中每個結(jié)點最多有兩棵子樹，二叉樹每個結(jié)點度小于等于2；2.左、右子樹不能顛倒——有序樹；3.二叉樹是遞歸結(jié)構(gòu)，在二叉樹的定義中又用到了二叉樹的概念。BADCFEG6.2二叉樹目前十一頁\總數(shù)一百零一頁\編于十四點φ(a)(b)(c)(d)(e)(a)空樹(b)只含根結(jié)點(c)右子樹為空樹(d)左右子樹均不為空樹(e)左子樹為空樹LLRR二叉樹的形態(tài)目前十二頁\總數(shù)一百零一頁\編于十四點性質(zhì)1 在二叉樹的第i層上至多有2i-1個結(jié)點。(i≥

1)

[證明用歸納法]證明：當i=1時，只有根結(jié)點，2i-1=20=1。假設(shè)對所有j，1≤j﹤i，命題成立，即第j層上至多有2j-1個結(jié)點。由歸納假設(shè)第i-1層上至多有2i-2個結(jié)點。由于二叉樹的每個結(jié)點的度至多為2，故在第i層上的最大結(jié)點數(shù)為第i-1層上的最大結(jié)點數(shù)的2倍，即2×2i-2=2i-1。6.2.2二叉樹的性質(zhì)目前十三頁\總數(shù)一百零一頁\編于十四點性質(zhì)2 深度為k的二叉樹至多有2k-1個結(jié)點(k≥1)。證明：由性質(zhì)1可見，深度為k的二叉樹的最大結(jié)點數(shù)為

＝20+21+…+2k-1=2k-1＝6.2.2二叉樹的性質(zhì)目前十四頁\總數(shù)一百零一頁\編于十四點性質(zhì)3對任何一棵二叉樹T，如果其葉結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0＝n2＋1。證明：設(shè)二叉樹中度為1的結(jié)點數(shù)為n1，二叉樹中總結(jié)點數(shù)為：n＝n0＋n1＋n2

二叉樹中的分支數(shù)，除根結(jié)點外，其余結(jié)點都有一個進入分支，設(shè)B為二叉樹中的分支總數(shù)，則有：n＝B＋1。由于這些分支都是由度為1和2的結(jié)點射出的，所以有：B＝n1+2×n2;n＝B＋1＝n1＋2×n2＋1得到：n0＝n2＋16.2.2二叉樹的性質(zhì)目前十五頁\總數(shù)一百零一頁\編于十四點滿二叉樹：深度為k的二叉樹，有2k-1個結(jié)點則稱為滿二叉樹；完全二叉樹：如果深度為k、由n個結(jié)點的二叉樹中個結(jié)點能夠與深度為k的順序編號的滿二叉樹從1到n標號的結(jié)點相對應(yīng)，則稱為完全二叉樹。完全二叉樹的特點是：1.所有的葉結(jié)點都出現(xiàn)在第k層或k－1層。2.對任一結(jié)點，如果其右子樹的最大層次為l，則其左子樹的最大層次為l或l＋1。兩種特殊的二叉樹目前十六頁\總數(shù)一百零一頁\編于十四點6217543891011131415126217543891011122154367216543非完全二叉樹完全二叉樹滿二叉樹兩種特殊的二叉樹目前十七頁\總數(shù)一百零一頁\編于十四點性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為

log2n

+1。證明：設(shè)完全二叉樹的深度為k，則根據(jù)性質(zhì)2和完全二叉樹的定義有 2k-1-1<n≤2k-1或2k-1

≤n<2k取對數(shù)k-1<log2n≤k，又k是整數(shù)，因此有k=log2n＋16.2.2二叉樹的性質(zhì)目前十八頁\總數(shù)一百零一頁\編于十四點性質(zhì)5：如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號(從第1層到第log2n+1層，每層從左到右)，則對任一結(jié)點i(1≤i≤n)，有：

1.如果i＝1，則結(jié)點i無雙親，是二叉樹的根；如果i>1，則其雙親是結(jié)點i/2。

2.如果2i>n，則結(jié)點i為葉子結(jié)點，無左孩子；否則，其左孩子是結(jié)點2i。

3.如果2i＋1>n，則結(jié)點i無右孩子；否則，其右孩子是結(jié)點2i＋1。6.2.2二叉樹的性質(zhì)目前十九頁\總數(shù)一百零一頁\編于十四點證明：此性質(zhì)可采用數(shù)學(xué)歸納法證明。因為1與2、3是相對應(yīng)的，所以只需證明2和3。當i=1時，根據(jù)結(jié)點編號方法可知，根的左、右孩子編號分別是2和3，結(jié)論成立。假定i-1時結(jié)論成立，即結(jié)點i-1的左右孩子編號滿足：LCHILD(i-1)=2(i-1)；RCHILD(i-1)=2(i-1)+1通過完全二叉樹可知，結(jié)點i或者與結(jié)點i-1同層且緊靠其右，或者結(jié)點i-1在某層最右端，而結(jié)點i在其下一層最左端。但是，無論如何，結(jié)點i的左孩子的編號都是緊接著結(jié)點i-1的右孩子的編號，故：LCHILD(i)=RCHILD(i-1)+1=2i；RCHILD(i)=LCHILD(i)+1=2i+1命題成立。6.2.2二叉樹的性質(zhì)目前二十頁\總數(shù)一百零一頁\編于十四點分析：根據(jù)完全二叉樹的結(jié)構(gòu)和編號規(guī)則，在i的左孩子前面的兩個結(jié)點是結(jié)點i-1的左、右孩子，由歸納假設(shè)有：結(jié)點i-1的左孩子為2(i-1)，右孩子為2(i-1)+1。…...…...i與i+1同層…...…...i-12(i-1)2(i-1)+1i2i2i+1…...…...…...…...i與i+1不同層6.2.2二叉樹的性質(zhì)i2i2i+1i-12i-22i-1目前二十一頁\總數(shù)一百零一頁\編于十四點最后證明結(jié)論1。當i=1時，顯然根結(jié)點無雙親；當i＞1時，結(jié)點i可能是其雙親x的左孩子，也可能是右孩子，若是左孩子，由結(jié)論2知，x的左孩子應(yīng)為2x，即2x=i，x=i/2；若是右孩子，由結(jié)論3知，x的右孩子應(yīng)為2x+1，即2x+1=i，x=(i-1)/2。故i的雙親為└i/2┘證畢。6.2.2二叉樹的性質(zhì)目前二十二頁\總數(shù)一百零一頁\編于十四點順序存儲結(jié)構(gòu)所謂順序存儲結(jié)構(gòu)，就是用一組連續(xù)的存儲單元存儲二叉樹的數(shù)據(jù)元素，結(jié)點在這個序列中的相互位置能反映出結(jié)點之間的邏輯關(guān)系。二叉樹中結(jié)點之間的關(guān)系就是雙親結(jié)點與左右孩子結(jié)點間的關(guān)系。因此，必須把二叉樹的所有結(jié)點安排成為一個恰當?shù)男蛄小＞唧w定義如下：#defineMAX-TREE-SIZE100TElemTypeSqBiTree[MAX-TREE-SIZE];

6.2.3二叉樹的存儲結(jié)構(gòu)目前二十三頁\總數(shù)一百零一頁\編于十四點通常是按照二叉樹結(jié)點從上至下、從左到右的順序存儲，但這樣結(jié)點在存儲位置上的前驅(qū)后繼關(guān)系并不一定就是它們在邏輯上的鄰接關(guān)系。依據(jù)二叉樹的性質(zhì)，完全二叉樹和滿二叉樹采用順序存儲比較合適，樹中結(jié)點的序號可以唯一地反映出結(jié)點之間的邏輯關(guān)系，這樣既能夠最大可能地節(jié)省存儲空間，又可以利用數(shù)組元素的下標值確定結(jié)點在二叉樹中的位置，以及結(jié)點之間的關(guān)系。二叉樹的順序存儲結(jié)構(gòu)目前二十四頁\總數(shù)一百零一頁\編于十四點FBAGEDCHIJKL例如：bt[3]的雙親為└3/2┘=1，即在bt[1]中；其左孩子在bt[2i]=bt[6]中；其右孩子在bt[2i+1]=bt[7]中。如何反映結(jié)點之間的邏輯關(guān)系？A1B2C3D4E5F6G7H8I9J10K11L12完全二叉樹的順序表示目前二十五頁\總數(shù)一百零一頁\編于十四點一般二叉樹也按完全二叉樹形式存儲，只有增添一些并不存在的空結(jié)點(用?表示，?表示該處沒有元素存在，僅僅為了好理解)，使之成為一棵完全二叉樹的形式，然后再用一維數(shù)組順序存儲。A1B2C3D4?5E6F7G8H9?10?11?12?13I14J15EBAFDCGHIJ?????例如對于B結(jié)點而言：bt[2]的雙親為└1/2┘=1，即在bt[1]中(為A)；其左孩子在bt[2i]=bt[4]中(為D)；其右孩子在bt[2i+1]=bt[5]中(為?)。一般二叉樹的順序表示目前二十六頁\總數(shù)一百零一頁\編于十四點這種存儲結(jié)構(gòu)適合于完全二叉樹，既不浪費存儲空間，又能很快確定結(jié)點的存放位置、以及結(jié)點的雙親和左右孩子的存放位置，但對一般二叉樹，可能造成存儲空間的浪費。例如，深度為k，且只有k個結(jié)點的右單支樹(每個非葉結(jié)點只有右孩子)，也需2k-1個單元，即有(2k-1)-k個單元被浪費。12k順序存儲的優(yōu)缺點目前二十七頁\總數(shù)一百零一頁\編于十四點所謂鏈式存儲是指，用鏈表來表示一棵二叉樹，即用鏈來指示著元素的邏輯關(guān)系。通常采用二叉鏈表來存儲。鏈表中每個結(jié)點由三個域組成，除了數(shù)據(jù)域外，還有兩個指針域，分別用來給出該結(jié)點左右孩子所在的結(jié)點的存儲地址。其定義如下：typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;鏈式存儲結(jié)構(gòu)目前二十八頁\總數(shù)一百零一頁\編于十四點^D

AB^C^^E^^F^Tlchilddatarchild結(jié)點結(jié)構(gòu)BADCEF二叉鏈表目前二十九頁\總數(shù)一百零一頁\編于十四點ABCDEFG^^^^^^^^^三叉鏈表圖示BACDEFG三叉鏈表lchilddata結(jié)點結(jié)構(gòu)parentrchild目前三十頁\總數(shù)一百零一頁\編于十四點6.3遍歷二叉樹和線索二叉樹6.3.1遍歷二叉樹定義：所謂遍歷二叉樹，就是遵從某種次序，訪問二叉樹中的所有結(jié)點，使得每個結(jié)點僅被訪問一次。這里所提的“訪問”的含義很廣，可以是查詢、修改、輸出某元素的值，以及對元素作某種運算等等。但要求這種訪問不破壞它原來的數(shù)據(jù)結(jié)構(gòu)。遍歷一個線性結(jié)構(gòu)很簡單，只須從開始結(jié)點出發(fā)，順序掃描每個結(jié)點即可。但對二叉樹這樣的非線性結(jié)構(gòu)，每個結(jié)點可能有兩個后繼結(jié)點，因此需要尋找一種規(guī)律來系統(tǒng)訪問樹中的各結(jié)點。如何訪問二叉樹的每個結(jié)點且每個結(jié)點僅被訪問一次？目前三十一頁\總數(shù)一百零一頁\編于十四點由于二叉樹的定義是遞歸的，它是由三個基本單元組成，即根結(jié)點、左子樹和右子樹。因此，遍歷一棵非空二叉樹的問題可以分解為三個子問題：訪問根結(jié)點、遍歷左子樹、遍歷右子樹，只要依次遍歷這三部分，就可以遍歷整個二叉樹。由于實際問題一般都是要求左子樹較右子樹先遍歷，分別稱為先序遍歷、中序遍歷和后序遍歷。令L，R，D分別代表二叉樹的左子樹、右子樹、根結(jié)點，則有DLR、LDR、LRD三種遍歷規(guī)則。遞歸實現(xiàn)方法目前三十二頁\總數(shù)一百零一頁\編于十四點若二叉樹非空，則：1.訪問根結(jié)點2.先序遍歷左子樹3.先序遍歷右子樹BADCDLRADLRDLR>B>>D>>CDLR得到的序列為：ABDC先序遍歷二叉樹目前三十三頁\總數(shù)一百零一頁\編于十四點StatusPreOrderTraverse(BiTreeT){

//采用二叉鏈表存貯二叉樹if(T){//若二叉樹不為空Visit(T->data)；//訪問根結(jié)點

PreOrderTraverse(T->lchild);//先序遍歷T的左子樹PreOrderTraverse(T->rchild);//先序遍歷T的右子樹

}//PreOrderTraverse先序遍歷二叉樹算法實現(xiàn)目前三十四頁\總數(shù)一百零一頁\編于十四點viodpre(bintT){if(T)visite(T->data);pre(T->lchild);pre(T->rchild);}先序遍歷二叉樹算法實現(xiàn)BADC主程序Pre(T)TAvisite(A);pre(TL);TBvisite(B);pre(TL);T>返回pre(TR);TDvisite(D);pre(TL);T>返回pre(TR);T>返回pre(TR);TCvisite(C);pre(TL);T>返回pre(TR);T>返回先序序列：ABDC目前三十五頁\總數(shù)一百零一頁\編于十四點若二叉樹非空，則：1.中序遍歷左子樹2.訪問根結(jié)點3.中序遍歷右子樹BADCLDRBLDRLDR>A>>D>>CLDR得到的序列為：BDAC中序遍歷二叉樹目前三十六頁\總數(shù)一百零一頁\編于十四點若二叉樹非空，則：1.后序遍歷左子樹2.訪問根結(jié)點3.后序遍歷右子樹BADCLRDLRDLRD>A>>D>>CLRDB得到的序列為：DBCA后序遍歷二叉樹目前三十七頁\總數(shù)一百零一頁\編于十四點*-bca這一路線正是從根結(jié)點開始沿左子樹深入下去，當深入到最左端，無法再深入下去時，則返回，再逐一進入剛才深入時遇到結(jié)點的右子樹，再進行如此的深入和返回，直到最后從根結(jié)點的右子樹返回到根結(jié)點為止。先序遍歷是在深入時遇到結(jié)點就訪問，中序遍歷是在從左子樹返回時遇到結(jié)點訪問，后序遍歷是在從右子樹返回時遇到結(jié)點訪問。在這一過程中，返回結(jié)點的順序與深入結(jié)點的順序相反，即后深入先返回，正好符合棧結(jié)構(gòu)后進先出的特點。因此，可以用棧來幫助實現(xiàn)這一遍歷路線。三種遍歷過程示意圖例-*abc目前三十八頁\總數(shù)一百零一頁\編于十四點先序遍歷：從二叉樹根結(jié)點開始，沿左子樹一直走到末端(左子樹為空)為止，在走的過程中，訪問所遇結(jié)點，并依次把所遇結(jié)點進棧，當左子樹為空時，從棧頂退出某結(jié)點，并將指針指向該結(jié)點的右子樹。如此重復(fù)，直到棧為空或指針為空止。中序遍歷：從二叉樹根結(jié)點開始，沿左子樹一直走到末端(左子樹為空)為止，在走的過程中，把依次遇到的結(jié)點進棧，待左子樹為空時，從棧中退出結(jié)點并訪問，然后再轉(zhuǎn)向它的右子樹。如此重復(fù)，直到?？栈蛑羔槥榭罩埂７沁f歸實現(xiàn)方法目前三十九頁\總數(shù)一百零一頁\編于十四點statusInOrderTraverse(BiTreeT){InitStack(S);Push(S,T);//根結(jié)點進棧while(!StackEmpty(S){while(GetTop(S,p)&&p)Push(S,p->lchild);Pop(S,p);//空指針退棧if(!StackEmpty(S)){Pop(S,p);Visit(p->data);Push(S,p->rchild);}}returnOK;}中序遍歷的非遞歸算法目前四十頁\總數(shù)一百零一頁\編于十四點中序遍歷的非遞歸算法演示ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)目前四十一頁\總數(shù)一百零一頁\編于十四點中序遍歷的非遞歸算法演示ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B訪問：C(4)目前四十二頁\總數(shù)一百零一頁\編于十四點中序遍歷的非遞歸算法演示pABCDEFGiP->A訪問：CB(5)ABCDEFGiP->AP->D訪問：CBp(6)目前四十三頁\總數(shù)一百零一頁\編于十四點中序遍歷的非遞歸算法演示ABCDEFGiP->AP->DP->E訪問：CBp(7)ABCDEFGiP->AP->D訪問：CBEp(8)目前四十四頁\總數(shù)一百零一頁\編于十四點中序遍歷的非遞歸算法演示ABCDEFGiP->AP->DP->G訪問：CBEP=NULL(9)ABCDEFGiP->AP->D訪問：CBEGp(10)目前四十五頁\總數(shù)一百零一頁\編于十四點中序遍歷的非遞歸算法演示ABCDEFGiP->A訪問：CBEGDp(11)ABCDEFGiP->AP->F訪問：CBEGDp(12)目前四十六頁\總數(shù)一百零一頁\編于十四點中序遍歷的非遞歸算法演示ABCDEFGiP->A訪問：CBEGDFp=NULL(13)ABCDEFGi訪問：CBEGDFAp(14)目前四十七頁\總數(shù)一百零一頁\編于十四點中序遍歷的非遞歸算法演示ABCDEFGi訪問：CBEGDFAp=NULL(15)目前四十八頁\總數(shù)一百零一頁\編于十四點后序遍歷：利用棧來實現(xiàn)二叉樹的后序遍歷要比先序和中序遍歷復(fù)雜得多，在后序遍歷中，當搜索指針指向某一個結(jié)點時，不能馬上進行訪問，而先要遍歷左子樹，所以此結(jié)點應(yīng)先進棧保存，當遍歷完它的左子樹后，再次回到該結(jié)點，還不能訪問它，還需先遍歷其右子樹，所以該結(jié)點還必須再次進棧，只有等它的右子樹遍歷完后，再次退棧時，才能訪問該結(jié)點。為了區(qū)分同一結(jié)點的兩次進棧，引入一個棧次數(shù)的標志，元素第一次進棧標志為1，第二次進標志為2，當退出的元素標志為2時，訪問結(jié)點。非遞歸實現(xiàn)方法目前四十九頁\總數(shù)一百零一頁\編于十四點voidleaf(BiTreeT){//采用二叉鏈表存貯二叉樹，n為全局變量，用于累加二叉樹的葉子結(jié)點個數(shù)，本算法在先序遍歷二叉樹的過程中，統(tǒng)計葉子結(jié)點的個數(shù)，初始化n=0if(T){

if(T->lchild==NULL&&T->rchild==NULL)n+=1;

//若T所指結(jié)點為葉子結(jié)點則計數(shù)leaf(T->lchild);leaf(T->rchild);}//if}//leaf例1編寫求二叉樹的葉子結(jié)點個數(shù)的算法目前五十頁\總數(shù)一百零一頁\編于十四點voidleaf(BiTreeT){If(T){

if(T->lchild==NULL&&T->rchild==NULL)n+=1;leaf(T->lchild);leaf(T->rchild);}//if}//leafStatusPreOrderTraverse(BiTreeT){

if(T){

Visit(T->data)；

PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}//PreOrderTraverse訪問結(jié)點時統(tǒng)計葉子結(jié)點的個數(shù)訪問結(jié)點時調(diào)用visit()比較先序遍歷和計算葉子結(jié)點算法相同點和不同點目前五十一頁\總數(shù)一百零一頁\編于十四點分析：本算法要借用隊列來完成，其基本思想是，若二叉樹非空，先將根結(jié)點進隊列。然后進入循環(huán)：只要隊列不空，就出隊列，遍歷該結(jié)點，然后判斷出隊列的結(jié)點是否有左孩子和右孩子，如有就讓左、右孩子進隊列。例2按層次遍歷二叉樹的算法目前五十二頁\總數(shù)一百零一頁\編于十四點voidlayorder(BiTreeT){InitQueue(Q)//隊列初始化if(T!=NULL){EnQueue(Q,T);//入隊列while(notQueueEmpty(Q))//若隊列非空{(diào)DeQueue(Q,p);//出隊visite(p->data);if(p->lchild!=NULL)EnQueue(Q,p->lchild);//入隊列if(p->rchild!=NULL)EnQueue(Q,p->rchild);//入隊列}}}例2按層次遍歷二叉樹的算法目前五十三頁\總數(shù)一百零一頁\編于十四點輸入：二叉樹的先序序列結(jié)果：二叉樹的二叉鏈表問題：遍歷操作訪問二叉樹的每個結(jié)點，而且每個結(jié)點僅被訪問一次。是否可利用遍歷，建立二叉鏈表的所有結(jié)點并完成相應(yīng)結(jié)點的鏈接？基本思想：輸入在空子樹處添加字符￠的二叉樹的按先序遍歷的順序，建立二叉鏈表的所有結(jié)點并完成相應(yīng)結(jié)點鏈接。BADCEF￠￠￠￠￠￠￠在空子樹處添加￠的二叉樹的先序序列：ABD￠F￠￠E￠￠C￠￠例3建立二叉鏈表目前五十四頁\總數(shù)一百零一頁\編于十四點StatusCreateBiTree(BiTree&T){//輸入(在空子樹處添加字符￠的二叉樹的)先序序列(設(shè)元素均為字符)scanf(&ch);if(ch==‘￠’)T=NULL;//若ch==‘￠’則表示空子樹else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;//建立(根)結(jié)點

CreateBiTree(T->lchild);//遞歸構(gòu)造左子樹鏈表CreateBiTree(T->rchild);//遞歸構(gòu)造右子樹鏈表}returnOK;}//CreateBiTree建立二叉鏈表算法目前五十五頁\總數(shù)一百零一頁\編于十四點建立二叉鏈表算法BACDAB

C

D

ABCDATBCD^^^^^目前五十六頁\總數(shù)一百零一頁\編于十四點分析：由先序序列和中序序列的定義可知，先序序列中第一個結(jié)點必為根結(jié)點，而在中序序列中，根結(jié)點剛好是左、右子樹的分界點，因此，可按如下方法建立二叉樹：1.用先序序列的第一個結(jié)點作為根結(jié)點;2.在中序序列中查找根結(jié)點的位置，并以此為界將中序序列劃分為左、右兩個序列(左、右子樹);3.根據(jù)左、右子樹的中序序列中的結(jié)點個數(shù)，將先序序列去掉根結(jié)點后的序列劃分為左、右兩個序列，它們分別是左、右子樹的先序序列;

4.對左、右子樹的先序序列和中序序列遞歸地實施同樣方法，直到所得左、右子樹為空。例4由二叉樹先序和中序序列建立一個唯一二叉樹目前五十七頁\總數(shù)一百零一頁\編于十四點如一棵二叉樹的先序序列為ABDGHCEFI，中序序列為GDHBAECIF，試建立該二叉樹。構(gòu)造過程：由先序可知A為根結(jié)點，再根據(jù)中序序列知：由GDHB是左子樹，ECIF是右子樹。A為根結(jié)點ABDGHCEFIGDHBAECIFB為左子樹的根結(jié)點BDGHGDHB一直進行下去……AG,D,H,B組成左子樹E,C,I,F組成右子樹示例分析目前五十八頁\總數(shù)一百零一頁\編于十四點abcdefgcbdaegfaabbccddeeffggabcdefg^^^^^^^^先序序列中序序列目前五十九頁\總數(shù)一百零一頁\編于十四點遍歷是二叉樹最基本最常用的操作。

1.對二叉樹所有結(jié)點做某種處理可在遍歷過程中實現(xiàn)；

2.查找二叉樹某個結(jié)點，可通過遍歷實現(xiàn)；與線性表相比，對二叉樹的遍歷存在如下問題：1.遍歷算法要復(fù)雜的多，費時的多；2.為查找二叉樹中某結(jié)點在某種遍歷下的后繼，必須從根開始遍歷，直到找到該結(jié)點及后繼；如果能將二叉樹線性化，就可以減化遍歷算法，提高遍歷速度。6.3.2線索二叉樹目前六十頁\總數(shù)一百零一頁\編于十四點定義：當以二叉鏈表作為存儲結(jié)構(gòu)時，只能找到結(jié)點的左右孩子的信息，而不能直接得到結(jié)點的任一序列的前驅(qū)與后繼信息，這種信息只有在遍歷的動態(tài)過程中才能得到，為了能保存所需的信息，可增加標志域。0lchild域指示結(jié)點的左孩子1lchild域指示結(jié)點的前驅(qū)0rchild域指示結(jié)點的右孩子1rchild域指示結(jié)點的后繼以這種結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，叫做線索鏈表，其中指向結(jié)點前驅(qū)與后繼的指針叫做線索。加上線索的二叉樹稱之為線索二叉樹。LTag=RTag=一、線索二叉樹定義目前六十一頁\總數(shù)一百零一頁\編于十四點利用現(xiàn)有的空指針域，每個n個結(jié)點的二叉鏈表，有n+1個空指針域，故可利用這些的空指針域存放結(jié)點的前趨和后繼指針。(n個結(jié)點共有2n個鏈域，而每個結(jié)點(除根結(jié)點外)都有一個分支指向，則共有n-1個分支，其中每個分支占有一個鏈域，所以空鏈域為2n-(n-1)=n+1。)若結(jié)點有左子樹，則左指針lchild指示其左孩子(LTag=0)；否則，令左指針指示其前驅(qū)(LTag=1)；若結(jié)點有右子樹，則右指針rchild指示其右孩子(RTag=0)；否則，令右指針指示其后繼(RTag=1)。二、如何保存遍歷過程中得到的信息？目前六十二頁\總數(shù)一百零一頁\編于十四點typedefenumPointerTeg{Link,Thread};

//Link==0:指針，Thread==1:線索typedefstructBiThrNod{TElemTypedata;structBiThrNode*lchild,*rchild;//左右指針PointerTegLTag,RTag;//左右標志}BiThrNode,*BiThrTree;三、線索鏈表的類型描述lchildLTagdataRTagrchild目前六十三頁\總數(shù)一百零一頁\編于十四點(以中序遍歷為例)查找任意結(jié)點的前驅(qū)結(jié)點如果該結(jié)點的左標志為1，那么其左指針域所指向的結(jié)點便是它的前驅(qū)結(jié)點；如果該結(jié)點的左標志為0，表明該結(jié)點有左孩子，根據(jù)中序遍歷的定義，它的前驅(qū)結(jié)點是以該結(jié)點的左孩子為根結(jié)點的子樹的最右結(jié)點，即沿著其左子樹的右指針鏈向下查找，當某結(jié)點的右標志為1時，它就是所要找的前驅(qū)結(jié)點。中序線索二叉樹中序：DBGJEACHLKFI四、如何找結(jié)點的前驅(qū)和后繼BACEFDGJHIKL目前六十四頁\總數(shù)一百零一頁\編于十四點中序線索二叉樹中序：DBGJEACHLKFI四、如何找結(jié)點的前驅(qū)和后繼(續(xù))(以中序遍歷為例)查找任意結(jié)點的后繼結(jié)點對任意結(jié)點p，若右標志為1，則rchild指向該結(jié)點的后繼；若右標志為0，則rchild指向該結(jié)點的右孩子，此時，應(yīng)從右孩子開始，沿左指針前進，直到找到?jīng)]有左孩子的結(jié)點s(Ltag=1)，則s就是p的后繼，即后繼是中序遍歷右子樹時，訪問的第一個結(jié)點。BACEFDGJHIKL目前六十五頁\總數(shù)一百零一頁\編于十四點按不同的方式遍歷二叉樹所得到的線索二叉樹是不相同的。BADCE五、遍歷線索二叉樹ABDCET先序序列：ABCDE先序線索二叉樹00001111^11ABDCET中序序列：BCAED中序線索二叉樹00001111^11^ABDCET后序序列：CBEDA后序線索二叉樹0000111111^目前六十六頁\總數(shù)一百零一頁\編于十四點BADCEABDCET0000111111

01中序序列：BCAED中序線索二叉樹五、遍歷線索二叉樹(續(xù))帶頭結(jié)點的線索二叉樹在存儲線索二叉樹時往往增設(shè)一頭結(jié)點，其數(shù)據(jù)域不存放信息，其左指針域指向二叉樹的根結(jié)點，右指針域指向某種遍歷時訪問的最后一個結(jié)點。而原二叉樹在某序遍歷下的第一個結(jié)點的前驅(qū)線索和最后一個結(jié)點的后繼線索都指向該頭結(jié)點。注：可從第一個結(jié)點起順后繼進行遍歷，也可以從最后一個結(jié)點起順前驅(qū)進行遍歷。目前六十七頁\總數(shù)一百零一頁\編于十四點

找遍歷的第一個結(jié)點左子樹上處于“最左下”(沒有左子樹)的結(jié)點。

不斷地找遍歷到的結(jié)點的后繼結(jié)點，直到樹中各結(jié)點都遍歷到為止，結(jié)束若無右子樹，則為后繼線索所指結(jié)點；否則為對其右子樹進行中序遍歷時訪問的第一個結(jié)點。遍歷線索二叉樹步驟(以中序遍歷為例)目前六十八頁\總數(shù)一百零一頁\編于十四點voidInOrderTraverse_Thr(BiThrTreeT){p=T->lchild;while(p!=T){while(p->LTag==0)p=p->lchild;Visit(p->data));while(p->RTag==1&&p->rchild!=T){p=p->rchild;Visit(p->data);}p=p->rchild;}}//InOrderTraverse_Thr中序線索二叉樹中序：DBGJEACHLKFI中序遍歷線索二叉樹算法實現(xiàn)TBACEFDGJHIKL目前六十九頁\總數(shù)一百零一頁\編于十四點建立線索二叉樹，或者說對二叉樹線索化，實質(zhì)上是遍歷一棵二叉樹。在遍歷過程中訪問結(jié)點操作visit()是檢查當前結(jié)點的左、右指針域是否為空，如果為空，將空的lchild改為結(jié)點的直接前驅(qū)，將空的rchild改為結(jié)點的直接后繼。而對于非空指針，仍然指向孩子結(jié)點。為了記下遍歷過程中訪問結(jié)點的先后關(guān)系，附設(shè)指針pre始終指向剛剛被訪問過的結(jié)點,若p指針指向當前訪問的結(jié)點，則pre指向它的前驅(qū)。六、如何建立線索二叉樹？目前七十頁\總數(shù)一百零一頁\編于十四點StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))exit(OVERFLOW);Thrt->LTag=0;Thrt->RTag=1;Thrt->rchild=Thrt;//添加頭結(jié)點if(!T)Thrt->lchild=Thrt;else{Thrt->lchild=T;pre=Thrt;

InThreading(T);

pre->rchild=Thrt;//處理最后一個結(jié)點pre->RTag=1;Thrt->rchild=pre;}returnOK;}//InOrderThreadingThrt

01LR算法實現(xiàn)(1)：目前七十一頁\總數(shù)一百零一頁\編于十四點voidleaf(BiTreeT){if(T){

leaf(T->lchild);

if(T->lchild==NULL&&T->rchild==NULL)n+=1;leaf(T->rchild);}}StatusPreOrderTraverse(BiTreeT){

if(T){PreOrderTraverse(T->lchild);

Visit(T->data)；

PreOrderTraverse(T->rchild);}算法實現(xiàn)(2)：目前七十二頁\總數(shù)一百零一頁\編于十四點voidInThreading(BiThrTreep){if(p){

InThreading(p->lchild);//左子樹線索化

if(!p->lchild)//建前驅(qū)線索{p->LTag=1;p->lchild=pre;}if(!pre->rchild)//建后繼線索{pre->RTag=1;pre->rchild=p;}pre=p;//保持pre指向p的前驅(qū)

InThreading(p->rchild);//右子樹線索化}//if}//InThreading相當于遍歷算法中的visit()算法實現(xiàn)(2)：目前七十三頁\總數(shù)一百零一頁\編于十四點6.4.1樹的存貯結(jié)構(gòu)一、雙親表示法：以一組連續(xù)的空間存儲樹的結(jié)點，通過保存每個結(jié)點的雙親結(jié)點的位置，表示樹中結(jié)點之間的結(jié)構(gòu)關(guān)系。其類型定義如下：#defineMAX_TREEE_SIZE100typedefstructPTNode{ElemTypedata;intparent;//雙親位置域}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;//結(jié)點數(shù)}Ptree;特點：找雙親容易，找孩子難ARDCFEGBHKA0B0C0D1E1F3G6H6R-1K60123456789數(shù)組下標6.4樹和森林目前七十四頁\總數(shù)一百零一頁\編于十四點通過保存每個結(jié)點的孩子結(jié)點的位置，表示樹中結(jié)點之間的結(jié)構(gòu)關(guān)系。多重鏈表：每個結(jié)點有多個指針域，分別指向其子樹的根。結(jié)點同構(gòu)：結(jié)點的指針個數(shù)相等，為樹的度d。結(jié)點不同構(gòu)：結(jié)點指針個數(shù)不等，為該結(jié)點的度d。datachild1child2……childddatadegreechild1child2……childd二、孩子表示法目前七十五頁\總數(shù)一百零一頁\編于十四點孩子鏈表：其主體是一個與結(jié)點個數(shù)一樣大小的一維數(shù)組，數(shù)組的每一個元素有兩個域組成，一個域用來存放結(jié)點信息，另一個用來存放指針，該指針指向由該結(jié)點孩子組成的單鏈表的首位置。單鏈表的結(jié)構(gòu)也由兩個域組成，一個存放孩子結(jié)點在一維數(shù)組中的序號，另一個是指針域，指向下一個孩子。每個結(jié)點的孩子結(jié)點用單鏈表存儲，再用含n個元素的結(jié)構(gòu)數(shù)組指向每個孩子鏈表。二、孩子表示法目前七十六頁\總數(shù)一百零一頁\編于十四點ARDCFEGBHKAB^CD^E^FG^H^RK^0123456789數(shù)組下標125^43^789^6^特點：找孩子容易，找雙親難孩子鏈表表示法圖示目前七十七頁\總數(shù)一百零一頁\編于十四點typedefstructCTNode{//孩子結(jié)點intchild;structCTNode*next;}*ChildPtr;typedefstruct{ElemTypedata;ChildPtrfirstchild;//孩子鏈表頭指針}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;//結(jié)點數(shù)和根的位置}CTree;孩子鏈表表示法類型定義目前七十八頁\總數(shù)一百零一頁\編于十四點用二叉鏈表作樹的存儲結(jié)構(gòu)，鏈表中每個結(jié)點的兩個指針域分別指向其第一個孩子結(jié)點和下一個兄弟結(jié)點。特點：操作容易，但破壞了樹的層次。孩子兄弟表示法類型定義：typedefstructCSNode{ElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;三、孩子兄弟表示法目前七十九頁\總數(shù)一百零一頁\編于十四點ARDCFEGBHKR^AD^

B^

E^∧C

^F

∧G^

H^

K^^利用樹的孩子兄弟鏈表這種存儲結(jié)構(gòu)便于實現(xiàn)各種樹的操作。例如找某結(jié)點的第i個孩子，則只要先從左指針域中找到第1個孩子結(jié)點上，然后沿著孩子結(jié)點的next域連續(xù)走i-1步便可找到第i個孩子。如增加一個parent域，則也能方便實現(xiàn)求雙親的操作。三、孩子兄弟表示法目前八十頁\總數(shù)一百零一頁\編于十四點一.樹轉(zhuǎn)變?yōu)槎鏄浼泳€：在兄弟之間加一連線；抹線：對每個結(jié)點，除了其左孩子外，去除其與其余孩子之間的關(guān)系；旋轉(zhuǎn)：以樹的根結(jié)點為軸心，將整樹順時針轉(zhuǎn)45°。6.4.2樹、森林與二叉樹轉(zhuǎn)換目前八十一頁\總數(shù)一百零一頁\編于十四點BAEDGHCFIBAEDGHCFIBAEDGHCFIBAEDGHCFIBAEDGHCFI由上面的轉(zhuǎn)換可以看出，在二叉樹中，左分支上的各結(jié)點在原來的樹中是父子關(guān)系，而右分支上的各結(jié)點在原來的樹中是兄弟關(guān)系。由于樹的根結(jié)點沒有兄弟，所以變換后的二叉樹的根結(jié)點的右孩子必為空。樹轉(zhuǎn)變?yōu)槎鏄鋵崿F(xiàn)過程目前八十二頁\總數(shù)一百零一頁\編于十四點由森林的概念可知，森林是若干棵樹的集合，只要將森林中各棵樹的根視為兄弟，每棵樹又可以用二叉樹表示，這樣，森林也同樣可以用二叉樹表示。具體的方法如下：將各棵樹分別轉(zhuǎn)換成二叉樹；將每棵樹的根結(jié)點用線相連；以第一棵樹根結(jié)點為二叉樹的根，再以根結(jié)點為軸心，順時針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)。二、森林轉(zhuǎn)換成二叉樹目前八十三頁\總數(shù)一百零一頁\編于十四點HIGJBADCEFHIGJBADCEFHIGJBADCEFHIGMBADCEF森林轉(zhuǎn)變?yōu)槎鏄鋵崿F(xiàn)過程目前八十四頁\總數(shù)一百零一頁\編于十四點加線：若p結(jié)點是雙親結(jié)點的左孩子，則將p的右孩子，右孩子的右孩子，……，沿分支找到的所有右孩子，都與p的雙親用線連起來；抹線：抹掉原二叉樹中雙親與右孩子之間的連線；調(diào)整：將結(jié)點按層次排列，形成樹結(jié)構(gòu)。BAEDGHCFIBAEDGHCFIBAEDGHCFI注：該二叉樹的右子樹為空三、二叉樹轉(zhuǎn)換成樹目前八十五頁\總數(shù)一百零一頁\編于十四點抹線：將二叉樹中根結(jié)點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹。還原：將孤立的二叉樹還原成樹。HIGMBADCEFHIGJBADCEF注：該二叉樹的右子樹一定不為空四、二叉樹轉(zhuǎn)換成森林目前八十六頁\總數(shù)一百零一頁\編于十四點在樹和森林中，一個結(jié)點可能有兩棵以上的子樹，所以不宜討論它們的中序遍歷，即樹和森林只有先序遍歷和后序遍歷。1.樹的先序遍歷若樹非空，則先訪問根結(jié)點，然后依次先序遍歷各子樹。先序遍歷：ABEFIGCDHJKLNOM2.樹的后序遍歷若樹非空，則依次后序遍歷各子樹，最后訪問根結(jié)點。后序遍歷：EIFGBCJKNOLMHDA6.4.3樹和森林的遍歷ACBDEFGIHJKLMNO目前八十七頁\總數(shù)一百零一頁\編于十四點3.森林的先序遍歷若森林非空，則先訪問森林中第一棵樹的根結(jié)點，再先序遍歷第一棵樹各子樹，接著先序遍歷第二棵樹、第三棵樹、…、直到最后一棵樹。遍歷結(jié)果：ABCDEFGHIJ4.森林的后序遍歷按順序后序遍歷森林中的每一棵樹。遍歷結(jié)果：BCDAFEHJIG6.4.3樹和森林的遍歷HIGJBADCEF目前八十八頁\總數(shù)一百零一頁\編于十四點

一、基本概念路徑和路徑長度：在一棵樹中，從一個結(jié)點往下可以達到的孩子或子孫結(jié)點之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點的層數(shù)為1，則從根結(jié)點到第L層結(jié)點的路徑長度為L-1。結(jié)點的權(quán)及帶權(quán)路徑長度：若將樹中結(jié)點賦給一個有著某種含義的數(shù)值，則這個數(shù)值稱為該結(jié)點的權(quán)。從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積稱為結(jié)點的帶權(quán)路徑長度。6.6赫夫曼樹及其應(yīng)用目前八十九頁\總數(shù)一百零一頁