樹(shù)和二叉樹(shù)學(xué)習(xí)

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

結(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)第6頁(yè)/共222頁(yè)7樹(shù)的基本概念

結(jié)點(diǎn)的度和樹(shù)的度結(jié)點(diǎn)的度即結(jié)點(diǎn)擁有的子樹(shù)個(gè)數(shù)。樹(shù)的度是樹(shù)內(nèi)各結(jié)點(diǎn)的度的最大值。ABCDEFGHIJKLM3213200100000第7頁(yè)/共222頁(yè)8樹(shù)的基本概念

結(jié)點(diǎn)的層次和樹(shù)的深度(高度)結(jié)點(diǎn)的層次從根開(kāi)始定義。根位于第1層，根的孩子位于第2層，余則類推。樹(shù)的深度即樹(shù)中結(jié)點(diǎn)的最大層次。第1層第2層第3層第4層樹(shù)的高度為4ABCDEFGHIJKLM第8頁(yè)/共222頁(yè)9樹(shù)的基本概念

孩子、雙親、兄弟結(jié)點(diǎn)的子樹(shù)的根稱為結(jié)點(diǎn)的孩子。該結(jié)點(diǎn)稱為其孩子的雙親。同一雙親的孩子間互稱兄弟。ABCDEFGHIJKLM孩子雙親第9頁(yè)/共222頁(yè)10樹(shù)的基本概念

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

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

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

個(gè)結(jié)點(diǎn)？1第21頁(yè)/共222頁(yè)22二叉樹(shù)的性質(zhì)性質(zhì)2：深度為k的二叉樹(shù)最多有2k-1個(gè)結(jié)點(diǎn)(k>=1)證明：由性質(zhì)1可知：第i層最多有2i-1個(gè)結(jié)點(diǎn)所以總的結(jié)點(diǎn)數(shù)最多為k=41234第22頁(yè)/共222頁(yè)23二叉樹(shù)的性質(zhì)性質(zhì)3：對(duì)任何一棵二叉樹(shù)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)無(wú)外乎度為0、1、2三種情況”五個(gè)手指四個(gè)叉”除了樹(shù)根，其余每個(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+1第23頁(yè)/共222頁(yè)24樹(shù)的葉子數(shù)與其它結(jié)點(diǎn)數(shù)的關(guān)系設(shè)度為m的樹(shù)中度為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

第24頁(yè)/共222頁(yè)25滿二叉樹(shù)(FullBinaryTree)深度為k，結(jié)點(diǎn)數(shù)為2k-1即結(jié)點(diǎn)數(shù)達(dá)到最大值特殊形態(tài)的二叉樹(shù)完全二叉樹(shù)(CompleteBinaryTree)樹(shù)中每個(gè)結(jié)點(diǎn)的編號(hào)（從上到下，從左到右）都與一個(gè)同深度的滿二叉樹(shù)的結(jié)點(diǎn)一一對(duì)應(yīng)葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)完全二叉樹(shù)和和滿二叉樹(shù)相比，就是最底層最右邊連續(xù)缺少一些結(jié)點(diǎn)第25頁(yè)/共222頁(yè)26特殊形態(tài)的二叉樹(shù)2h-1結(jié)論：

深度為h且具有2h-1個(gè)結(jié)點(diǎn)的二叉樹(shù)為滿二叉樹(shù)。思考：深度為h的完全二叉樹(shù)至少有多少個(gè)結(jié)點(diǎn)？第26頁(yè)/共222頁(yè)27二叉樹(shù)的性質(zhì)性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的非空完全二叉樹(shù)的深度為證明：設(shè)深度為k，則：2k-1-1<n<=2k-1由此推出：2k-1<=n<2k兩邊求對(duì)數(shù)：k-1<=log2n<k所以：24-123-1第27頁(yè)/共222頁(yè)28二叉樹(shù)的性質(zhì)性質(zhì)5：若將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)自頂向下，同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào)：(1)若i=1，則結(jié)點(diǎn)i是樹(shù)根，無(wú)雙親 若i>1，則其雙親是結(jié)點(diǎn)i/2(2)若2i>n，則結(jié)點(diǎn)i無(wú)左孩子(即i為葉結(jié)點(diǎn))，否則其左孩子為2i(3)若2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子，否則其右孩子為2i+1由(2)(3)可以推導(dǎo)出(1)理解：結(jié)點(diǎn)i如果有左孩子的話，其編號(hào)應(yīng)該為2i如果2i>n，則左孩子不存在第28頁(yè)/共222頁(yè)29二叉樹(shù)的性質(zhì)性質(zhì)6：具有n個(gè)結(jié)點(diǎn)的非空二叉樹(shù)共有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ù)的分支總數(shù)為n-1。第29頁(yè)/共222頁(yè)301.n(n>0)個(gè)結(jié)點(diǎn)的樹(shù)的高度最低是多少？最高是多少？2.n(n>0)個(gè)結(jié)點(diǎn)的二叉樹(shù)的高度最低是多少？最高是多少？推論n個(gè)結(jié)點(diǎn)的樹(shù)：高最多為n，最低為2。n個(gè)結(jié)點(diǎn)的二叉樹(shù)：高最多為n(單支樹(shù))，最低為log2n+1(完全二叉樹(shù))。自測(cè)題第30頁(yè)/共222頁(yè)31自測(cè)題

