第六章樹和二叉樹

第六章樹和二叉樹2樹的類型定義二叉樹的類型定義二叉樹的存儲(chǔ)結(jié)構(gòu)遍歷二叉樹和線索二叉樹樹和森林主要內(nèi)容3社會(huì)的組織結(jié)構(gòu)家族的族譜計(jì)算機(jī)中的目錄組織描述層次結(jié)構(gòu)，是一種一對(duì)多的邏輯關(guān)系樹型結(jié)構(gòu)實(shí)例41.樹的類型定義樹的定義(Tree)樹是由n(n>0)個(gè)結(jié)點(diǎn)組成的有限集合如果n=0，稱為空樹如果n>0，則有一個(gè)特定的稱之為根(root)的結(jié)點(diǎn)，它只有直接后繼，但沒有直接前驅(qū)除根以外的其它結(jié)點(diǎn)劃分為m(m>=0)個(gè)互不相交的有限集合T0,T1,…,Tm-1，每個(gè)集合又是一棵樹，并且稱之為根的子樹遞歸定義5ABCDEFGHIJKLM根子樹樹(邏輯上)的特點(diǎn)每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼6ABCDEFGHIJKLM樹的基本概念

結(jié)點(diǎn)分支結(jié)點(diǎn)葉子結(jié)點(diǎn)根結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)結(jié)點(diǎn)度不為0的結(jié)點(diǎn)度為0的結(jié)點(diǎn)7樹的基本概念

結(jié)點(diǎn)的度和樹的度結(jié)點(diǎn)的度即結(jié)點(diǎn)擁有的子樹個(gè)數(shù)。樹的度是樹內(nèi)各結(jié)點(diǎn)的度的最大值。ABCDEFGHIJKLM32132001000008樹的基本概念

結(jié)點(diǎn)的層次和樹的深度(高度)結(jié)點(diǎn)的層次從根開始定義。根位于第1層，根的孩子位于第2層，余則類推。樹的深度即樹中結(jié)點(diǎn)的最大層次。第1層第2層第3層第4層樹的高度為4ABCDEFGHIJKLM9樹的基本概念

孩子、雙親、兄弟結(jié)點(diǎn)的子樹的根稱為結(jié)點(diǎn)的孩子。該結(jié)點(diǎn)稱為其孩子的雙親。同一雙親的孩子間互稱兄弟。ABCDEFGHIJKLM孩子雙親10樹的基本概念

祖先、子孫結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)；以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱該結(jié)點(diǎn)的子孫。ABCDEFGHIJKLMABCDEFGHIJKLM11樹的基本概念森林：m(m>=0)棵互不相交的樹的集合BEFKLDHMIJCGACGBDEFKLHMIJ12樹的有序性：若樹中結(jié)點(diǎn)的子樹的相對(duì)位置不能隨意改變，則稱該樹為有序樹，否則稱該樹為無序樹。樹的基本概念==有序樹無序樹ABDCACBD13有序樹中最左邊的子樹的根稱其第一個(gè)孩子，最右邊的子樹的根稱其最后一個(gè)孩子。老大老二老三

有序樹的第一個(gè)孩子和最后一個(gè)孩子樹的基本概念A(yù)BDC14樹的常用表示法AEFBIJGHCDFGIJABCEDH凹入表示嵌套集合廣義表A(B(E,F),C,D(G(J),H,I))ABEFCDGJHI15為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)“叉”的樹？樹太一般，子樹的個(gè)數(shù)無限制，表示困難二叉樹的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)可以證明，所有樹都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹，不失一般性。2.二叉樹16二叉樹的基本定義二叉樹的定義是n≥0個(gè)結(jié)點(diǎn)的有窮集合該集合或者為空、或者由一個(gè)根結(jié)點(diǎn)和兩個(gè)分別稱為左子樹和右子樹的互不相交的二叉樹組成。當(dāng)集合為空時(shí)，稱該二叉樹為空二叉樹。邏輯結(jié)構(gòu)：一對(duì)二(1:2)基本特征:樹的一種每個(gè)結(jié)點(diǎn)最多有2棵子樹(即度<=2)BCADE17二叉樹與樹的區(qū)別

樹至少應(yīng)有一個(gè)結(jié)點(diǎn)，而二叉樹可以為空；樹的孩子結(jié)點(diǎn)沒有限制，而二叉樹中的每個(gè)結(jié)點(diǎn)最多有2個(gè)孩子結(jié)點(diǎn)；樹的子樹沒有順序，但如果二叉樹的根結(jié)點(diǎn)只有一棵子樹，必須明確區(qū)分它是左子樹還是右子樹，因?yàn)閮烧邔?gòu)成不同形態(tài)的二叉樹。18二叉樹的五種基本形態(tài)2.只有樹根A1.空樹ΦBADE3.只有左子樹4.只有右子樹BADEBCADE5.左右子樹都有19問：具有3個(gè)結(jié)點(diǎn)的二叉樹可能有幾種不同形態(tài)？有5種Φ二叉樹的基本形態(tài)201.度為2的樹是二叉樹。2.度為2的有序樹是二叉樹。3.具有三個(gè)結(jié)點(diǎn)的樹可以有以下五種形態(tài)：1種21二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層最多有2i-1個(gè)結(jié)點(diǎn)(i>=1)證明：當(dāng)i=1時(shí)，顯然成立假設(shè)當(dāng)i=k時(shí)，也成立，即第k層最多2k-1個(gè)結(jié)點(diǎn)當(dāng)i=k+1時(shí)，由于二叉樹的每個(gè)結(jié)點(diǎn)最多有2個(gè)孩子，所以第k+1層最多有2*2k-1=2(k+1)-1個(gè)結(jié)點(diǎn)故對(duì)于任意i(i>=1)，二叉樹的第i層最多有2i-1個(gè)結(jié)點(diǎn)提問：第i層上至少有

個(gè)結(jié)點(diǎn)？122二叉樹的性質(zhì)性質(zhì)2：深度為k的二叉樹最多有2k-1個(gè)結(jié)點(diǎn)(k>=1)證明：由性質(zhì)1可知：第i層最多有2i-1個(gè)結(jié)點(diǎn)所以總的結(jié)點(diǎn)數(shù)最多為k=4123423二叉樹的性質(zhì)性質(zhì)3：對(duì)任何一棵二叉樹T，若葉子結(jié)點(diǎn)數(shù)(即度為0的結(jié)點(diǎn)數(shù))為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1證明：總結(jié)點(diǎn)數(shù)n=n0+n1+n2設(shè)分支數(shù)為B，則n=B+1又B=n1+2n2結(jié)點(diǎn)無外乎度為0、1、2三種情況”五個(gè)手指四個(gè)叉”除了樹根，其余每個(gè)結(jié)點(diǎn)”上方”都有一個(gè)分支度為2的結(jié)點(diǎn)“下方”有2個(gè)分支度為1的結(jié)點(diǎn)“下方”有1個(gè)分支度為0的結(jié)點(diǎn)“下方”有0個(gè)分支解方程組： 得：n0=n2+124樹的葉子數(shù)與其它結(jié)點(diǎn)數(shù)的關(guān)系設(shè)度為m的樹中度為0,1,2,…,m的結(jié)點(diǎn)數(shù)分別為n0,n1,n2,…,nm，結(jié)點(diǎn)總數(shù)為n，分支數(shù)為B，則下面二式成立n=n0+n1+n2+…+nm(1)n=B+1=n1+2n2+…+mnm+1(2)由(1)和(2)得葉子結(jié)點(diǎn)數(shù)

n0=1+n2+2n3+…+(m-1)nm

25滿二叉樹(FullBinaryTree)深度為k，結(jié)點(diǎn)數(shù)為2k-1即結(jié)點(diǎn)數(shù)達(dá)到最大值特殊形態(tài)的二叉樹完全二叉樹(CompleteBinaryTree)樹中每個(gè)結(jié)點(diǎn)的編號(hào)（從上到下，從左到右）都與一個(gè)同深度的滿二叉樹的結(jié)點(diǎn)一一對(duì)應(yīng)葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)完全二叉樹和和滿二叉樹相比，就是最底層最右邊連續(xù)缺少一些結(jié)點(diǎn)26特殊形態(tài)的二叉樹2h-1結(jié)論：深度為h且具有2h-1個(gè)結(jié)點(diǎn)的二叉樹為滿二叉樹。思考：深度為h的完全二叉樹至少有多少個(gè)結(jié)點(diǎn)？27二叉樹的性質(zhì)性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的非空完全二叉樹的深度為證明：設(shè)深度為k，則：2k-1-1<n<=2k-1由此推出：2k-1<=n<2k兩邊求對(duì)數(shù)：k-1<=log2n<k所以：24-123-128二叉樹的性質(zhì)性質(zhì)5：若將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào)：(1)若i=1，則結(jié)點(diǎn)i是樹根，無雙親 若i>1，則其雙親是結(jié)點(diǎn)i/2(2)若2i>n，則結(jié)點(diǎn)i無左孩子(即i為葉結(jié)點(diǎn))，否則其左孩子為2i(3)若2i+1>n，則結(jié)點(diǎn)i無右孩子，否則其右孩子為2i+1由(2)(3)可以推導(dǎo)出(1)理解：結(jié)點(diǎn)i如果有左孩子的話，其編號(hào)應(yīng)該為2i如果2i>n，則左孩子不存在29二叉樹的性質(zhì)性質(zhì)6：具有n個(gè)結(jié)點(diǎn)的非空二叉樹共有n-1個(gè)分支。證明：除了根結(jié)點(diǎn)以外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親結(jié)點(diǎn)，即每個(gè)結(jié)點(diǎn)與其雙親結(jié)點(diǎn)之間僅有一個(gè)分支存在，因此，具有n個(gè)結(jié)點(diǎn)的非空二叉樹的分支總數(shù)為n-1。301.n(n>0)個(gè)結(jié)點(diǎn)的樹的高度最低是多少？最高是多少？2.n(n>0)個(gè)結(jié)點(diǎn)的二叉樹的高度最低是多少？最高是多少？推論n個(gè)結(jié)點(diǎn)的樹：高最多為n，最低為2。n個(gè)結(jié)點(diǎn)的二叉樹：高最多為n(單支樹)，最低為log2n+1(完全二叉樹)。自測(cè)題31自測(cè)題3.有關(guān)二叉樹下列說法正確的是()A.二叉樹的度為2B.一棵二叉樹的度可以小于2C.二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2D.二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為24.已知一棵完全二叉樹的第6層(設(shè)根是第1層)有8個(gè)葉結(jié)點(diǎn)，則該完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多是()

A.39B.52C.111D.11932完全二叉樹性質(zhì)的推論n個(gè)結(jié)點(diǎn)的完全二叉樹中：度為1的結(jié)點(diǎn)數(shù)為(n+1)%2度為0的結(jié)點(diǎn)數(shù)為(n+1)/2度為2的結(jié)點(diǎn)數(shù)為(n+1)/2-1編號(hào)最大的分支結(jié)點(diǎn)是n/2編號(hào)最小的葉子結(jié)點(diǎn)是n/2+1具有n0個(gè)葉子結(jié)點(diǎn)的完全二叉樹中共有2n0個(gè)結(jié)點(diǎn)或2n0-1個(gè)結(jié)點(diǎn)。33一棵完全二叉樹有1000個(gè)結(jié)點(diǎn)，則它必有

個(gè)葉子結(jié)點(diǎn)；有

個(gè)度為2的結(jié)點(diǎn)；有

個(gè)結(jié)點(diǎn)只有非空左子樹；有

個(gè)結(jié)點(diǎn)只有非空右子樹。(1000+1)/2=500葉子總數(shù)-1=49910因?yàn)樽詈笠粋€(gè)結(jié)點(diǎn)坐標(biāo)是偶數(shù)，所以必為左子樹。有1個(gè)結(jié)點(diǎn)只有非空左子樹，有0個(gè)結(jié)點(diǎn)只有非空右子樹。自測(cè)題34自測(cè)題5.一棵124個(gè)葉結(jié)點(diǎn)的完全二叉樹，最多有()個(gè)結(jié)點(diǎn)。A.247B.248C.249D.250E.2516.已知一棵完全二叉樹中共有626個(gè)結(jié)點(diǎn)，葉子結(jié)點(diǎn)的個(gè)數(shù)應(yīng)為()。A.311B.312C.313D.314E.其他35自測(cè)題7.一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為()。A.11B.10C.11至1025之間D.10至1024之間8.已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該樹有______個(gè)葉子結(jié)點(diǎn)。1236二叉樹本節(jié)小結(jié)二叉樹的概念和類型定義注意和樹的類型定義的對(duì)比二叉樹的性質(zhì)要求自己能推導(dǎo)、應(yīng)用、推廣373.二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu)用一維數(shù)組來表示#defineMAX_TREE_SIZE100typedefdatatypeSqBiTree[MAX_TREE_SIZE];SqBiTreeBt;按照滿二叉樹的順序存放38完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)

根據(jù)完全二叉樹的性質(zhì)5，對(duì)于深度為h的完全二叉樹，將樹中所有結(jié)點(diǎn)的數(shù)據(jù)信息按編號(hào)順序一次存儲(chǔ)到數(shù)組BT[1…2h-1]中，由于編號(hào)與數(shù)組下標(biāo)一一對(duì)應(yīng)，該數(shù)組就是該完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)。1234567891012345678910下標(biāo)：BT[3]的雙親為3/2=1，即在BT[1]中；其左孩子在BT[2i]=BT[6]中；其右孩子在BT[2i+1]=BT[7]中。39一般二叉樹的順序存儲(chǔ)結(jié)構(gòu)123456789101234567891012345678910BT[5]的雙親為5/2=2，即在BT[2]中，與實(shí)際矛盾！其左孩子在BT[2i]=BT[10]中，實(shí)際應(yīng)在BT[9]中。

對(duì)于一般二叉樹，需要在二叉樹中“增添”一些實(shí)際上并不存在的“虛結(jié)點(diǎn)”(可以認(rèn)為這些結(jié)點(diǎn)的數(shù)據(jù)信息為空)，使其在形式上成為一棵“完全二叉樹”；然后按照完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)的構(gòu)造方法將所有結(jié)點(diǎn)的信息依次存放到數(shù)組BT[1..2h-1]中。4012340678900120015123456789101112131415BT[6]的雙親為6/2=3，即在BT[3]中！其左孩子在BT[2i]=BT[12]中；其右孩子在BT[2i+1]=BT[13]中，而BT[13]＝0，表示無右孩子。41一般二叉樹的順序存儲(chǔ)結(jié)構(gòu)極端情形：?jiǎn)沃渖疃葹閗的二叉樹，最少只有k個(gè)結(jié)點(diǎn)卻需要2k-1個(gè)存儲(chǔ)單元137深度增加一層10增加1倍之多103000700000001542二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈表data為數(shù)據(jù)域；lchild與rchild分別為指向左、右子樹的指針域。3.二叉樹的存儲(chǔ)結(jié)構(gòu)lchilddatarchilddatalchildrchild43二叉鏈表示例說明：一個(gè)二叉鏈表由根指針T唯一確定。若二叉樹為空，則T=NULL；若結(jié)點(diǎn)的某個(gè)孩子不存在，則相應(yīng)的指針為空。具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，共有2n個(gè)指針域。其中只有n-1個(gè)用來指示結(jié)點(diǎn)的左、右孩子，其余的n+1個(gè)指針域?yàn)榭铡?4二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)三叉鏈表比二叉鏈表的鏈結(jié)點(diǎn)多增加了一個(gè)指向雙親結(jié)點(diǎn)的指針域parent。3.二叉樹的存儲(chǔ)結(jié)構(gòu)lchilddataparentrchildparentdataleftchildrightchild45三叉鏈表示例46二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)的定義