3.有關(guān)二叉樹(shù)下列說(shuō)法正確的是()A.二叉樹(shù)的度為2B.一棵二叉樹(shù)的度可以小于2C.二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2D.二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為24.已知一棵完全二叉樹(shù)的第6層(設(shè)根是第1層)有8個(gè)葉結(jié)點(diǎn)，則該完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)最多是()

A.39B.52C.111D.119第31頁(yè)/共222頁(yè)32完全二叉樹(shù)性質(zhì)的推論n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中：度為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)的完全二叉樹(shù)中共有2n0個(gè)結(jié)點(diǎn)或2n0-1個(gè)結(jié)點(diǎn)。第32頁(yè)/共222頁(yè)33一棵完全二叉樹(shù)有1000個(gè)結(jié)點(diǎn)，則它必有

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

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

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

個(gè)結(jié)點(diǎn)只有非空右子樹(shù)。(1000+1)/2

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

根據(jù)完全二叉樹(shù)的性質(zhì)5，對(duì)于深度為h的完全二叉樹(shù)，將樹(shù)中所有結(jié)點(diǎn)的數(shù)據(jù)信息按編號(hào)順序一次存儲(chǔ)到數(shù)組BT[1…2h-1]中，由于編號(hào)與數(shù)組下標(biāo)一一對(duì)應(yīng)，該數(shù)組就是該完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)。1234567891012345678910下標(biāo)：

BT[3]的雙親為3/2=1，即在BT[1]中；其左孩子在BT[2i]=BT[6]中；其右孩子在BT[2i+1]=BT[7]中。第38頁(yè)/共222頁(yè)39一般二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)123456789101234567891012345678910BT[5]的雙親為5/2=2，即在BT[2]中，與實(shí)際矛盾！其左孩子在BT[2i]=BT[10]中，實(shí)際應(yīng)在BT[9]中。

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

第43頁(yè)/共222頁(yè)44二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)三叉鏈表比二叉鏈表的鏈結(jié)點(diǎn)多增加了一個(gè)指向雙親結(jié)點(diǎn)的指針域parent。3.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)lchilddataparentrchildparentdataleftchildrightchild第44頁(yè)/共222頁(yè)45三叉鏈表示例第45頁(yè)/共222頁(yè)46二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)的定義

typedefintdatatype;typedefstructnode { datatypedata;

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

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

已知具有n個(gè)結(jié)點(diǎn)的非空完全二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)，結(jié)點(diǎn)的數(shù)據(jù)信息依次存放于數(shù)組BT[1..n]中。請(qǐng)寫(xiě)出由此產(chǎn)生該二叉樹(shù)二叉鏈表結(jié)構(gòu)的算法。第54頁(yè)/共222頁(yè)55建立根結(jié)點(diǎn)以BT的第2個(gè)元素開(kāi)始取一個(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ù)組中利用二叉樹(shù)的性質(zhì)5第55頁(yè)/共222頁(yè)56設(shè)置一個(gè)一維數(shù)組PTR存放結(jié)點(diǎn)所在鏈結(jié)點(diǎn)的地址建立根結(jié)點(diǎn)，并將根結(jié)點(diǎn)的地址保存在數(shù)組PTR中從數(shù)組BT的第2個(gè)元素開(kāi)始依次取結(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)的右孩子；第56頁(yè)/共222頁(yè)57ijj=i/2當(dāng)i%2==0時(shí)，i是j的左孩子當(dāng)i%2!=0時(shí)，i是j的右孩子第57頁(yè)/共222頁(yè)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)*/第58頁(yè)/共222頁(yè)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;}第59頁(yè)/共222頁(yè)60

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

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