typedefintdatatype;typedefstructnode { datatypedata; structnode*lchild,*rchild; }bitree;二叉樹的鏈表表示lchilddatarchild47二叉樹的存儲(chǔ)結(jié)構(gòu)本節(jié)小結(jié)各種存儲(chǔ)結(jié)構(gòu)注意各自的優(yōu)缺點(diǎn)比如順序存儲(chǔ)空間浪費(fèi)大二叉鏈表不能直接找到父結(jié)點(diǎn)48練習(xí)1

已知非空二叉樹采用廣義表形式作為輸入，請(qǐng)寫一算法，建立該二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)。49關(guān)于廣義表形式表示二叉樹的說明1.約定表中的一個(gè)字母代表一個(gè)結(jié)點(diǎn)的數(shù)據(jù)信息。2.每個(gè)根結(jié)點(diǎn)作為由子樹構(gòu)成的表的名字放在表的前面。3.每個(gè)結(jié)點(diǎn)的左子樹和右子樹之間用逗號(hào)分開，若只有右子樹而無左子樹，則逗號(hào)不能省略。4.在整個(gè)廣義表的末尾加一個(gè)特殊符號(hào)（如@）作為結(jié)束標(biāo)志。ABCDFGE50二叉樹的廣義表表示方法二叉樹@defi=“@”空樹Φ51大寫字母二叉樹@defi=“A”只有樹根A二叉樹的廣義表表示方法52大寫字母(二叉樹,)二叉樹#二叉樹defi=“A(B,C(D,E))”ACDEB二叉樹的廣義表表示方法531.若取到的元素為字母，則如下建立一個(gè)新結(jié)點(diǎn)，若該結(jié)點(diǎn)為根結(jié)點(diǎn)，則將該結(jié)點(diǎn)的地址送T。若該結(jié)點(diǎn)不是二叉樹的根結(jié)點(diǎn)，則將該結(jié)點(diǎn)作為左孩子（若標(biāo)志為1）或者右孩子（若標(biāo)志為2）鏈接到其雙親結(jié)點(diǎn)上（雙親結(jié)點(diǎn)的地址在棧頂）。2.若取到的元素為左括號(hào)（，則表明一個(gè)子表開始，將標(biāo)志置為1，同時(shí)將前面那個(gè)結(jié)點(diǎn)的地址進(jìn)棧。3.若取到的元素為右括號(hào)），則表明一個(gè)子表結(jié)束，作退棧操作。4.若取到的元素為逗號(hào)，則表明以左孩子為根的子樹處理完畢，接著應(yīng)該處理以右孩子為根的子樹，將標(biāo)志置為2。如此處理廣義表中每一個(gè)元素，直到取到結(jié)束符號(hào)@為止。54練習(xí)2

已知具有n個(gè)結(jié)點(diǎn)的非空完全二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，結(jié)點(diǎn)的數(shù)據(jù)信息依次存放于數(shù)組BT[1..n]中。請(qǐng)寫出由此產(chǎn)生該二叉樹二叉鏈表結(jié)構(gòu)的算法。55建立根結(jié)點(diǎn)以BT的第2個(gè)元素開始取一個(gè)元素建立一個(gè)新結(jié)點(diǎn)保存新結(jié)點(diǎn)的地址找到新結(jié)點(diǎn)的雙親結(jié)點(diǎn)的地址確定新結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左（或右）孩子將新結(jié)點(diǎn)插入二叉鏈表中保存在一個(gè)數(shù)組中利用二叉樹的性質(zhì)556設(shè)置一個(gè)一維數(shù)組PTR存放結(jié)點(diǎn)所在鏈結(jié)點(diǎn)的地址建立根結(jié)點(diǎn)，并將根結(jié)點(diǎn)的地址保存在數(shù)組PTR中從數(shù)組BT的第2個(gè)元素開始依次取結(jié)點(diǎn)的信息BT[i]，每取得一個(gè)結(jié)點(diǎn)做如下操作：1.建立一個(gè)新結(jié)點(diǎn)，并將結(jié)點(diǎn)地址保存在PTR[i]中；2.建立新結(jié)點(diǎn)的雙親結(jié)點(diǎn)的位置(地址)；3.確定新結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子或右孩子；4.將新結(jié)點(diǎn)作為雙親結(jié)點(diǎn)的左孩子或右孩子插入二叉鏈表中。位置j=i/2地址PTR[j]若i%2==0，則新結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子；當(dāng)i%2!=0，則新結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的右孩子；57ijj=i/2當(dāng)i%2==0時(shí)，i是j的左孩子當(dāng)i%2!=0時(shí)，i是j的右孩子58#defineMaxNode100/*MaxNode>=n*/bitree*BUILDBTREE(datatypeBT[],intn){bitree*T,*PTR[MaxNode];inti,j;PTR[1]=(bitree*)malloc(sizeof(bitree));PTR[1]->data=BT[1];PTR[1]->lchild=NULL;PTR[1]->rchild=NULL;T=PTR[1];/*建立根結(jié)點(diǎn)*/59for(i=2;i<=n;i++){PTR[i]=(bitree*)malloc(sizeof(bitree));PTR[i]->data=BT[i];PTR[i]->lchild=NULL;PTR[i]->rchild=NULL;j=i/2;/*計(jì)算雙親結(jié)點(diǎn)的位置j*/if(i%2==0)PTR[j]->lchild=PTR[i];/*BT[i]是雙親的左孩子*/elsePTR[j]->rchild=PTR[i];/*BT[i]是雙親的右孩子*/}returnT;}60

已知非空二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，結(jié)點(diǎn)的數(shù)據(jù)信息依次存放于數(shù)組BT[1..n]中。請(qǐng)寫出由此產(chǎn)生該二叉樹二叉鏈表結(jié)構(gòu)的算法。練習(xí)361一、二叉樹的遍歷

按照一定的順序(原則)對(duì)二叉樹中每一個(gè)結(jié)點(diǎn)都訪問一次(僅訪問一次)，得到一個(gè)由該二叉樹的所有結(jié)點(diǎn)組成的序列，這一過程稱為二叉樹的遍歷。訪問的含義包括查詢、打印、計(jì)算、修改等對(duì)結(jié)點(diǎn)的操作。4.二叉樹的遍歷62常用的遍歷方法：

1.前(先)序遍歷DLR2.中序遍歷LDR3.后序遍歷LRD4.按層次遍歷遍歷規(guī)則注：指訪問的結(jié)點(diǎn)D是先于子樹出現(xiàn)還是后于子樹出現(xiàn)。以根結(jié)點(diǎn)為參照系根左子樹右子樹63原則若被遍歷的二叉樹為空，則空操作否則1.訪問根結(jié)點(diǎn)2.以前序遍歷原則遍歷根結(jié)點(diǎn)的左子樹3.以前序遍歷原則遍歷根結(jié)點(diǎn)的右子樹二、前序遍歷(PreorderTraversal)遞歸64BACFDEGHA遍歷序列：BCFDEGH(1)訪問根結(jié)點(diǎn)；(2)前序遍歷左子樹；(3)前序遍歷右子樹。二、前序遍歷(PreorderTraversal)65三、中序遍歷(InorderTraversal)原則若被遍歷的二叉樹為空，則空操作否則1.以中序遍歷原則遍歷根結(jié)點(diǎn)的左子樹2.訪問根結(jié)點(diǎn)3.以中序遍歷原則遍歷根結(jié)點(diǎn)的右子樹遞歸66遍歷序列：(1)中序遍歷左子樹；(2)訪問根結(jié)點(diǎn)；(3)中序遍歷右子樹。BACFDEGHABCFDEGH三、中序遍歷(InorderTraversal)67四、后序遍歷(PostorderTraversal)原則若被遍歷的二叉樹為空，則空操作否則1.以后序遍歷原則遍歷根結(jié)點(diǎn)的左子樹2.以后序遍歷原則遍歷根結(jié)點(diǎn)的右子樹3.訪問根結(jié)點(diǎn)遞歸68遍歷序列：(1)后序遍歷左子樹；(2)后序遍歷右子樹；(3)訪問根結(jié)點(diǎn)。BACFDEGHABCFDEGH四、后序遍歷(PostorderTraversal)69二叉樹的其它操作：廣度優(yōu)先遍歷BACFDEGHA遍歷序列：BCFDEGH廣度優(yōu)先遍歷(也叫層次遍歷)(1)按結(jié)點(diǎn)所在層次，由低層向高層依次遍歷；(2)同層按自左向右次序遍歷。70二叉樹的其它操作：廣度優(yōu)先遍歷