1.前(先)序遍歷

DLR2.中序遍歷

LDR3.后序遍歷

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

二叉樹(shù)的層序遍歷算法：

(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)指針，訪問(wèn)該結(jié)點(diǎn)；

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

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

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

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

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

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

if(p->lchild)AddQueue(Q,p->lchild);

//左孩子入隊(duì)

if(p->rchild)AddQueue(Q,p->rchild);

//右孩子入隊(duì)

}

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

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

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

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

}}第74頁(yè)/共222頁(yè)75二叉樹(shù)的中序遍歷遞歸算法若二叉樹(shù)為空，則算法結(jié)束；否則：(1)中序遍歷根結(jié)點(diǎn)的左子樹(shù)；(2)訪問(wèn)根結(jié)點(diǎn)；(3)中序遍歷根結(jié)點(diǎn)的右子樹(shù)。voidInOrderTraverse(bitree*T){if(T){

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

printf("\t%c\n",T->data);

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

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

InitStack(S);

//建棧

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

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

{Push(S,p);p=p->lchild;

//遍歷左子樹(shù)

}else//p為NULL，說(shuō)明走到了底

{Pop(S,p);Visit(p->data);

//彈出一個(gè)還沒(méi)訪問(wèn)的結(jié)點(diǎn)，訪問(wèn)之

p=p->rchild;//遍歷右子樹(shù)

}}returnOK;}p指向樹(shù)根p走到了底，再依次彈出剛才路過(guò)卻沒(méi)有訪問(wèn)的結(jié)點(diǎn)，訪問(wèn)之，然后p向右走第82頁(yè)/共222頁(yè)83時(shí)間復(fù)雜度n個(gè)結(jié)點(diǎn)，每一個(gè)都要訪問(wèn)一次顯然時(shí)間復(fù)雜度為O(n)(這里n為結(jié)點(diǎn)數(shù))空間復(fù)雜度不論是遞歸還是非遞歸算法都要用到棧棧的最大深度=樹(shù)的深度所有空間復(fù)雜度為O(n)(這里n為樹(shù)的深度)二叉樹(shù)的遍歷：算法效率第83頁(yè)/共222頁(yè)84二叉樹(shù)的初始化算法的基本思想:創(chuàng)建二叉樹(shù)的頭結(jié)點(diǎn)。程序?qū)崿F(xiàn)：voidInitiate(bitree**root){*root=(bitree*)malloc(sizeof(bitree));(*root)->lchild=NULL;(*root)->rchild=NULL;}root是指向根指針的指針第84頁(yè)/共222頁(yè)85按前序構(gòu)造二叉鏈表例1：按下列次序輸入字符(φ表示空格):ABCφφDEφGφφFφφφ

A^B^C^D^E^F^^G^二叉鏈表為:例2：HGφFφφMφφrootH^G^M^^F^第85頁(yè)/共222頁(yè)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ā)生變化后可以返回第86頁(yè)/共222頁(yè)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,E第87頁(yè)/共222頁(yè)88第88頁(yè)/共222頁(yè)89前序序列：中序序列：后序序列：ABIFCGDEHFIBCGADEHFIGCBHEDA第89頁(yè)/共222頁(yè)90利用前序序列和中序序列恢復(fù)二叉樹(shù)利用中序序列和后序序列恢復(fù)二叉樹(shù)利用前序序列和后序序列恢復(fù)二叉樹(shù)前序序列：A,B,D,C后序序列：D,B,C,A第90頁(yè)/共222頁(yè)91六、由遍歷序列恢復(fù)二叉樹(shù)前序序列：

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

D,B,J,E,A,F,I,C,G第91頁(yè)/共222頁(yè)92已知前序序列和中序序列，恢復(fù)二叉樹(shù)

在前序序列中尋找根；到中序序列中分左右。規(guī)律已知中序序列和后序序列，恢復(fù)二叉樹(shù)

在后序序列中尋找根；到中序序列中分左右。第92頁(yè)/共222頁(yè)93例:已知結(jié)點(diǎn)的前序序列和中序序列分別為：前序序列：ABDEGHCF

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

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

中序序列DBMFAHECGL請(qǐng)構(gòu)造該二叉樹(shù)。自測(cè)題第99頁(yè)/共222頁(yè)100

一棵二叉樹(shù)的前序、中序和后序序列如下，其中有部分未標(biāo)出，試構(gòu)造出該二叉樹(shù)。前序序列為：__CDE_GHI_K中序序列為：CB__FA_JKIG后序序列為：_EFDB_JIH_A自測(cè)題第100頁(yè)/共222頁(yè)101試找出滿足下列條件的二叉樹(shù)1)前序序列與后序序列相同2)中序序列與后序序列相同3)前序序列與中序序列相同4)前序、中序、后序序列均相同5)中序序列與層次遍歷序列相同自測(cè)題第101頁(yè)/共222頁(yè)102一棵二叉樹(shù)的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是()。A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEGB自測(cè)題第102頁(yè)/共222頁(yè)103一棵非空的二叉樹(shù)的前序序列和后序序列正好相反，則該二叉樹(shù)一定滿足()。A.其中任意一個(gè)結(jié)點(diǎn)均無(wú)左孩子B.其中任意一個(gè)結(jié)點(diǎn)均無(wú)右孩子C.其中只有一個(gè)葉子結(jié)點(diǎn)D.其中度為2的結(jié)點(diǎn)最多為一個(gè)E.空或只有一個(gè)結(jié)點(diǎn)F.高度等于其結(jié)點(diǎn)數(shù)自測(cè)題第103頁(yè)/共222頁(yè)104注意：

一個(gè)二叉樹(shù)的遍歷序列不能決定一棵二叉樹(shù)，但前序（或后序）和中序遍歷序列的組合可以唯一確定一棵二叉樹(shù)。而前序和后序遍歷則不能?？谠E：DLR—前序遍歷，即先根再左再右LDR—中序遍歷，即先左再根再右LRD—后序遍歷，即先左再右再根第104頁(yè)/共222頁(yè)105例6.1給二叉樹(shù)中某個(gè)指定結(jié)點(diǎn)插入一個(gè)左結(jié)點(diǎn)

算法思想:

若當(dāng)前結(jié)點(diǎn)(假設(shè)為curr)非空，在curr的左子樹(shù)插入元素值為x的新結(jié)點(diǎn)，原curr所指結(jié)點(diǎn)的左子樹(shù)成為新插入結(jié)點(diǎn)的左子樹(shù)。若插入成功返回新插入結(jié)點(diǎn)的指針，否則返回空指針。二叉樹(shù)操作舉例第105頁(yè)/共222頁(yè)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;}第106頁(yè)/共222頁(yè)107算法思想:

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

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

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

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

if(!BT->lchild&&!BT->rchild)num++;

//葉子結(jié)點(diǎn)計(jì)數(shù)

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

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

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

if(!BT->lchild&&!BT->rchild)return(1);

elsereturn//左子樹(shù)葉子數(shù)加上右子樹(shù)葉子數(shù)