二叉樹的層序遍歷算法：

(1)初始化設(shè)置一個(gè)隊(duì)列；

(2)把根結(jié)點(diǎn)指針入隊(duì)列；

(3)當(dāng)隊(duì)列非空時(shí)，循環(huán)執(zhí)行步驟(a)到步驟(c):(a)出隊(duì)列取得一個(gè)結(jié)點(diǎn)指針，訪問該結(jié)點(diǎn)；

(b)若該結(jié)點(diǎn)的左子樹非空，則將該結(jié)點(diǎn)的左子樹指針入隊(duì)列；

(c)若該結(jié)點(diǎn)的右子樹非空，則將該結(jié)點(diǎn)的右子樹指針入隊(duì)列；

(4)結(jié)束。71(1)從根開始：若二叉樹非空，則根入隊(duì)；(2)隊(duì)頭出隊(duì)，并訪問；BA^C^D^E^G^^F^^H^T排隊(duì)處遍歷序列思路：ApBC(3)若當(dāng)前結(jié)點(diǎn)有左子樹，則其左子樹的根入隊(duì)；(4)若當(dāng)前結(jié)點(diǎn)有右子樹，則其右子樹的根入隊(duì)；(5)重復(fù)(2)~(4)，DEpFpGHppp直至隊(duì)空。72算法：StatusLevelOrderTraverse(biTree*T){InitQueue(Q);AddQueue(Q,T);//樹根入隊(duì)

while(!QueueEmpty(Q))//只要隊(duì)列非空

{DeleteQueue(Q,p);//出隊(duì)一個(gè)結(jié)點(diǎn)

if(!Visit(p->data))returnERROR;//訪問之

if(p->lchild)AddQueue(Q,p->lchild);//左孩子入隊(duì)

if(p->rchild)AddQueue(Q,p->rchild);//右孩子入隊(duì)

} returnOK;}73二叉樹的遍歷:算法回憶一下遞歸算法的適用情況(1)問題本身直接用遞歸定義的(2)問題的規(guī)律有遞歸的特點(diǎn)二叉樹及其遍歷是用遞歸定義的用遞歸算法肯定可以解決如果不用遞歸呢？74二叉樹的前序遍歷遞歸算法若二叉樹為空，則算法結(jié)束；否則：(1)訪問根結(jié)點(diǎn)；(2)前序遍歷根結(jié)點(diǎn)的左子樹；(3)前序遍歷根結(jié)點(diǎn)的右子樹。voidPreOrderTraverse(bitree*T){if(T)二叉樹非空

{printf("\t%c\n",T->data);訪問根結(jié)點(diǎn)

PreOrderTraverse(T->lchild);前序遍歷左子樹

PreOrderTraverse(T->rchild);前序遍歷右子樹

}}75二叉樹的中序遍歷遞歸算法若二叉樹為空，則算法結(jié)束；否則：(1)中序遍歷根結(jié)點(diǎn)的左子樹；(2)訪問根結(jié)點(diǎn)；(3)中序遍歷根結(jié)點(diǎn)的右子樹。voidInOrderTraverse(bitree*T){if(T){InOrderTraverse(T->lchild);printf("\t%c\n",T->data);InOrderTraverse(T->rchild);}}76二叉樹的后序遍歷遞歸算法若二叉樹為空，則算法結(jié)束；否則：(1)后序遍歷根結(jié)點(diǎn)的左子樹；(2)后序遍歷根結(jié)點(diǎn)的右子樹；(3)訪問根結(jié)點(diǎn)。voidPostOrderTraverse(bitree*T){if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("\t%c\n",T->data);

}}771.遞歸算法的優(yōu)點(diǎn)(1)問題的數(shù)學(xué)模型或算法設(shè)計(jì)方法本身就是遞歸的，采用遞歸算法來描述它們非常自然；(2)描述直觀，結(jié)構(gòu)清晰、簡(jiǎn)潔；正確性證明比非遞歸算法容易。2.遞歸算法的不足(1)算法的執(zhí)行時(shí)間與空間開銷往往比非遞歸算法要大，當(dāng)問題規(guī)模較大時(shí)尤為明顯；(2)對(duì)算法進(jìn)行優(yōu)化比較困難；(3)分析跟蹤算法的執(zhí)行過程比較麻煩；(4)描述算法的語(yǔ)言不具有遞歸功能時(shí)，算法無法描述。謹(jǐn)慎使用遞歸，因?yàn)樗暮?jiǎn)潔可能會(huì)掩蓋它的低效率。五、遞歸問題的非遞歸算法的設(shè)計(jì)78五、遞歸問題的非遞歸算法的設(shè)計(jì)回顧遍歷的過程(以中序?yàn)槔?1先走到最左2往回訪問父結(jié)點(diǎn)3往右訪問右子樹3.1走到最左3.2回訪父結(jié)點(diǎn)3.3訪問右子樹

...ABCDEFG79二叉樹的遍歷：非遞歸算法ABCDEFG當(dāng)向左/右走到底時(shí)怎么辦？需要返回到祖先哪個(gè)祖先？路過的卻未訪問的最近的祖先這就需要一種機(jī)制能記錄訪問的“歷史信息”:路過卻未訪問的結(jié)點(diǎn)，以便能夠回溯回去這就需要一個(gè)棧存放來這些祖先80EH二叉樹的遍歷：非遞歸算法(1)非空樹從根開始；(2)若當(dāng)前結(jié)點(diǎn)存在，則暫存，p下到左子樹；否則回退→訪問當(dāng)前結(jié)點(diǎn)→p下到右子樹中序遍歷非遞歸思路：BA^C^D^E^G^^F^^H^TpA棧SBDp^p遍歷序列：Dp^pBGp^Gpp^pEp^pHp^pACp^pCFp^pFp^(3)重復(fù)(2)直到p空且?？?1Stack[0..M-1]--保存遍歷過程中結(jié)點(diǎn)的地址；top--棧頂指針，初始為-1；p--遍歷過程中使用的指針變量，初始時(shí)指向根結(jié)點(diǎn)。用自然語(yǔ)言表達(dá)的算法1.若p指向的結(jié)點(diǎn)非空，則將p指的結(jié)點(diǎn)的地址進(jìn)棧，然后，將p指向左子樹的根；2.若p指向的結(jié)點(diǎn)為空，則從棧中退出棧頂元素送p，訪問該結(jié)點(diǎn)，然后，將p指向右子樹的根；重復(fù)上述過程，直到p為空，并且棧也為空。82二叉樹的中序遍歷：非遞歸算法intInOrderT(bitree*T){bitree*p=T;SqStack*S;InitStack(S);//建棧

while(p||!StackEmpty(s))//還有未訪問的

{if(p)//一直向左走到底，路過的所有的根入棧

{Push(S,p);p=p->lchild;//遍歷左子樹}else//p為NULL，說明走到了底

{Pop(S,p);Visit(p->data);//彈出一個(gè)還沒訪問的結(jié)點(diǎn)，訪問之

p=p->rchild;//遍歷右子樹

}}returnOK;}p指向樹根p走到了底，再依次彈出剛才路過卻沒有訪問的結(jié)點(diǎn)，訪問之，然后p向右走83時(shí)間復(fù)雜度n個(gè)結(jié)點(diǎn)，每一個(gè)都要訪問一次顯然時(shí)間復(fù)雜度為O(n)(這里n為結(jié)點(diǎn)數(shù))空間復(fù)雜度不論是遞歸還是非遞歸算法都要用到棧棧的最大深度=樹的深度所有空間復(fù)雜度為O(n)(這里n為樹的深度)二叉樹的遍歷：算法效率84二叉樹的初始化算法的基本思想:創(chuàng)建二叉樹的頭結(jié)點(diǎn)。程序?qū)崿F(xiàn)：voidInitiate(bitree**root){*root=(bitree*)malloc(sizeof(bitree));(*root)->lchild=NULL;(*root)->rchild=NULL;}root是指向根指針的指針85按前序構(gòu)造二叉鏈表例1：按下列次序輸入字符(φ表示空格):ABCφφDEφGφφFφφφA^B^C^D^E^F^^G^二叉鏈表為:例2：HGφFφφMφφrootH^G^M^^F^86按前序構(gòu)造二叉鏈表的算法voidCreateBT(bitree**P){charch;ch=getchar();/*從鍵盤上輸入一個(gè)字符*/if(ch=='')*P=NULL;else{*P=(bitree*)malloc(sizeof(bitree));(*P)->data=ch;CreateBT(&((*P)->lchild));CreateBT(&((*P)->rchild));}}P是指向根指針的指針，*P的值發(fā)生變化后可以返回87前序遍歷序列：A,B,D,K,J,G,C,F,I,E,H中序遍歷序列：D,B,G,J,K,A,F,I,E,C,H后序遍歷序列：D,G,J,K,B,E,I,F,H,C,A按層次遍歷序列：A,B,C,D,K,F,H,J,I,G,E8889前序序列：中序序列：后序序列：ABIFCGDEHFIBCGADEHFIGCBHEDA90利用前序序列和中序序列恢復(fù)二叉樹利用中序序列和后序序列恢復(fù)二叉樹利用前序序列和后序序列恢復(fù)二叉樹前序序列：A,B,D,C后序序列：D,B,C,A91六、由遍歷序列恢復(fù)二叉樹前序序列：