(leafcount(BT->lchild)+leafcount(BT->rchild));}第112頁(yè)/共222頁(yè)113例6.5交換所有結(jié)點(diǎn)的左右子樹(shù)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);}}第113頁(yè)/共222頁(yè)114例6.6求二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)intnodecount(bitree*BT){if(BT==NULL)return(0);//空二叉樹(shù)

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

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

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

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

lpre=pre(1,i-1); rpre=pre(i,n); lmid=mid(0,i-1); rmid=mid(i,m);第118頁(yè)/共222頁(yè)119

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

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

如何保存結(jié)點(diǎn)在遍歷序列中的線性關(guān)系。第126頁(yè)/共222頁(yè)127

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

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

5^8^^6^^9^T^7^第127頁(yè)/共222頁(yè)128

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

5^8^^6^^9^T^7^21345869T700000000^^^^^^^^^^1111111111第129頁(yè)/共222頁(yè)130二、什么是線索二叉樹(shù)

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

利用鏈結(jié)點(diǎn)的空的左指針域存放該結(jié)點(diǎn)的直接前驅(qū)的地址，空的右指針域存放該結(jié)點(diǎn)的直接后繼的地址；而非空的指針域仍然存放結(jié)點(diǎn)的左孩子或右孩子的地址。第130頁(yè)/共222頁(yè)131對(duì)下圖按照中序遍歷進(jìn)行線索化中序遍歷的結(jié)果為：a+b*c-d-e/f稱作中序線索二叉樹(shù)NULLNULL第131頁(yè)/共222頁(yè)132對(duì)下圖按照前序遍歷進(jìn)行線索化前序遍歷的結(jié)果為：-+a*b-cd/ef稱作前序線索二叉樹(shù)NULL第132頁(yè)/共222頁(yè)133對(duì)下圖按照后序遍歷進(jìn)行線索化后序遍歷的結(jié)果為：abcd-*+ef/-稱作后序線索二叉樹(shù)NULL第133頁(yè)/共222頁(yè)134線索二叉樹(shù)：結(jié)點(diǎn)的結(jié)構(gòu)現(xiàn)在lchild有2個(gè)功能(1)指向左孩子(2)指向前驅(qū)結(jié)點(diǎn)如何區(qū)別呢？增加一個(gè)標(biāo)記ltag說(shuō)明其當(dāng)前的功能當(dāng)ltag=0時(shí)：指向左孩子，是指針當(dāng)ltag=1時(shí)：指向前驅(qū)結(jié)點(diǎn)，是線索rchild類似處理lchildltagdatartagrchild第134頁(yè)/共222頁(yè)135線索二叉樹(shù)：結(jié)點(diǎn)類型定義lchildltagdatartagrchildtypedefintdatatype;typedefstructnode{

datatypedata;

structnode*lchild,*rchild;intltag,rtag;}bithptr;第135頁(yè)/共222頁(yè)136例：帶了兩個(gè)標(biāo)志的某前序遍歷結(jié)果如下表所示，請(qǐng)畫(huà)出對(duì)應(yīng)的二叉樹(shù)。dataAGEIDJHCFBLtag0011110101Rtag0001010111AAGEIDJHCFBTag=1表示線索:Ltag=1表示前驅(qū)Rtag=1表示后繼第136頁(yè)/共222頁(yè)1371a10*01e11f11b10-01c11d10+00/00-0??中序線索二叉樹(shù):a+b*c-d-e/f第137頁(yè)/共222頁(yè)1381a10*01e11f11b10-01c11d10+00/00-0頭結(jié)點(diǎn)01第138頁(yè)/共222頁(yè)139線索二叉樹(shù)：中序線索二叉樹(shù)的遍歷線索化二叉樹(shù)的目的就在于方便遍歷增加頭結(jié)點(diǎn)lchild是指針：指向樹(shù)根rchild是線索：指向中序遍歷序列的尾結(jié)點(diǎn)同時(shí)中序遍歷序列中的首結(jié)點(diǎn)的lchild和尾結(jié)點(diǎn)的rchild都是一個(gè)線索：都指向頭結(jié)點(diǎn)這樣就能方便的進(jìn)行中序和逆向中序遍歷了第139頁(yè)/共222頁(yè)140例：在中序線索二叉樹(shù)中查找結(jié)點(diǎn)p的后繼結(jié)點(diǎn)二叉樹(shù)中序遍歷序列:a+b*c-d當(dāng)rtag=1時(shí)，后繼就是p->rchild；當(dāng)rtag=0時(shí)，說(shuō)明p有右子樹(shù)，必須沿著p的右子樹(shù)的根的左子樹(shù)方向查找，直到某結(jié)點(diǎn)的lchild域?yàn)榫€索(即，p右子樹(shù)中最左下角的結(jié)點(diǎn))，此結(jié)點(diǎn)就是p結(jié)點(diǎn)的后繼。p四、線索二叉鏈表的應(yīng)用+-*abdc第140頁(yè)/共222頁(yè)141中序線索二叉樹(shù)查找結(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第141頁(yè)/共222頁(yè)回顧二叉樹(shù)的中序遍歷：非遞歸算法intInOrderT(bitree*T){bitree*p=T;SqStack*S;

InitStack(S);

∥建棧

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

p=p->lchild;

∥遍歷左子樹(shù)

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

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

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

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

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

Visit(p->data);//訪問(wèn)p

while(p->rtag==1&&p->rchild!=T)//p->rchild為線索

{p=p->rchild;

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

}

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

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

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

pre=Thrt;

//pre是全局變量

InThreading(T);

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

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

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

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

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

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);//右子樹(shù)線索化

}}第151頁(yè)/共222頁(yè)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;InT