A,B,D,E,J,C,F,I,G中序序列：

D,B,J,E,A,F,I,C,G92已知前序序列和中序序列，恢復(fù)二叉樹在前序序列中尋找根；到中序序列中分左右。規(guī)律已知中序序列和后序序列，恢復(fù)二叉樹在后序序列中尋找根；到中序序列中分左右。93例:已知結(jié)點(diǎn)的前序序列和中序序列分別為：前序序列：ABDEGHCF

中序序列：DBGEHACF求此二叉樹六、由遍歷序列恢復(fù)二叉樹94由已知的前序序列和中序序列構(gòu)造二叉樹的方法ABD前序EGHCFDBG中序EHACFA012345左子樹右子樹左子樹右子樹六、由遍歷序列恢復(fù)二叉樹95ABD前序EGHCFDBG中序EHACFAB01左右左右D由已知的前序序列和中序序列構(gòu)造二叉樹的方法六、由遍歷序列恢復(fù)二叉樹96ABD前序EGHCFDBG中序EHACFBADE01左左右右GH由已知的前序序列和中序序列構(gòu)造二叉樹的方法六、由遍歷序列恢復(fù)二叉樹97ABD前序EGHCFDBG中序EHACFBACFDEGH0右右由已知的前序序列和中序序列構(gòu)造二叉樹的方法六、由遍歷序列恢復(fù)二叉樹98(1)由前序序列得根；(2)在中序序列中查找根，并確定左子樹中結(jié)點(diǎn)個(gè)數(shù)；(3)分別確定左、右子樹的前序序列和中序序列；(4)分別構(gòu)造左、右子樹六、由遍歷序列恢復(fù)二叉樹由已知的前序序列和中序序列構(gòu)造二叉樹的方法99已知二叉樹的1.前序序列ABDFCEHG

中序序列DBFAHECG請(qǐng)構(gòu)造該二叉樹。2.后序序列DMFBHELGCA

中序序列DBMFAHECGL請(qǐng)構(gòu)造該二叉樹。自測(cè)題100

一棵二叉樹的前序、中序和后序序列如下，其中有部分未標(biāo)出，試構(gòu)造出該二叉樹。前序序列為：__CDE_GHI_K中序序列為：CB__FA_JKIG后序序列為：_EFDB_JIH_A自測(cè)題101試找出滿足下列條件的二叉樹1)前序序列與后序序列相同2)中序序列與后序序列相同3)前序序列與中序序列相同4)前序、中序、后序序列均相同5)中序序列與層次遍歷序列相同自測(cè)題102一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是()。A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEGB自測(cè)題103一棵非空的二叉樹的前序序列和后序序列正好相反，則該二叉樹一定滿足()。A.其中任意一個(gè)結(jié)點(diǎn)均無左孩子B.其中任意一個(gè)結(jié)點(diǎn)均無右孩子C.其中只有一個(gè)葉子結(jié)點(diǎn)D.其中度為2的結(jié)點(diǎn)最多為一個(gè)E.空或只有一個(gè)結(jié)點(diǎn)F.高度等于其結(jié)點(diǎn)數(shù)自測(cè)題104注意：一個(gè)二叉樹的遍歷序列不能決定一棵二叉樹，但前序（或后序）和中序遍歷序列的組合可以唯一確定一棵二叉樹。而前序和后序遍歷則不能。口訣：DLR—前序遍歷，即先根再左再右LDR—中序遍歷，即先左再根再右LRD—后序遍歷，即先左再右再根105例6.1給二叉樹中某個(gè)指定結(jié)點(diǎn)插入一個(gè)左結(jié)點(diǎn)

算法思想:

若當(dāng)前結(jié)點(diǎn)(假設(shè)為curr)非空，在curr的左子樹插入元素值為x的新結(jié)點(diǎn)，原curr所指結(jié)點(diǎn)的左子樹成為新插入結(jié)點(diǎn)的左子樹。若插入成功返回新插入結(jié)點(diǎn)的指針，否則返回空指針。二叉樹操作舉例106bitree*InsertLeftNode(bitree*curr,datatypex){bitree*s,*t;if(curr==NULL)returnNULL;t=curr->lchild;s=(bitree*)malloc(sizeof(bitree));s->data=x;s->lchild=t; s->rchild=NULL;

curr->lchild=s; returncurr->lchild;}107算法思想:

若curr非空，刪除curr所指結(jié)點(diǎn)的左子樹。若刪除成功，返回刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)指針，否則返回空指針。例6.2刪除二叉樹中指定結(jié)點(diǎn)的左子樹bitree*DeleteLeftTree(bitree*curr){if(curr==NULL||curr->lchild==NULL)returnNULL;free(curr->lchild);curr->lchild=NULL;returncurr;}108例6.3求二叉樹深度算法思想:

從二叉樹深度的定義可知，二叉樹的深度應(yīng)為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，并將所得的左、右子樹深度的最大值加1。109intBTreeDepth(bitree*BT){intleftdep,rightdep;if(BT==NULL)return(0);//空二叉樹

else{leftdep=BTreeDepth(BT->lchild);rightdep=BTreeDepth(BT->rchild);if(leftdep>rightdep)return(leftdep+1);elsereturn(rightdep+1);}110例6.4統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)（1）算法思想:

中序(或前序或后序)遍歷二叉樹，在遍歷過程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。由此，需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)，并將遍歷算法中“訪問結(jié)點(diǎn)”的操作改為：若是葉子，則計(jì)數(shù)器增1。111intnum=0;//全局變量voidLeafCount(bitree*BT){if(BT){LeafCount(BT->lchild);//中序遍歷左子樹

if(!BT->lchild&&!BT->rchild)num++;//葉子結(jié)點(diǎn)計(jì)數(shù)

LeafCount(BT->rchild);//中序遍歷右子樹

}}112例6.4統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)（2）intleafcount(bitree*BT){if(!BT)return(0);//空樹沒有葉子

else//只有根結(jié)點(diǎn)

if(!BT->lchild&&!BT->rchild)return(1);elsereturn//左子樹葉子數(shù)加上右子樹葉子數(shù)

(leafcount(BT->lchild)+leafcount(BT->rchild));}113例6.5交換所有結(jié)點(diǎn)的左右子樹voidSubtree_Revolute(bitree*T){bitree*p;if(T){p=T->lchild;T->lchild=T->rchild;T->rchild=p;Subtree_Revolute(T->lchild);Subtree_Revolute(T->rchild);}}114例6.6求二叉樹的結(jié)點(diǎn)個(gè)數(shù)intnodecount(bitree*BT){if(BT==NULL)return(0);//空二叉樹

elsereturn(nodecount(BT->lchild)+nodecount(BT->rchild)+1);}115例6.7求二叉樹的非葉子結(jié)點(diǎn)個(gè)數(shù)intnotleafcount(bitree*BT){if(!BT)return(0);//空二叉樹

else//只有根結(jié)點(diǎn)

if(!BT->lchild&&!BT->rchild)return(0);elsereturn(notleafcount(BT->lchild)+notleafcount(BT->rchild)+1);}116例6.8設(shè)一棵二叉樹中各結(jié)點(diǎn)的值互不相同，其前序序列和中序序列分別存于兩個(gè)一維數(shù)組pre[1..n]和mid[1..n]中，試遍寫算法建立該二叉樹的二叉鏈表。117"ABDEGHCF"02134567pre"DBGEHACF"02134567mid1.由前序序列得根2.若序列中多于1個(gè)元素，則在中序序列中查找根（定位根在字符串中第一次出現(xiàn)的位置），并確定左子樹中結(jié)點(diǎn)個(gè)數(shù)；makeT(pre,mid)1184.分別構(gòu)造左、右子樹

r.lchild=makeT(lpre,lmid); r.rchild=makeT(rpre,rmid);3.分別確定左、右子樹的前序序列和中序序列

lpre=pre(1,i-1); rpre=pre(i,n); lmid=mid(0,i-1); rmid=mid(i,m);119

已知具有n個(gè)結(jié)點(diǎn)的完全二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，結(jié)點(diǎn)的數(shù)據(jù)信息依次存放于一維數(shù)組BT[1..n]中，寫出中序遍歷二叉樹的非遞歸算法。120BT[1..6]ABCDEF123456中序序列：DBEAFC121Stack[0..M-1]--保存遍歷過程中結(jié)點(diǎn)的位置；top--棧頂指針，初始為-1；i--遍歷過程中使用的位置變量，初始時(shí)指向根結(jié)點(diǎn)。i=1,BT[1]1.若i指向的結(jié)點(diǎn)非空，則將i進(jìn)棧，然后，將i指向左子樹的根；2.若i指向的結(jié)點(diǎn)為空，則從堆棧中退出棧頂元素送i，訪問該結(jié)點(diǎn)，然后，將i指向右子樹的根；重復(fù)上述過程，直到i為空，并且堆棧也為空。i=2*i;i=2*i+1;122#defineMaxN100voidINORDER(datatypeBT[],intn){intStack[MaxN],i=1,top=-1;if(n>=0){do{while(i<=n){Stack[++top]=i;/*BT[i]的位置進(jìn)棧*/i=i*2;}/*找到i的左孩子的位置*/i=Stack[top--];/*退棧*/VISIT(BT[i]);/*訪問結(jié)點(diǎn)BT[i]*/i=i*2+1;/*找到i的右孩子的位置*/}while(i<n||top>=0);}}123二叉樹的其它操作建議思考以下問題：求二叉樹中只有一個(gè)孩子的結(jié)點(diǎn)個(gè)數(shù)求二叉樹中有兩個(gè)孩子的結(jié)點(diǎn)個(gè)數(shù)復(fù)制一棵二叉樹交換一棵二叉樹的所有左右子樹124二叉樹的操作本節(jié)小結(jié)深度優(yōu)先遍歷（包括前、中、后序）手工能寫出前、中、后序遍歷的結(jié)果要求能夠?qū)懗鲞f歸和非遞歸的算法廣度優(yōu)先遍歷了解其算法：為什么要用隊(duì)列其它操作能把握大致方向：借助深度優(yōu)先遍歷、遞歸、廣度優(yōu)先遍歷等1255.線索二叉樹一、線索二叉樹的提出

二叉樹的任何一種遍歷，其實(shí)質(zhì)均為對(duì)非線性結(jié)構(gòu)的線性化。若將遍歷序列中所體現(xiàn)的結(jié)點(diǎn)間的線性關(guān)系，保存在二叉樹的存儲(chǔ)結(jié)構(gòu)中，則稱線索二叉樹。1265.線索二叉樹241356897【例】設(shè)二叉樹Ｔ如圖，則其中序遍歷序列為：④⑦②⑧⑤⑨①③⑥【問題】

如何保存結(jié)點(diǎn)在遍歷序列中的線性關(guān)系。127

方案一在二叉鏈表中每個(gè)結(jié)點(diǎn)上增加兩個(gè)指針域，分別用以指向該結(jié)點(diǎn)在遍歷序列中的直接前驅(qū)和直接后繼。5.線索二叉樹二叉樹Ｔ的中序遍歷序列為：④⑦②⑧⑤⑨①③⑥21^3^4

5^8^^6^^9^T^7^^^21^3^4

5^8^^6^^9^T^7^128

方案二5.線索二叉樹利用二叉鏈表中的空鏈域保存結(jié)點(diǎn)間的線性關(guān)系：若結(jié)點(diǎn)的lchild域?yàn)榭?，則保存指向其直接前驅(qū)的指針；若結(jié)點(diǎn)的rchild域?yàn)榭?，則用于保存指向其直接后繼的指針。為此，每個(gè)結(jié)點(diǎn)還需另設(shè)兩個(gè)標(biāo)志域，用以指明該結(jié)點(diǎn)的lchild域(rchild域)中所保存的指針是指向其左(右)孩子的，還是指向其直接前驅(qū)(直接后繼)的。129二叉樹Ｔ的中序遍歷序列為：④⑦②⑧⑤⑨①③⑥5.線索二叉樹21^3^4

5^8^^6^^9^T^7^21345869T700000000^^^^^^^^^^1111111111130二、什么是線索二叉樹

利用二叉鏈表中空的指針域指出結(jié)點(diǎn)在某種遍歷序列中的直接前驅(qū)和直接后繼。指向前驅(qū)和后繼的指針稱為線索，加了線索的二叉樹稱為線索二叉樹。三、線索二叉樹的構(gòu)造

利用鏈結(jié)點(diǎn)的空的左指針域存放該結(jié)點(diǎn)的直接前驅(qū)的地址，空的右指針域存放該結(jié)點(diǎn)的直接后繼的地址；而非空的指針域仍然存放結(jié)點(diǎn)的左孩子或右孩子的地址。131對(duì)下圖按照中序遍歷進(jìn)行線索化中序遍歷的結(jié)果為：a+b*c-d-e/f稱作中序線索二叉樹NULLNULL132對(duì)下圖按照前序遍歷進(jìn)行線索化前序遍歷的結(jié)果為：-+a*b-cd/ef稱作前序線索二叉樹NULL133對(duì)下圖按照后序遍歷進(jìn)行線索化后序遍歷的結(jié)果為：abcd-*+ef/-稱作后序線索二叉樹NULL134線索二叉樹：結(jié)點(diǎn)的結(jié)構(gòu)現(xiàn)在lchild有2個(gè)功能(1)指向左孩子(2)指向前驅(qū)結(jié)點(diǎn)如何區(qū)別呢？增加一個(gè)標(biāo)記ltag說明其當(dāng)前的功能當(dāng)ltag=0時(shí)：指向左孩子，是指針當(dāng)ltag=1時(shí)：指向前驅(qū)結(jié)點(diǎn)，是線索rchild類似處理lchildltagdatartagrchild135線索二叉樹：結(jié)點(diǎn)類型定義lchildltagdatartagrchildtypedefintdatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;intltag,rtag;}bithptr;136例：帶了兩個(gè)標(biāo)志的某前序遍歷結(jié)果如下表所示，請(qǐng)畫出對(duì)應(yīng)的二叉樹。dataAGEIDJHCFBLtag0011110101Rtag0001010111AAGEIDJHCFBTag=1表示線索:Ltag=1表示前驅(qū)Rtag=1表示后繼1371a10*01e11f11b10-01c11d10+00/00-0??中序線索二叉樹:a+b*c-d-e/f1381a10*01e11f11b10-01c11d10+00/00-0頭結(jié)點(diǎn)01139線索二叉樹：中序線索二叉樹的遍歷線索化二叉樹的目的就在于方便遍歷增加頭結(jié)點(diǎn)lchild是指針：指向樹根rchild是線索：指向中序遍歷序列的尾結(jié)點(diǎn)同時(shí)中序遍歷序列中的首結(jié)點(diǎn)的lchild和尾結(jié)點(diǎn)的rchild都是一個(gè)線索：都指向頭結(jié)點(diǎn)這樣就能方便的進(jìn)行中序和逆向中序遍歷了140例：在中序線索二叉樹中查找結(jié)點(diǎn)p的后繼結(jié)點(diǎn)二叉樹中序遍歷序列:a+b*c-d當(dāng)rtag=1時(shí)，后繼就是p->rchild；當(dāng)rtag=0時(shí)，說明p有右子樹，必須沿著p的右子樹的根的左子樹方向查找，直到某結(jié)點(diǎn)的lchild域?yàn)榫€索(即，p右子樹中最左下角的結(jié)點(diǎn))，此結(jié)點(diǎn)就是p結(jié)點(diǎn)的后繼。p四、線索二叉鏈表的應(yīng)用+-*abdc141中序線索二叉樹查找結(jié)點(diǎn)p的后繼結(jié)點(diǎn)算法bithptr*InOrderNext(bithptr*p){bithptr*q;if(p->rtag==1)return(p->rchild);else{q=p->rchild;while(q->ltag==0)q=q->lchild;return(q);}}+-*abdc回顧二叉樹的中序遍歷：非遞歸算法intInOrderT(bitree*T){bitree*p=T;SqStack*S;InitStack(S);∥建棧

while(p||!StackEmpty(s)){if(p){Push(S,p);∥二叉樹非空，根結(jié)點(diǎn)進(jìn)棧

p=p->lchild;∥遍歷左子樹}else{Pop(S,p);Visit(p->data);p=p->rchild;∥遍歷右子樹

}}returnOK;}143中序線索二叉樹的遍歷(順后繼進(jìn)行)基本思想第一個(gè)訪問的結(jié)點(diǎn)應(yīng)該是最左下角的結(jié)點(diǎn)(假設(shè)為p)然后p的后繼是誰(shuí)？若p->rchild是指針(0)，說明p有右子樹，下一個(gè)結(jié)點(diǎn)應(yīng)該是p右子樹中最左下角的結(jié)點(diǎn)若p->rchild是線索(1)，直接訪問p->rchild如此循環(huán)往復(fù)...144中序線索二叉樹的遍歷算法intInOrderTraverse_Thr(bithptr*T){p=T->lchild;//p指向樹根

while(p!=T)//p等于T則說明已經(jīng)遍歷完畢

{while(p->ltag==0)//p->lchild為指針

p=p->lchild;//則向左下走到底

Visit(p->data);//訪問pwhile(p->rtag==1&&p->rchild!=T)//p->rchild為線索

{p=p->rchild;Visit(p->data);//訪問p}p=p->rchild;//向右繼續(xù)遍歷

}returnOK;}145中序線索二叉樹的遍歷思考：如果反方向進(jìn)行遍歷呢(順前驅(qū)進(jìn)行)？第一個(gè)訪問的結(jié)點(diǎn)應(yīng)該是最右下角的結(jié)點(diǎn)(假設(shè)為p)然后p的前驅(qū)是誰(shuí)？若p->lchild是指針，說明p有左子樹，前驅(qū)應(yīng)該是p左子樹中最右下角的結(jié)點(diǎn)若p->lchild是線索，直接訪問p->lchild如此循環(huán)往復(fù)...146以后序線索二叉樹為例第一個(gè)訪問的應(yīng)該是最左下角的結(jié)點(diǎn)(假設(shè)為p)，p的后繼是誰(shuí)？p線索二叉樹：前/后序線索二叉樹的遍歷147解答若p->rchild是線索則后繼就是p->rchild否則若p是樹根，則無后繼若p是右孩子或者是唯一的左孩子，則后繼是其父結(jié)點(diǎn)若p是左孩子，且有右兄弟，則后繼是p的父結(jié)點(diǎn)的右子樹中第一個(gè)訪問的結(jié)點(diǎn)pppp線索二叉樹：前/后序線索二叉樹的遍歷148線索二叉樹：前/后序線索二叉樹的遍歷困難對(duì)于后序線索二叉樹，想要找結(jié)點(diǎn)p的后繼結(jié)點(diǎn)，可能需要知道p的父結(jié)點(diǎn)是誰(shuí)可是這是很難辦到的兩種方法從樹根開始查找改用三叉鏈表來表示二叉樹此困難對(duì)于后序線索二叉樹找前驅(qū)結(jié)點(diǎn)、前序線索二叉樹找后繼/前驅(qū)結(jié)點(diǎn)同樣存在p149五、線索二叉樹：二叉樹的線索化普通的二叉樹怎么變成線索二叉樹？稱作線索化基本思想線索其實(shí)就是按照遍歷的順序把閑置的指針鏈接到前驅(qū)/后繼結(jié)點(diǎn)：遍歷過程中維護(hù)兩個(gè)指針：pre和p，分別指向遍歷序列中一前一后的兩個(gè)結(jié)點(diǎn)若pre->rchild閑置，pre->rchild=p若p->lchild閑置，p->lchild=pre150StatusInOrderThreading(Bitree*Thrt,Bitree*T){Thrt=(Bitree*)malloc(sizeof(bithptr));//頭結(jié)點(diǎn)

if(!Thrt)exit(OVERFLOW);Thrt->ltag=0;//頭結(jié)點(diǎn)的lchild是指針

Thrt->rtag=1;//頭結(jié)點(diǎn)的rchild是線索

if(!T)//若T為空樹，頭結(jié)點(diǎn)的左右指針回指

{Thrt->lchild=Thrt;Thrt->rchild=Thrt;}else{Thrt->lchild=T;

//頭結(jié)點(diǎn)的lchild指向樹根

pre=Thrt;

//pre是全局變量

InThreading(T);

//調(diào)用中序線索化函數(shù)處理二叉樹Tpre->rchild=Thrt;//InThreading調(diào)用完以后

pre->rtag=1;//就差最后一個(gè)結(jié)點(diǎn)沒有鏈接好

Thrt->rchild=pre;//此時(shí)，pre指向最后一個(gè)結(jié)點(diǎn)

}returnOK;}創(chuàng)建中序線索二叉樹的頭結(jié)點(diǎn)頭結(jié)點(diǎn)與樹根之間的連接修改中序遍歷的最后一個(gè)結(jié)點(diǎn)與頭結(jié)點(diǎn)之間的連接151voidInThreading(Bitree*p){if(p){//p為空則返回

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

if(!p->lchild){//若p->lchild閑置

p->lchild=pre;p->ltag=1;}if(!pre->rchild){//若pre->rchild閑置

pre->rchild=p;pre->rtag=1;}pre=p;//維持pre和p一前一后的關(guān)系

InThreading(p->rchild);//右子樹線索化

}}152voidInThreading(Bitree*p){if(p)

{InThreading(p->lchild);if(!p->lchild){p->lchild=pre;p->ltag=1;}

if(!pre->rchild){pre->rchild=p;pre->rtag=1;}

pre=p;InThreading(p->rchild);

}}ABC頭結(jié)點(diǎn)prep以p->lchild為參數(shù)遞歸調(diào)用此時(shí)的p就是A->lchild(B)以p->lchild為參數(shù)遞歸調(diào)用此時(shí)的p就是B->lchild此時(shí)p->lchild(B->lchild)閑置，應(yīng)作為線索，指向pre此時(shí)pre->rchild閑置應(yīng)作為線索，指向p注意：這次操作是無效的pre跟進(jìn)以p->rchild為參數(shù)遞歸調(diào)用調(diào)用完畢p->lchild不閑置pre->rchild閑置應(yīng)作為索引，指向ppre跟進(jìn)以p->rchild為參數(shù)遞歸調(diào)用p以p->lchild為參數(shù)遞歸調(diào)用此時(shí)p->lchild閑置應(yīng)作為線索，指向prepre->rchild不閑置pre跟進(jìn)pre以p->rchild為參數(shù)遞歸調(diào)用153StatusInOrderThreading(Bitree*Thrt,Bitree*T){......InThreading(T);pre->rchild=Thrt;pre->rtag=1;Thrt->rchild=pre;}returnOK;}ABC頭結(jié)點(diǎn)prepre此時(shí)指向遍歷序列的最后一個(gè)結(jié)點(diǎn)，pre->rchild應(yīng)作為線索，指向頭結(jié)點(diǎn)頭結(jié)點(diǎn)的rchild應(yīng)指向遍歷序列的最后結(jié)點(diǎn)程序結(jié)束調(diào)用完畢154例：畫出二叉鏈表存儲(chǔ)結(jié)構(gòu)上的中序線索二叉樹。中序遍歷序列:H,D,I,B,E,A,F,C,G0A00B00C00D01E11F11G11H11I1root01155前序線索樹上找前驅(qū)和后繼找前驅(qū)：困難，需要知道其雙親。找后繼：若結(jié)點(diǎn)有左子女，則左子女是后繼；否則，rchild指向后繼。156中序的前驅(qū)和后繼都往上指向祖先找前驅(qū)：若左標(biāo)記為1，則lchild指向其前驅(qū)；否則，其前驅(qū)是其左子樹上按中序遍歷的最后一個(gè)結(jié)點(diǎn)。找后繼：若右標(biāo)記為1，則rchild指向其后繼；否則，其后繼是其右子樹上按中序遍歷的第一個(gè)結(jié)點(diǎn)。中序線索樹上找前驅(qū)和后繼157后序線索樹上找前驅(qū)和后繼找前驅(qū)：若結(jié)點(diǎn)有右子女，則右子女是其前驅(qū)；否則，lchild指向其前驅(qū)。找后繼：困難，需要知道其雙親。158線索樹上結(jié)點(diǎn)的插入與刪除除修改結(jié)點(diǎn)指針外，還需要修改線索。1596.樹和森林：回顧樹：如果n>0，則有一個(gè)特定的稱之為根(root)的結(jié)點(diǎn)，它只有直接后繼，但沒有直接前驅(qū)除根以外的其它結(jié)點(diǎn)劃分為m(m>=0)個(gè)互不相交的有限集合T0,T1,…,Tm-1，每個(gè)集合又是一棵樹，并且稱之為根的子樹森林m(m>=0)棵互不相交的樹的集合160樹的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(居多)主要取決于要對(duì)樹進(jìn)行何種操作無論采用何種存儲(chǔ)結(jié)構(gòu)，需要存儲(chǔ)的信息有：結(jié)點(diǎn)本身的數(shù)據(jù)信息；結(jié)點(diǎn)之間存在的關(guān)系(分支)。161樹的存儲(chǔ)結(jié)構(gòu)：孩子表示法孩子表示法每個(gè)結(jié)點(diǎn)可以有多個(gè)孩子方法一：定長(zhǎng)結(jié)點(diǎn)的多重鏈表結(jié)構(gòu)問題：因n為樹的度，是所有結(jié)點(diǎn)的最大的度，因此樹中有相當(dāng)部分的指針域?yàn)榭?，浪費(fèi)空間。有n個(gè)結(jié)點(diǎn)的樹的度為k，空指針域有n(k-1)+1個(gè)。datachild1child2child3...childnn為樹的度162樹的存儲(chǔ)結(jié)構(gòu)：孩子表示法孩子表示法每個(gè)結(jié)點(diǎn)可以有多個(gè)孩子方法二：不定長(zhǎng)結(jié)點(diǎn)的多重鏈表結(jié)構(gòu)問題：量體裁衣，節(jié)省存儲(chǔ)空間不同的數(shù)據(jù)元素，結(jié)點(diǎn)構(gòu)造不同；操作不方便。datadegreechild1child2...childn結(jié)點(diǎn)的度163樹的存儲(chǔ)結(jié)構(gòu)：孩子表示法孩子表示法每個(gè)結(jié)點(diǎn)可以有多個(gè)孩子方法三：用一個(gè)靜態(tài)數(shù)組，存放所有的結(jié)點(diǎn)數(shù)組的每個(gè)數(shù)據(jù)元素，包括兩部分：數(shù)據(jù)元素，指針；指針指向一個(gè)鏈表，鏈表結(jié)點(diǎn)的數(shù)據(jù)域是一個(gè)整數(shù)，表示該結(jié)點(diǎn)的孩子在數(shù)組中的下標(biāo)；特點(diǎn)：順序+鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；找孩子容易，找雙親難；164樹的存儲(chǔ)結(jié)構(gòu)：孩子表示法bdaefcnum6a0MAX-1nodes2c3d4e5f1b^^^^【例】34^512^165還可以增加雙親信息(孩子-雙親表示法)bdaefcnum6a0MAX-1nodes2c3d4e5f1b^^^^-10110134^512^【例】166雙親表示法樹中一個(gè)結(jié)點(diǎn)的孩子的數(shù)量不定但是雙親卻只有一個(gè)所以保存每個(gè)結(jié)點(diǎn)的雙親0bdaefcnum6-10111a0MAX-1nodes2c3d4e5f1b【例】?jī)?yōu)點(diǎn)查找雙親、樹根操作很快缺點(diǎn)查找孩子操作慢，需遍歷整個(gè)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)：雙親表示法167從向下的縱向和向右的橫向描述樹；定義結(jié)點(diǎn)結(jié)構(gòu):數(shù)據(jù)元素和兩個(gè)指針。一個(gè)指向該結(jié)點(diǎn)的第一個(gè)孩子，另一個(gè)指向該結(jié)點(diǎn)的下一個(gè)兄弟；firstchilddatanextsibling第一個(gè)兒子下一個(gè)兄弟又稱二叉樹表示法樹的存儲(chǔ)結(jié)構(gòu)：孩子兄弟表示法168即左孩子、右兄弟表示法用二叉樹來表示樹左指針指向其大兒子右指針指向其兄弟樹的存儲(chǔ)結(jié)構(gòu)：孩子兄弟表示法169樹、森林和二叉樹的轉(zhuǎn)換轉(zhuǎn)換步驟：step1:將樹中同一結(jié)點(diǎn)的兄弟相連；step2:保留結(jié)點(diǎn)的最左孩子連線，刪除其它孩子連線；step3:將同一孩子的連線繞左孩子旋轉(zhuǎn)45度角。加線抹線旋轉(zhuǎn)討論1：樹如何轉(zhuǎn)為二叉樹？170abcdefgih樹轉(zhuǎn)二叉樹舉例：方法：加線—抹線—旋轉(zhuǎn)兄弟相連長(zhǎng)兄為父孩子靠左abcdefgih特點(diǎn)是？根結(jié)點(diǎn)沒有右孩子！171森林到二叉樹的轉(zhuǎn)換若樹采用孩子兄弟表示法，二叉樹采用二叉鏈表表示，則：任一棵樹，都可以找到唯一的一棵二叉樹和它對(duì)應(yīng)，而且該二叉樹沒有右子樹。若把森林中的第二棵樹的根結(jié)點(diǎn)，看成是第一棵樹的根結(jié)點(diǎn)的兄弟結(jié)點(diǎn)，則這兩棵樹可以轉(zhuǎn)換為一棵二叉樹（該二叉樹的根結(jié)點(diǎn)的右子女沒有右子樹）。依次類推，可以認(rèn)為森林和二叉樹是一一對(duì)應(yīng)的，從而得到二叉樹和森林的轉(zhuǎn)換規(guī)則。172樹、森林和二叉樹的轉(zhuǎn)換討論2：森林如何轉(zhuǎn)為二叉樹？方法一：(1)把森林中的每一棵樹轉(zhuǎn)換