數(shù)據(jù)結(jié)構(gòu)中的樹

1、 第六章第六章 樹和二叉樹樹和二叉樹（ Tree & Binary tree Tree & Binary tree ） 主講：李耀國主講：李耀國第六章第六章 樹和二叉樹樹和二叉樹 6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語 6.1.2 二叉樹二叉樹 6.2.1 二叉樹的定義和基本術(shù)語二叉樹的定義和基本術(shù)語 6.2.2 二叉樹的幾個(gè)基本性質(zhì)二叉樹的幾個(gè)基本性質(zhì) 6.2.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) 6.2 遍歷二叉樹和線索二叉遍歷二叉樹和線索二叉樹樹 6.2.1 問題的提出問題的提出 6.2.2 遍歷算法描述遍歷算法描述 6.2.3 二叉樹遍歷應(yīng)用舉例二叉樹遍歷應(yīng)用舉例

2、 6.2.4 線索二叉樹線索二叉樹n 6.3 6.3 樹和森林樹和森林n 6.3.1 6.3.1 樹和森林的定義樹和森林的定義n 6.3.2 6.3.2 樹和森林的存儲結(jié)構(gòu)樹和森林的存儲結(jié)構(gòu)n 6.3.3 6.3.3 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換n 6.3.4 6.3.4 樹和森林的遍歷樹和森林的遍歷n 6.4 6.4 樹的應(yīng)用樹的應(yīng)用n 6.4.1 6.4.1 堆排序的實(shí)現(xiàn)堆排序的實(shí)現(xiàn)n 6.4.2 6.4.2 二叉排序樹二叉排序樹n 6.4.3 6.4.3 赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用6.1 二叉樹二叉樹6.1.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語6.1.2 二叉樹

3、的定義和基本術(shù)語二叉樹的定義和基本術(shù)語6.1.3 二叉樹的幾個(gè)基本性質(zhì)二叉樹的幾個(gè)基本性質(zhì)6.1.4 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)第第6章章 樹和二叉樹樹和二叉樹 樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，其中樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，其中以樹和二叉樹最為常用。直觀角度看，樹是以以樹和二叉樹最為常用。直觀角度看，樹是以分支關(guān)系分支關(guān)系定義的定義的層次結(jié)構(gòu)層次結(jié)構(gòu)。樹在計(jì)算機(jī)領(lǐng)域中。樹在計(jì)算機(jī)領(lǐng)域中得到廣泛應(yīng)用，如文件管理中的得到廣泛應(yīng)用，如文件管理中的目錄結(jié)構(gòu)目錄結(jié)構(gòu)、數(shù)、數(shù)據(jù)庫系統(tǒng)中的據(jù)庫系統(tǒng)中的信息組織形式信息組織形式等。樹結(jié)構(gòu)在客觀等。樹結(jié)構(gòu)在客觀世界中也廣泛存在，如人類社會的族

4、譜和各種世界中也廣泛存在，如人類社會的族譜和各種社會組織機(jī)構(gòu)都可用樹來形象表示。本章重點(diǎn)社會組織機(jī)構(gòu)都可用樹來形象表示。本章重點(diǎn)討論二叉樹的存儲結(jié)構(gòu)及各種操作，并研究樹討論二叉樹的存儲結(jié)構(gòu)及各種操作，并研究樹和森林與二叉樹的轉(zhuǎn)換關(guān)系。和森林與二叉樹的轉(zhuǎn)換關(guān)系。第第6章章 樹和二叉樹樹和二叉樹 到目前為止，我們已經(jīng)介紹了線性數(shù)據(jù)結(jié)構(gòu)和表數(shù)到目前為止，我們已經(jīng)介紹了線性數(shù)據(jù)結(jié)構(gòu)和表數(shù)據(jù)結(jié)構(gòu)。這些數(shù)據(jù)結(jié)構(gòu)據(jù)結(jié)構(gòu)。這些數(shù)據(jù)結(jié)構(gòu)一般不適合于描述具有層次一般不適合于描述具有層次結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)。在層次化的數(shù)據(jù)之間可能有祖先。在層次化的數(shù)據(jù)之間可能有祖先-后后代、上級代、上級-下屬、整體下屬、整體-部分

5、以及其他類似的關(guān)系。部分以及其他類似的關(guān)系。 例例1Joe的后代的后代：上圖給出了：上圖給出了Joe的后代，并按層的后代，并按層次方式組織，其中次方式組織，其中Joe在最頂層。在最頂層。Joe的孩子（的孩子（Ann，Mary和和John）列在下一層，在父母和孩子間有一）列在下一層，在父母和孩子間有一條邊。在層次表示中，非常容易地找到條邊。在層次表示中，非常容易地找到Ann的兄弟的兄弟姐妹，姐妹，Joe的后代，的后代，Chris的祖先等。的祖先等。第第6章章 樹和二叉樹樹和二叉樹例例2軟件工程軟件工程：考察另一種層次：考察另一種層次數(shù)據(jù)數(shù)據(jù)軟件工程中的模塊化技術(shù)。軟件工程中的模塊化技術(shù)。通過模塊

6、化，可以把大的復(fù)雜的任通過模塊化，可以把大的復(fù)雜的任務(wù)分成一組小的不太復(fù)雜的任務(wù)。務(wù)分成一組小的不太復(fù)雜的任務(wù)。模塊化的目標(biāo)是把軟件系統(tǒng)分成許模塊化的目標(biāo)是把軟件系統(tǒng)分成許多功能不相關(guān)的部分或模塊以便于多功能不相關(guān)的部分或模塊以便于進(jìn)行相對獨(dú)立的開發(fā)。由于解決幾進(jìn)行相對獨(dú)立的開發(fā)。由于解決幾個(gè)小問題比解決大問題更容易一些，個(gè)小問題比解決大問題更容易一些，因此模塊化方法可以縮短整個(gè)軟件因此模塊化方法可以縮短整個(gè)軟件的開發(fā)時(shí)間。另外，不同的程序員的開發(fā)時(shí)間。另外，不同的程序員可以同時(shí)開發(fā)不同的模塊。如果有可以同時(shí)開發(fā)不同的模塊。如果有必要，每個(gè)模塊可以再細(xì)分，從而必要，每個(gè)模塊可以再細(xì)分，從而得到

7、如圖所示的用樹形表示的模塊得到如圖所示的用樹形表示的模塊層次結(jié)構(gòu)。該樹給出了某文字處理層次結(jié)構(gòu)。該樹給出了某文字處理器的一種可行的模塊分解圖。器的一種可行的模塊分解圖。第第6章章 樹和二叉樹樹和二叉樹 例例3：學(xué)校的組織結(jié)構(gòu)學(xué)校的組織結(jié)構(gòu)學(xué)院學(xué)院教務(wù)科教務(wù)科院辦院辦基礎(chǔ)部基礎(chǔ)部科學(xué)系科學(xué)系技術(shù)系技術(shù)系計(jì)算中心計(jì)算中心軟件系軟件系研究所研究所后勤處后勤處應(yīng)用室應(yīng)用室人工智能室人工智能室可計(jì)算性室可計(jì)算性室學(xué)生科學(xué)生科師資科師資科教學(xué)科教學(xué)科教材科教材科 何謂樹狀結(jié)構(gòu)何謂樹狀結(jié)構(gòu) 樹是樹是n(n0)個(gè)結(jié)點(diǎn)的有限集。個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹中在任意一棵非空樹中：(1)有有且僅有一個(gè)特定的稱為

8、根的結(jié)且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；點(diǎn)；(2)當(dāng)當(dāng)n1時(shí)，其余結(jié)點(diǎn)可時(shí)，其余結(jié)點(diǎn)可分為分為m(m 0)個(gè)互不相交的有個(gè)互不相交的有限集限集T1, T2, ,Tm，其中每一，其中每一個(gè)集合本身又是一棵樹，并且個(gè)集合本身又是一棵樹，并且稱為根的子樹。稱為根的子樹。 若一棵樹中的結(jié)點(diǎn)可以有若一棵樹中的結(jié)點(diǎn)可以有n個(gè)子結(jié)點(diǎn)，則稱這樣的樹為個(gè)子結(jié)點(diǎn)，則稱這樣的樹為n元樹，例如二叉樹中的結(jié)點(diǎn)，元樹，例如二叉樹中的結(jié)點(diǎn)，最多只能有兩個(gè)結(jié)點(diǎn)。最多只能有兩個(gè)結(jié)點(diǎn)。AMDCBRQPA為根結(jié)點(diǎn)為根結(jié)點(diǎn)B、C、D、M為為A的子結(jié)點(diǎn)的子結(jié)點(diǎn)6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語 樹的相關(guān)名稱及意義樹的相關(guān)名稱及意

9、義 根結(jié)點(diǎn)（根結(jié)點(diǎn)（root node）一棵樹中沒有父結(jié)點(diǎn)的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)一棵樹中沒有父結(jié)點(diǎn)的結(jié)點(diǎn)，稱為根結(jié)點(diǎn) 葉（子）結(jié)點(diǎn)葉（子）結(jié)點(diǎn)leaf node或終端結(jié)點(diǎn)或終端結(jié)點(diǎn)terminal node一棵樹中沒有子結(jié)點(diǎn)的結(jié)點(diǎn)，稱為葉（子）結(jié)點(diǎn)或終端結(jié)點(diǎn)一棵樹中沒有子結(jié)點(diǎn)的結(jié)點(diǎn)，稱為葉（子）結(jié)點(diǎn)或終端結(jié)點(diǎn) 分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)（分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)（nonterminal node） 除了葉（子）結(jié)點(diǎn)以外的其他結(jié)點(diǎn)，稱為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)除了葉（子）結(jié)點(diǎn)以外的其他結(jié)點(diǎn)，稱為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn) ADCBEFGHI葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)根結(jié)點(diǎn)根結(jié)點(diǎn)6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語非終端結(jié)

10、點(diǎn)非終端結(jié)點(diǎn) 父結(jié)點(diǎn)（父結(jié)點(diǎn)（parent）和子結(jié)點(diǎn)（）和子結(jié)點(diǎn)（child）若結(jié)點(diǎn)若結(jié)點(diǎn)x有一個(gè)以結(jié)點(diǎn)有一個(gè)以結(jié)點(diǎn)y為樹根的子樹為樹根的子樹, 則則x為為y的父結(jié)點(diǎn)（父親），而的父結(jié)點(diǎn)（父親），而y為為x的子結(jié)點(diǎn)（孩子）。的子結(jié)點(diǎn)（孩子）。 兄弟（兄弟（sibling） 同一個(gè)父結(jié)點(diǎn)之子結(jié)點(diǎn)，稱為兄弟同一個(gè)父結(jié)點(diǎn)之子結(jié)點(diǎn)，稱為兄弟如圖如圖B、C、D的父結(jié)點(diǎn)均為的父結(jié)點(diǎn)均為A，故，故B、C、D互為兄弟互為兄弟 結(jié)點(diǎn)的度（結(jié)點(diǎn)的度（degree）結(jié)點(diǎn)的子樹個(gè)數(shù)，稱為結(jié)點(diǎn)的度。結(jié)點(diǎn)的子樹個(gè)數(shù)，稱為結(jié)點(diǎn)的度。如圖，如圖，A的度為的度為3，B的度為的度為3，C的度為的度為1，最大的度值為，最大的度值為

11、3，故樹為，故樹為3元元樹。樹。 層次（層次（level）層次為結(jié)點(diǎn)之特性值，將根結(jié)點(diǎn)之層次設(shè)為層次為結(jié)點(diǎn)之特性值，將根結(jié)點(diǎn)之層次設(shè)為1，其子結(jié)點(diǎn)為，其子結(jié)點(diǎn)為2，依此類推。，依此類推。如圖，層次為如圖，層次為1的有結(jié)點(diǎn)的有結(jié)點(diǎn)A, 為為2的有結(jié)點(diǎn)的有結(jié)點(diǎn)B、C、D，為，為3的有結(jié)點(diǎn)的有結(jié)點(diǎn)E、F、G、H、I。6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語ADCBEFG HI深度（深度（depth）或高度（）或高度（height）葉子結(jié)點(diǎn)的最大層次數(shù)稱為樹葉子結(jié)點(diǎn)的最大層次數(shù)稱為樹的深度的深度。 如圖，葉子最大層次值為如圖，葉子最大層次值為3，故樹，故樹 T的深度為的深度為3祖先（祖先（ance

12、stor） 由某結(jié)點(diǎn)由某結(jié)點(diǎn)X到根結(jié)點(diǎn)之路徑上的所有結(jié)點(diǎn)，均稱為到根結(jié)點(diǎn)之路徑上的所有結(jié)點(diǎn)，均稱為X之祖先之祖先樹林（樹林（forest） n=0個(gè)樹的集合稱為樹林個(gè)樹的集合稱為樹林 若將一樹的根結(jié)點(diǎn)移去，所剩這恰是一樹林若將一樹的根結(jié)點(diǎn)移去，所剩這恰是一樹林.ADCBEFG HIDCBEFGHI6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語A6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語例例1：只有根結(jié)點(diǎn)的樹：只有根結(jié)點(diǎn)的樹A例例2：一般的樹：一般的樹1.此樹此樹Tree-A 共有共有13個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn),是由三棵子樹組成：是由三棵子樹組成：Tree-B(T1) = B，E，F(xiàn)，K，LTree-C(

13、T2) = C，GTree-D(T3) = D，H，I，J，MB、C、D為三棵子樹的根，且互不相交為三棵子樹的根，且互不相交2. T1又分為兩個(gè)互不相交的又分為兩個(gè)互不相交的Tree-E(T11)=E，K，L 和和Tree-F(T12)=FT2又分為一個(gè)樹又分為一個(gè)樹Tree-G(T21)=GT3又分為三棵互不相交的又分為三棵互不相交的Tree-H(T31)=H，MTree-I(T32)=I 和和Tree-J(T33)=J3.T11又分為又分為:Tree-K(T111) 和和Tree-L(T112) T31又分又分為為:Tree-M(T311)ADCBKGLEFH IJM每棵子樹的結(jié)構(gòu)均符合上

14、述定義每棵子樹的結(jié)構(gòu)均符合上述定義6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語 例例3：不是一棵樹：不是一棵樹 因?yàn)橐驗(yàn)?子樹子樹Tree-H=H，M子樹子樹Tree-I=I，M出現(xiàn)了交叉，違出現(xiàn)了交叉，違反樹的定義。反樹的定義。 樹的其它表示形式樹的其它表示形式Tree-A的結(jié)構(gòu)：的結(jié)構(gòu)：結(jié)點(diǎn)結(jié)點(diǎn)A包括包括B,C,D結(jié)點(diǎn)結(jié)點(diǎn)B包括包括E,F結(jié)點(diǎn)結(jié)點(diǎn)C包括包括G結(jié)點(diǎn)結(jié)點(diǎn)D包括包括H,I,J結(jié)點(diǎn)結(jié)點(diǎn)E包括包括K,L結(jié)點(diǎn)結(jié)點(diǎn)H包括包括MADCBKGLEFH IJMADCBKGLEFHIJM樹的表示形式樹的表示形式A:B,C,DB:E,FC:GD:H,I,JE:K,LH:MK KE EB BA AL

15、 LF FC CG GD DM MH HI IJ J2 2 凹入表示法凹入表示法1 1 集合表示法集合表示法6.1.2 二叉樹的定義和基本術(shù)語二叉樹的定義和基本術(shù)語 二叉樹（二叉樹（binary tree）是）是n(n0)個(gè)數(shù)據(jù)元素的有限集，個(gè)數(shù)據(jù)元素的有限集，它或?yàn)榭占驗(yàn)榭占?n0)，或者含有唯一的稱為根的元素，且其，或者含有唯一的稱為根的元素，且其余元素分成余元素分成兩個(gè)兩個(gè)互不相交的子集，每個(gè)子集自身也是一棵互不相交的子集，每個(gè)子集自身也是一棵二叉樹二叉樹，分別稱為根的，分別稱為根的左子樹左子樹和和右子樹右子樹。 集合為空的樹簡稱為空樹。集合為空的樹簡稱為空樹。 樹中的元素稱為結(jié)點(diǎn)。

16、樹中的元素稱為結(jié)點(diǎn)。ADCBEFBDE左子樹左子樹CF右子樹右子樹6.1.2 二叉樹的定義和基本術(shù)語二叉樹的定義和基本術(shù)語 根以外的任意兩個(gè)結(jié)點(diǎn)不可能同根以外的任意兩個(gè)結(jié)點(diǎn)不可能同時(shí)在同一棵子樹中出現(xiàn)。時(shí)在同一棵子樹中出現(xiàn)。 二叉樹的子樹有左右之分，不能二叉樹的子樹有左右之分，不能任意顛倒。任意顛倒。 如圖所示如圖所示 A為根結(jié)點(diǎn)為根結(jié)點(diǎn) D、G、H、J為葉子結(jié)點(diǎn)為葉子結(jié)點(diǎn) A是是B的父親，的父親，B是是A的左孩子，的左孩子，C是是A的右孩子，的右孩子，A是是E的祖先，的祖先，E是是A的子孫，的子孫，D和和E是兄弟，是兄弟，D和和F是堂兄弟是堂兄弟 A、B、的度為、的度為2，C、F、I的度為的

17、度為1， D、G、H、J的的度為度為0 二叉樹的深度為二叉樹的深度為5ADCBEGFIJH二叉樹的五種形態(tài)二叉樹的五種形態(tài)練習(xí)：如果只有三個(gè)結(jié)點(diǎn)，形態(tài)如何？練習(xí)：如果只有三個(gè)結(jié)點(diǎn)，形態(tài)如何？左、右子樹左、右子樹具全的二叉樹具全的二叉樹左子樹為空左子樹為空的二叉樹的二叉樹空的二叉樹空的二叉樹僅有根結(jié)點(diǎn)僅有根結(jié)點(diǎn)的二叉樹的二叉樹右子樹為空右子樹為空的二叉樹的二叉樹 滿二叉樹（滿二叉樹（full binary tree） 若二叉樹中所有的分支結(jié)點(diǎn)的度數(shù)都為若二叉樹中所有的分支結(jié)點(diǎn)的度數(shù)都為2，且葉子，且葉子結(jié)點(diǎn)都在同一層次上，則稱這類二叉樹為滿二叉樹。結(jié)點(diǎn)都在同一層次上，則稱這類二叉樹為滿二叉樹。若

18、該樹的高度為若該樹的高度為h，則此滿二叉樹的結(jié)點(diǎn)為，則此滿二叉樹的結(jié)點(diǎn)為 2h-1A層次：層次：1 CB層次：層次：2 DEFG層次：層次：3 6.1.2 二叉樹的定義和基本術(shù)語二叉樹的定義和基本術(shù)語 完全二叉樹（完全二叉樹（complete binary tree） 假如任意一棵包含假如任意一棵包含n個(gè)結(jié)點(diǎn)的二叉樹中每個(gè)結(jié)點(diǎn)都可以和同深度個(gè)結(jié)點(diǎn)的二叉樹中每個(gè)結(jié)點(diǎn)都可以和同深度的滿二叉樹中編號為的滿二叉樹中編號為1至至n的結(jié)點(diǎn)一一對應(yīng)，則稱這類二叉樹為完的結(jié)點(diǎn)一一對應(yīng)，則稱這類二叉樹為完全二叉樹。全二叉樹。 一棵樹扣除掉最大階層那層后為一滿二叉樹，且階層最大那層的一棵樹扣除掉最大階層那層后為一

19、滿二叉樹，且階層最大那層的結(jié)點(diǎn)均向左靠齊，則該二叉樹稱為完全二叉樹。結(jié)點(diǎn)均向左靠齊，則該二叉樹稱為完全二叉樹。滿二叉樹滿二叉樹 level最大層的最大層的結(jié)點(diǎn)均向左靠齊結(jié)點(diǎn)均向左靠齊 完全二叉樹完全二叉樹 ADCBEF6.1.2 二叉樹的定義和基本術(shù)語二叉樹的定義和基本術(shù)語6.1.2 二叉樹的定義和基本術(shù)語二叉樹的定義和基本術(shù)語 二叉樹的應(yīng)用二叉樹的應(yīng)用表示家族的血緣關(guān)系表示家族的血緣關(guān)系外曾祖母外曾祖母曾祖父曾祖父曾祖母曾祖母曾祖父曾祖父曾祖母曾祖母外曾祖母外曾祖母外曾祖父外曾祖父外曾祖父外曾祖父祖父祖父外祖父外祖父祖母祖母外祖母外祖母父親父親母親母親男方男方外曾祖母外曾祖母曾祖父曾祖父曾祖

20、母曾祖母曾祖父曾祖父曾祖母曾祖母外曾祖母外曾祖母外曾祖父外曾祖父外曾祖父外曾祖父祖父祖父外祖父外祖父祖母祖母外祖母外祖母父親父親母親母親女方女方家庭家庭1家庭家庭2不能有相同結(jié)點(diǎn)，不能有相同結(jié)點(diǎn)，否則為否則為近親近親結(jié)婚！結(jié)婚！6.1.2 二叉樹的定義和基本術(shù)語二叉樹的定義和基本術(shù)語二叉樹的基本操作定義二叉樹的基本操作定義(1)initBiTree(&T)n操作結(jié)果：構(gòu)造一棵空的二叉樹操作結(jié)果：構(gòu)造一棵空的二叉樹T。DestroyBiTree(&T)n初始條件：二叉樹初始條件：二叉樹T存在。存在。n操作結(jié)果：銷毀二叉樹操作結(jié)果：銷毀二叉樹TCreateBiTree(&T

21、,definition)n初始條件：初始條件：definition給出二叉樹給出二叉樹T的定義。的定義。n操作結(jié)果：按操作結(jié)果：按definition給出的定義構(gòu)造二叉樹給出的定義構(gòu)造二叉樹T。BiTreeEmpty(T)n初始條件：二叉樹初始條件：二叉樹T存在。存在。n操作結(jié)果：操作結(jié)果： 若若T為空二叉樹，則返回為空二叉樹，則返回TRUE， 否則返回否則返回FALSE.6.1.2 二叉樹的定義和基本術(shù)語二叉樹的定義和基本術(shù)語 二叉樹的基本操作定義二叉樹的基本操作定義(2)BiTreeDepth(T)n初始條件：二叉樹初始條件：二叉樹T存在。存在。n操作結(jié)果：返回操作結(jié)果：返回T的深度。的深

22、度。Parent(T,e)n初始條件：二叉樹初始條件：二叉樹T存在存在,e是是T中某個(gè)結(jié)點(diǎn)。中某個(gè)結(jié)點(diǎn)。n操作結(jié)果：若操作結(jié)果：若e是是T的非根結(jié)點(diǎn)，則返回它的雙親，的非根結(jié)點(diǎn)，則返回它的雙親， 否則返回否則返回“空空”。LeftChiild(T,e)n初始條件：二叉樹初始條件：二叉樹T存在，存在，e是是T中某個(gè)結(jié)點(diǎn)。中某個(gè)結(jié)點(diǎn)。n操作結(jié)果：返回操作結(jié)果：返回e的左孩子。若的左孩子。若e無左孩子，則返回?zé)o左孩子，則返回“空空”。RightChild(T,e)n初始條件：二叉樹初始條件：二叉樹T存在，存在，e是是T中某個(gè)結(jié)點(diǎn)。中某個(gè)結(jié)點(diǎn)。n操作結(jié)果：返回操作結(jié)果：返回e的右孩子。若的右孩子。若e

23、無右孩子，則返回?zé)o右孩子，則返回“空空”。6.1.2 二叉樹的定義和基本術(shù)語二叉樹的定義和基本術(shù)語 二叉樹的基本操作定義二叉樹的基本操作定義(3)LeftSibling(T,e)n初始條件：二叉樹初始條件：二叉樹T存在，存在，e是是T中某個(gè)結(jié)點(diǎn)。中某個(gè)結(jié)點(diǎn)。n操作結(jié)果：返回操作結(jié)果：返回e的左兄弟，若的左兄弟，若e是其雙親的左孩子或是其雙親的左孩子或無左兄弟，則返回?zé)o左兄弟，則返回“空空”。RighrtSibling(T,e)n初始條件：二叉樹初始條件：二叉樹T存在，存在，e是是T中某個(gè)結(jié)點(diǎn)。中某個(gè)結(jié)點(diǎn)。n操作結(jié)果：返回操作結(jié)果：返回e的右兄弟，若的右兄弟，若e是其雙親的左孩子或是其雙親的左孩

24、子或無左兄弟，則返回?zé)o左兄弟，則返回“空空”。InsertChild(T,p,LR,C)n初始條件：二叉樹初始條件：二叉樹T存在存在,p指向指向T中某個(gè)結(jié)點(diǎn)，左或右中某個(gè)結(jié)點(diǎn)，左或右的標(biāo)志的標(biāo)志LR為為0或或1，非空二叉樹，非空二叉樹c與與T不相交且右子樹為空。不相交且右子樹為空。n操作結(jié)果：根據(jù)操作結(jié)果：根據(jù)LR為為0或或1，插入，插入c為為T中中p所指結(jié)點(diǎn)的所指結(jié)點(diǎn)的左子樹或右子樹，左子樹或右子樹，p所指結(jié)點(diǎn)原有的左子樹或右子樹均成所指結(jié)點(diǎn)原有的左子樹或右子樹均成為為c的右子樹。的右子樹。6.1.2 二叉樹的定義和基本術(shù)語二叉樹的定義和基本術(shù)語二叉樹的基本操作定義二叉樹的基本操作定義(4)

25、DeleteChild(T,p,LR)n初始條件：二叉樹初始條件：二叉樹T存在，存在，p指向指向T中某個(gè)結(jié)點(diǎn)，中某個(gè)結(jié)點(diǎn)，LR為為0或或1。n操作結(jié)果：根據(jù)操作結(jié)果：根據(jù)LR為為0或或1，刪除，刪除T中中p所指結(jié)點(diǎn)的左或右所指結(jié)點(diǎn)的左或右子樹。子樹。Traverse（T）n初始條件：二叉樹初始條件：二叉樹T存在存在n操作結(jié)果：依某條搜索路徑遍歷操作結(jié)果：依某條搜索路徑遍歷T，對每個(gè)結(jié)點(diǎn)進(jìn)行一次，對每個(gè)結(jié)點(diǎn)進(jìn)行一次且僅一次訪問（例如輸出結(jié)點(diǎn)元素值）且僅一次訪問（例如輸出結(jié)點(diǎn)元素值）6.1.3 二叉樹的幾個(gè)基本性質(zhì)二叉樹的幾個(gè)基本性質(zhì) 性質(zhì)性質(zhì)1 在二叉樹的第在二叉樹的第i層上層上至多至多有有2i

26、-1個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（i 1）利用數(shù)學(xué)歸納法證明：利用數(shù)學(xué)歸納法證明： i =1時(shí)，只有一個(gè)根結(jié)點(diǎn)，顯然時(shí)，只有一個(gè)根結(jié)點(diǎn)，顯然2i-1 = 20 =1是對的。是對的。 現(xiàn)在假定對所有現(xiàn)在假定對所有j（1jn0 =n2+16.1.3 二叉樹的幾個(gè)基本性質(zhì)二叉樹的幾個(gè)基本性質(zhì)性質(zhì)性質(zhì)4 具有具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為個(gè)結(jié)點(diǎn)的完全二叉樹的深度為證明：證明：n 假設(shè)深度為假設(shè)深度為k，則根據(jù)性質(zhì)，則根據(jù)性質(zhì)2和完全二叉樹的定義有和完全二叉樹的定義有 2k-1-1 n 2k -1，或，或2k-1 n 2k n 取對數(shù)便有取對數(shù)便有k-1 log2n 1，則其雙親結(jié)點(diǎn)，則其雙親結(jié)點(diǎn)parent(i)

27、的編號是的編號是（2）如果）如果2in，則編號為，則編號為i的結(jié)點(diǎn)無左孩子（編號為的結(jié)點(diǎn)無左孩子（編號為i的結(jié)點(diǎn)為葉子結(jié)點(diǎn)）；否則其左孩子結(jié)點(diǎn)的結(jié)點(diǎn)為葉子結(jié)點(diǎn)）；否則其左孩子結(jié)點(diǎn)lChild(i)的編的編號是號是2i（3）如果）如果2i+1n，則編號為，則編號為i的結(jié)點(diǎn)無右左孩子；否的結(jié)點(diǎn)無右左孩子；否則其右孩子結(jié)點(diǎn)則其右孩子結(jié)點(diǎn)rChild(i)的編號是的編號是2i+1 1log2 n 2/ i 1log2 n6.1.3 二叉樹的幾個(gè)基本性質(zhì)二叉樹的幾個(gè)基本性質(zhì)ACBDFEGIHKJL1 12 23 34 45 56 67 78 89 9101011111212對于對于E E，2 2* *5

28、=1012,5=1012,其左孩子為其左孩子為10;210;2* *5+1=11125+1=11126+1=1312，沒有右孩子，沒有右孩子對于對于J J，2 2* *10=201210=2012，為葉子結(jié)點(diǎn)，為葉子結(jié)點(diǎn) 1.1.順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) 用一組地址連續(xù)的存儲單元存儲二叉樹中的數(shù)據(jù)元素用一組地址連續(xù)的存儲單元存儲二叉樹中的數(shù)據(jù)元素 將完全二叉樹編號為的結(jié)點(diǎn)存儲在一維數(shù)組下標(biāo)為的單元中將完全二叉樹編號為的結(jié)點(diǎn)存儲在一維數(shù)組下標(biāo)為的單元中 一般二叉樹可能浪費(fèi)大量存儲空間一般二叉樹可能浪費(fèi)大量存儲空間ABC DEFG0123456ABCD0123456789ADCBEFG(0) (1

29、) (2) (3) (4) (5) (6) (3) (7) (8) (2) (5) (6) (0) (1) (4) (9) ABCD6.1.4 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)6.1.4 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) 1.1.順序順序存儲結(jié)構(gòu)存儲結(jié)構(gòu) 完全二叉樹的順序存儲結(jié)構(gòu)定義：完全二叉樹的順序存儲結(jié)構(gòu)定義：const MAXSIZE=100； /結(jié)點(diǎn)數(shù)最大值結(jié)點(diǎn)數(shù)最大值typedef struct TElemType *data; /存儲空間基址存儲空間基址 int nodenum; /樹中結(jié)點(diǎn)數(shù)樹中結(jié)點(diǎn)數(shù)SqBiTree; /完全二叉樹的順序存儲結(jié)構(gòu)完全二叉樹的順序存儲結(jié)構(gòu) 1.順序

30、存儲結(jié)構(gòu)（從下標(biāo)為順序存儲結(jié)構(gòu)（從下標(biāo)為1的單元開始存儲）的單元開始存儲）假設(shè)父結(jié)點(diǎn)編號為假設(shè)父結(jié)點(diǎn)編號為n，可以得到：，可以得到： （1）左子結(jié)點(diǎn)為父結(jié)點(diǎn)乘以）左子結(jié)點(diǎn)為父結(jié)點(diǎn)乘以2：2*n （2）右子結(jié)點(diǎn)為父結(jié)點(diǎn)乘以）右子結(jié)點(diǎn)為父結(jié)點(diǎn)乘以2加加1：2*n+1ABC DEFG01234567ABCD012345678109ADCBEFG(1) (2) (3) (4) (5) (6) (7) (4) (8) (9) (3) (6) (7) (1) (2) (5) (10) ABCD6.1.4 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)6.1.4 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) 2. 鏈?zhǔn)酱鎯Ρ硎炬準(zhǔn)酱?/p>

31、儲表示二叉樹結(jié)點(diǎn)的邏輯結(jié)構(gòu)二叉樹結(jié)點(diǎn)的邏輯結(jié)構(gòu) 如左圖如左圖datadatalchildlchildrchildrchildlchildlchilddatadatarchildrchildn 二叉鏈表二叉鏈表 typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /左、右孩子指針左、右孩子指針 BiTNode,*BiTree; /完全二叉樹的二叉鏈表結(jié)構(gòu)完全二叉樹的二叉鏈表結(jié)構(gòu)6.1.4 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)ABCDEGHFIJ二叉樹的二叉鏈表二叉樹的二叉鏈表 A A B B D D E E F

32、 F C C I I G G H H J J6.1.4 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) 2. 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯Ρ硎颈硎?三叉鏈表三叉鏈表 typedef struct BiTNode TElemType data; /結(jié)點(diǎn)數(shù)據(jù)結(jié)點(diǎn)數(shù)據(jù) struct BiTNode *parent,*lchild,*rchild; BiTNode,*BiTree; /完全二叉樹的三叉鏈表結(jié)完全二叉樹的三叉鏈表結(jié)構(gòu)構(gòu)lchildlchildparentparentdatadatarchildrchilddatadataparentparentlchildlchildrchildrchild6.1.4 二叉樹的存

33、儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)ABCDEGHFIJ二叉樹的三叉鏈表二叉樹的三叉鏈表 A A B B C C D D E E G G H H F F I I J J 6.1.4 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)3. 結(jié)構(gòu)體數(shù)組存儲結(jié)構(gòu)體數(shù)組存儲可用結(jié)構(gòu)體數(shù)組來存儲二叉樹，此結(jié)構(gòu)體包含可用結(jié)構(gòu)體數(shù)組來存儲二叉樹，此結(jié)構(gòu)體包含3個(gè)字段，其中個(gè)字段，其中一個(gè)字段是用來存放結(jié)點(diǎn)的數(shù)據(jù)內(nèi)容，而另兩個(gè)字段則是分別一個(gè)字段是用來存放結(jié)點(diǎn)的數(shù)據(jù)內(nèi)容，而另兩個(gè)字段則是分別存放左子樹和右子樹在數(shù)組中的索引值。存放左子樹和右子樹在數(shù)組中的索引值。二叉樹的結(jié)構(gòu)體數(shù)組聲明如下：二叉樹的結(jié)構(gòu)體數(shù)組聲明如下： typedef str

34、uct int left; TElemType data; int right;treenode; /完全二叉樹的二叉鏈表結(jié)構(gòu)完全二叉樹的二叉鏈表結(jié)構(gòu)treenode b_treeSIZE;在結(jié)構(gòu)數(shù)組中在結(jié)構(gòu)數(shù)組中b_tree ，會將根結(jié)點(diǎn)置于數(shù)組結(jié)構(gòu)中索引值為，會將根結(jié)點(diǎn)置于數(shù)組結(jié)構(gòu)中索引值為0之處，將結(jié)點(diǎn)值存在之處，將結(jié)點(diǎn)值存在data字段，而字段，而left及及right字段則分別存儲字段則分別存儲左右子樹在數(shù)組結(jié)構(gòu)中的索引值，若子樹不存在則存值左右子樹在數(shù)組結(jié)構(gòu)中的索引值，若子樹不存在則存值-1。6.1.4 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)3. 結(jié)構(gòu)體數(shù)組存儲結(jié)構(gòu)體數(shù)組存儲例如，有一棵

35、二叉樹其樹狀結(jié)構(gòu)與結(jié)構(gòu)數(shù)組表示法如下：例如，有一棵二叉樹其樹狀結(jié)構(gòu)與結(jié)構(gòu)數(shù)組表示法如下：圖中根結(jié)點(diǎn)為圖中根結(jié)點(diǎn)為A，故，故A在結(jié)構(gòu)數(shù)組索引值為之處，其左子結(jié)點(diǎn)在結(jié)構(gòu)數(shù)組索引值為之處，其左子結(jié)點(diǎn)B在索引值在索引值1，右子結(jié)點(diǎn)，右子結(jié)點(diǎn)B在索引值在索引值2，故結(jié)點(diǎn)，故結(jié)點(diǎn)A的的left字段和字段和right字段分別為字段分別為1和和2，而結(jié)點(diǎn)，而結(jié)點(diǎn)C的的right字段值為字段值為-1，表示其沒有右子，表示其沒有右子結(jié)點(diǎn)，而結(jié)點(diǎn)結(jié)點(diǎn)，而結(jié)點(diǎn)D和和E都是葉結(jié)點(diǎn)（都是葉結(jié)點(diǎn)（leaf node ）沒有子結(jié)點(diǎn)，故）沒有子結(jié)點(diǎn)，故left 和和right字段均為字段均為-1。索引值索引值leftleftd

36、atadatarightright01A21-1B324C-13-1D-14-1E-1ACBDE(0) (1) (2) (3) (4) 6.2 二叉樹遍歷二叉樹遍歷6.2.1 問題的提出問題的提出6.2.2 遍歷算法描述遍歷算法描述6.2.3 二叉樹遍歷應(yīng)用舉例二叉樹遍歷應(yīng)用舉例6.2.4 線索二叉樹線索二叉樹6.2.1 問題的提出問題的提出 遍歷二叉樹（遍歷二叉樹（Traversing binary tree）：如何按某條搜索路徑）：如何按某條搜索路徑巡訪樹中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問到且僅被訪問一次。巡訪樹中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問到且僅被訪問一次。 訪問：存取操作、打印等加工處

37、理。訪問：存取操作、打印等加工處理。 數(shù)組和鏈表可以從前端到尾端或從尾端到前端依序抽取各個(gè)數(shù)據(jù)數(shù)組和鏈表可以從前端到尾端或從尾端到前端依序抽取各個(gè)數(shù)據(jù)值，而二叉樹是一種值，而二叉樹是一種特殊的數(shù)據(jù)結(jié)構(gòu)特殊的數(shù)據(jù)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)其下又各有左、，每個(gè)結(jié)點(diǎn)其下又各有左、右兩個(gè)分支，右兩個(gè)分支，“二叉樹的遍歷二叉樹的遍歷”是以固定的順序，有系統(tǒng)地抽取是以固定的順序，有系統(tǒng)地抽取二叉樹中的各結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)均恰好被抽取一次。二叉樹中的各結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)均恰好被抽取一次。 二叉樹的遍歷是以遞歸的方式進(jìn)行，以遞歸的調(diào)用順序不同，可二叉樹的遍歷是以遞歸的方式進(jìn)行，以遞歸的調(diào)用順序不同，可分為三種遍歷方式：分為三

38、種遍歷方式： 先序遍歷方式先序遍歷方式 中序遍歷方式中序遍歷方式 后序遍歷方式后序遍歷方式6.2.1 問題的提出問題的提出先序遍歷（先序遍歷（Preorder traversal）是是先遍歷先遍歷根根結(jié)點(diǎn)，再遍歷結(jié)點(diǎn)，再遍歷左子樹左子樹，最后，最后遍歷遍歷右子樹右子樹，若一棵二叉樹如右圖，若一棵二叉樹如右圖，則先序遍歷的順序?yàn)椋簞t先序遍歷的順序?yàn)椋篋LR,也就是說也就是說每當(dāng)遍歷一個(gè)結(jié)點(diǎn)就先處理該結(jié)點(diǎn)，每當(dāng)遍歷一個(gè)結(jié)點(diǎn)就先處理該結(jié)點(diǎn)，之后先向左方前進(jìn)，直到無法前進(jìn)才之后先向左方前進(jìn)，直到無法前進(jìn)才往右方走。往右方走。左圖中從根結(jié)點(diǎn)左圖中從根結(jié)點(diǎn)A開始，先往左開始，先往左子樹子樹B再到再到D，由

39、于，由于D沒有左子樹，沒有左子樹，故轉(zhuǎn)向右子樹故轉(zhuǎn)向右子樹G；再回到；再回到B，因?yàn)?，因?yàn)锽沒有右子樹，所以此時(shí)沒有右子樹，所以此時(shí)A的左子樹的左子樹均遍歷完畢，則轉(zhuǎn)向均遍歷完畢，則轉(zhuǎn)向A的右子樹，的右子樹，再往左邊繼續(xù)遍歷。再往左邊繼續(xù)遍歷。依此類推，其前序遍歷為：依此類推，其前序遍歷為：ABDGCEHIF。ADCBGEFHIDRL根結(jié)點(diǎn)根結(jié)點(diǎn)左子樹左子樹右子樹右子樹cDcLcRcAcIcHcGcFcEcDcCcB6.2.1 問題的提出問題的提出先序遍歷二叉樹的步驟如下：先序遍歷二叉樹的步驟如下：if 二叉樹為空二叉樹為空 then 遍歷結(jié)束遍歷結(jié)束else （1）訪問當(dāng)前結(jié)點(diǎn)）訪問當(dāng)前結(jié)點(diǎn)

40、 （2）先序訪問左子樹）先序訪問左子樹 （3）先序訪問右子樹）先序訪問右子樹6.2.1 問題的提出問題的提出中序遍歷（中序遍歷（Inorder traversal）是先遍是先遍歷歷左子樹左子樹，再，再根根結(jié)點(diǎn)，最后才遍歷結(jié)點(diǎn)，最后才遍歷右子右子樹樹，若一棵二叉樹如右圖，則中序遍歷，若一棵二叉樹如右圖，則中序遍歷的順序?yàn)椋旱捻樞驗(yàn)椋篖DR，也就是說一開始先往，也就是說一開始先往左方前進(jìn)，直到無法前進(jìn)才處理結(jié)點(diǎn)，左方前進(jìn)，直到無法前進(jìn)才處理結(jié)點(diǎn)，之后再往右方前進(jìn)。之后再往右方前進(jìn)。ADCBGEFHI左圖中從根結(jié)點(diǎn)左圖中從根結(jié)點(diǎn)A開始，一直開始，一直往左走到往左走到D無法再前進(jìn)，則處理無法再前進(jìn)，則

41、處理D，再往再往D之右方到之右方到G。此時(shí)，已遍歷。此時(shí)，已遍歷完完B之左子樹，接著處理之左子樹，接著處理B，再往，再往B的右方向前進(jìn)。由于的右方向前進(jìn)。由于B沒有右子沒有右子樹，故樹，故A之左子樹遍歷完畢，再往之左子樹遍歷完畢，再往A之右子樹前進(jìn)。之右子樹前進(jìn)。依此類推，其中序遍歷為：依此類推，其中序遍歷為：DGBAHEICF。DRL根結(jié)點(diǎn)根結(jié)點(diǎn)左子樹左子樹右子樹右子樹cDcLcRcAcIcHcGcFcEcDcCcB6.2.1 問題的提出問題的提出中序遍歷二叉樹的步驟如下：中序遍歷二叉樹的步驟如下：if 二叉樹為空二叉樹為空 then 遍歷結(jié)束遍歷結(jié)束else （1）中序訪問左子樹）中序訪問

42、左子樹 （2）訪問當(dāng)前結(jié)點(diǎn)）訪問當(dāng)前結(jié)點(diǎn) （3）中序訪問右子樹）中序訪問右子樹6.2.1 問題的提出問題的提出后序遍歷（后序遍歷（Postorder traversal）是是先遍歷先遍歷左子樹左子樹，再遍歷，再遍歷右子樹右子樹，最后，最后才遍歷才遍歷根根結(jié)點(diǎn)，若一棵二叉樹如右圖，結(jié)點(diǎn)，若一棵二叉樹如右圖，則后序遍歷的順序?yàn)椋簞t后序遍歷的順序?yàn)椋篖RD，也就是，也就是說一開始先往左方前進(jìn)，直到無法前說一開始先往左方前進(jìn)，直到無法前進(jìn)才處再往右方前進(jìn)，最后才處理結(jié)進(jìn)才處再往右方前進(jìn)，最后才處理結(jié)點(diǎn)。點(diǎn)。左圖中從根結(jié)點(diǎn)左圖中從根結(jié)點(diǎn)A開始，一直往左開始，一直往左走到走到D無法再前進(jìn)，則往無法再前進(jìn)，

43、則往D之右方前之右方前進(jìn)到進(jìn)到G，由于，由于G沒有左、右子樹，故沒有左、右子樹，故處理結(jié)點(diǎn)處理結(jié)點(diǎn)G。之后由于。之后由于D之右子樹處之右子樹處理完畢，故進(jìn)而處理理完畢，故進(jìn)而處理D，而，而B之左子之左子樹也相應(yīng)完成。且結(jié)點(diǎn)樹也相應(yīng)完成。且結(jié)點(diǎn)B沒有右子樹，沒有右子樹，故可接著處理故可接著處理B。此時(shí)。此時(shí)A之左子樹已之左子樹已遍歷完畢，再往遍歷完畢，再往A之右子樹之右子樹C前進(jìn)。前進(jìn)。依此類推，其后序遍歷為：依此類推，其后序遍歷為：GDBHIEFCA。ADCBGEFHIDRL根結(jié)點(diǎn)根結(jié)點(diǎn)左子樹左子樹右子樹右子樹cDcLcRcAcIcHcGcFcEcDcCcB6.2.1 問題的提出問題的提出后序

44、遍歷二叉樹的步驟如下：后序遍歷二叉樹的步驟如下：if 二叉樹為空二叉樹為空 then 遍歷結(jié)束遍歷結(jié)束else （1）后序訪問左子樹）后序訪問左子樹 （2）后序訪問右子樹）后序訪問右子樹 （3）訪問當(dāng)前結(jié)點(diǎn)）訪問當(dāng)前結(jié)點(diǎn)6.2.1 問題的提出問題的提出二叉樹遍歷過程示意圖二叉樹遍歷過程示意圖 A A B B E E D D C CABCDEA AC CB BD DC CE EA AA AB BD DE EC CE EB BD D先序：先序：ABDECABDEC中序：中序：DBEACDBEAC后序：后序：DEBCADEBCA遍歷練習(xí)遍歷練習(xí)ADCBGFIJEH先序：先序：ABDGEHCFIJAB

45、DGEHCFIJ中序：中序：DGBEHACIFJDGBEHACIFJ后序：后序：GDHEBIJFCAGDHEBIJFCA遍歷練習(xí)遍歷練習(xí) 已知某二叉樹的先序序列為已知某二叉樹的先序序列為:abdgcefh，中序序，中序序列為列為:dgbaechf，求其后序序列，求其后序序列先序先序a a b d g c e f h b d g c e f h中序中序d g b d g b a a e c h f e c h fa a b b d g d g c c e f h e f ha a b b d d g g c c e e f f h hd g d g b b a a e e c c h f h f

46、abced d g g b ab a e e c c h h f f根根右右根根根根左左左左左左右右根根根根根根右右左左dfgh遍歷練習(xí)遍歷練習(xí) 已知某二叉樹的后序序列為已知某二叉樹的后序序列為:gdbehfca:gdbehfca，中序序列，中序序列為為:dgbaechf:dgbaechf，求其先序序列，求其先序序列后序后序g d b e h f c g d b e h f c a a中序中序d g b d g b a a e c h f e c h fg d g d b b e h f e h f c c a ag g d d b b e e h h f f c c a ad g d g b

47、 b a a e e c c h f h fabced d g g b ab a e e c c h h f f根根右右根根根根左左左左左左右右根根根根根根右右左左dfgh6.2.2 遍歷算法描述遍歷算法描述 先序遞歸算法：先序遞歸算法：/ 先序遍歷以先序遍歷以T為根指針的二叉樹為根指針的二叉樹 void Preorder (BiTree T，void(*visit)( BiTree ) if(T) / T=NULL時(shí)，二叉樹為空樹，不做任何操作時(shí)，二叉樹為空樹，不做任何操作 visit(T); / 通過函數(shù)指針通過函數(shù)指針*visit訪問根結(jié)點(diǎn)，訪問根結(jié)點(diǎn)， 以便靈活完成相應(yīng)的操作以便靈活完

48、成相應(yīng)的操作 Preorder(T-lchild, visit); / 先序遍歷左子樹先序遍歷左子樹 Preorder(T-rchild, visit); / 先序遍歷右子樹先序遍歷右子樹 6.2.2 遍歷算法描述遍歷算法描述 中序遞歸算法：中序遞歸算法：/ 中序遍歷以中序遍歷以T為根指針的二叉樹為根指針的二叉樹 void Inorder (BiTree T，void(*visit)( BiTree ) if(T) / T=NULL時(shí)，二叉樹為空樹，不做任何操作時(shí)，二叉樹為空樹，不做任何操作 Inorder(T-lchild, visit); / 中序遍歷左子樹中序遍歷左子樹 visit(T)

49、; / 通過函數(shù)指針通過函數(shù)指針*visit訪問根結(jié)點(diǎn)，訪問根結(jié)點(diǎn)， 以便靈活完成相應(yīng)的操作以便靈活完成相應(yīng)的操作 Inorder(T-rchild, visit); / 中序遍歷右子樹中序遍歷右子樹 6.2.2 遍歷算法描述遍歷算法描述 后序遞歸算法：后序遞歸算法：/ 后序遍歷以后序遍歷以T為根指針的二叉樹為根指針的二叉樹 void Postorder (BiTree T，void(*visit)( BiTree ) if(T) / T=NULL時(shí)，二叉樹為空樹，不做任何操作時(shí)，二叉樹為空樹，不做任何操作 Postorder(T-lchild, visit); / 后序遍歷左子樹后序遍歷左子

50、樹 Postorder(T-rchild, visit); / 后序遍歷右子樹后序遍歷右子樹 visit(T); / 通過函數(shù)指針通過函數(shù)指針*visit訪問根結(jié)點(diǎn)，訪問根結(jié)點(diǎn)， 以便靈活完成相應(yīng)的操作以便靈活完成相應(yīng)的操作 6.2.2 遍歷算法描述遍歷算法描述 堆棧遍歷算法：堆棧遍歷算法：typedef enum Travel=1,Visit=0 TaskType;/為為Travel時(shí)工作狀態(tài)是遍歷，為時(shí)工作狀態(tài)是遍歷，為Visit時(shí)是訪問時(shí)是訪問typedef struct BiTree ptr; /指向二叉樹結(jié)點(diǎn)的指針指向二叉樹結(jié)點(diǎn)的指針 TaskType task;/任務(wù)的性質(zhì)任務(wù)的性

51、質(zhì)SElemType;/棧元素的類型定義棧元素的類型定義6.2.2 遍歷算法描述遍歷算法描述 先序堆棧算法：先序堆棧算法：void PreOrder_iter( BiTree BT，void(*visit)( BiTree ) ) / 利用棧實(shí)現(xiàn)中序遍歷二叉樹，利用棧實(shí)現(xiàn)中序遍歷二叉樹，T為指向二叉樹的根結(jié)點(diǎn)的頭指針為指向二叉樹的根結(jié)點(diǎn)的頭指針 InitStack(S); e.ptr=BT; e.task=Travel; / e為棧元素為棧元素 if(BT) Push(S, e); / 布置初始任務(wù)布置初始任務(wù) while(!StackEmpty(S) / 每次處理一項(xiàng)任務(wù)每次處理一項(xiàng)任務(wù) P

52、op(S,e); if(e.ptr) / 處理非空樹的遍歷任務(wù)處理非空樹的遍歷任務(wù) visit(e.ptr); / p=e.ptr; e.ptr=p-rchild; Push(S,e); / 最不迫切任務(wù)最不迫切任務(wù)(遍歷右子樹遍歷右子樹)進(jìn)棧進(jìn)棧 e.ptr=p-lchild; /直接處理迫切任務(wù)直接處理迫切任務(wù)(遍歷左子樹遍歷左子樹) /if /while/PreOrder_iter6.2.2 遍歷算法描述遍歷算法描述 中序堆棧算法：中序堆棧算法：void InOrder_iter( BiTree BT，void(*visit)( BiTree ) )/ 利用棧實(shí)現(xiàn)中序遍歷二叉樹，利用棧實(shí)

53、現(xiàn)中序遍歷二叉樹，T為指向二叉樹的根結(jié)點(diǎn)的頭指針為指向二叉樹的根結(jié)點(diǎn)的頭指針 InitStack(S); e.ptr=BT; e.task=Travel; / e為棧元素為棧元素 if(BT) Push(S, e); / 布置初始任務(wù)布置初始任務(wù) while(!StackEmpty(S) / 每次處理一項(xiàng)任務(wù)每次處理一項(xiàng)任務(wù) Pop(S,e); if(e.task=Visit) visit(e.ptr); / 處理訪問任務(wù)處理訪問任務(wù) else if(e.ptr) / 處理非空樹的遍歷任務(wù)處理非空樹的遍歷任務(wù) p=e.ptr; e.ptr=p-rchild; Push(S,e); / 最不迫切

54、任務(wù)最不迫切任務(wù)(遍歷右子樹遍歷右子樹)進(jìn)棧進(jìn)棧 e.ptr=p; e.task=Visit; Push(S,e); /處理訪問任務(wù)的工作狀態(tài)進(jìn)棧處理訪問任務(wù)的工作狀態(tài)進(jìn)棧 e.ptr=p-lchild;e.task=Travel; Push(S,e); /迫切任務(wù)迫切任務(wù)(遍歷左子樹遍歷左子樹)進(jìn)棧進(jìn)棧 /if /while/InOrder_iter6.2.2 遍歷算法描述遍歷算法描述 后序堆棧算法：后序堆棧算法：void PostOrder_iter( BiTree BT，void(*visit)( BiTree ) ) / 利用棧實(shí)現(xiàn)中序遍歷二叉樹，利用棧實(shí)現(xiàn)中序遍歷二叉樹，T為指向二叉

55、樹的根結(jié)點(diǎn)的頭指針為指向二叉樹的根結(jié)點(diǎn)的頭指針 InitStack(S); e.ptr=BT; e.task=Travel; / e為棧元素為棧元素 if(BT) Push(S, e); / 布置初始任務(wù)布置初始任務(wù) while(!StackEmpty(S) / 每次處理一項(xiàng)任務(wù)每次處理一項(xiàng)任務(wù) Pop(S,e); if(e.task=Visit) visit(e.ptr);/ 處理訪問任務(wù)處理訪問任務(wù) else if(e.ptr) / 處理非空樹的遍歷任務(wù)處理非空樹的遍歷任務(wù) p=e.ptr; e.ptr=p; e.task=Visit; Push(S,e); /處理訪問任務(wù)的工作狀態(tài)進(jìn)棧處

56、理訪問任務(wù)的工作狀態(tài)進(jìn)棧 e.ptr=p-rchild; e.task= Travel; Push(S,e); /不迫切任務(wù)不迫切任務(wù) e.ptr=p-lchild; Push(S,e); /迫切任務(wù)迫切任務(wù)(遍歷左子樹遍歷左子樹)進(jìn)棧進(jìn)棧 /if /while/PostOrder_iter6.2.3 二叉樹遍歷應(yīng)用舉例二叉樹遍歷應(yīng)用舉例二叉樹的遍歷是二叉樹各種操作的基礎(chǔ)，例如求結(jié)點(diǎn)二叉樹的遍歷是二叉樹各種操作的基礎(chǔ)，例如求結(jié)點(diǎn)雙親、結(jié)點(diǎn)的孩子、判定結(jié)點(diǎn)所在層次等，甚至建立雙親、結(jié)點(diǎn)的孩子、判定結(jié)點(diǎn)所在層次等，甚至建立二叉樹都要利用遍歷。二叉樹都要利用遍歷。6.2.3.1 建立二叉鏈表建立二叉

57、鏈表按先序建立二叉鏈表：按先序建立二叉鏈表： 輸入根結(jié)點(diǎn)輸入根結(jié)點(diǎn) 若為若為“#”，則為空樹，則為空樹 否則否則 生成新結(jié)點(diǎn)，設(shè)置生成新結(jié)點(diǎn)，設(shè)置data 遞歸建立其左子樹遞歸建立其左子樹 遞歸建立其右子樹遞歸建立其右子樹ABCEDn輸入順序：輸入順序：AB#DE#C#AB#DE#C#6.2.3 二叉樹遍歷應(yīng)用舉例二叉樹遍歷應(yīng)用舉例 建立二叉鏈表（算法建立二叉鏈表（算法6.3）void CreatebiTree(BiTree &T) /在先序遍歷二叉樹過程中輸入結(jié)點(diǎn)字符，建立二叉鏈表在先序遍歷二叉樹過程中輸入結(jié)點(diǎn)字符，建立二叉鏈表 /指針指針T指向所建二叉樹的根結(jié)點(diǎn)指向所建二叉樹的根結(jié)

58、點(diǎn) cin ch ； if(ch=#) T=NULL; / 建空樹建空樹 else T = new BiTNode ; / 訪問訪問操作為生成根結(jié)點(diǎn)操作為生成根結(jié)點(diǎn) T-data = ch; CreateBiTree(T-lchild); /遞歸建遞歸建(遍歷遍歷)左子樹左子樹 CreateBiTree(T-rchild); /遞歸建遞歸建(遍歷遍歷)右子樹右子樹 /else/CreateBiTree AB#DE#C#ABCED6.2.3 二叉樹遍歷應(yīng)用舉例二叉樹遍歷應(yīng)用舉例 6.2.3.2 求二叉樹的深度求二叉樹的深度深度（二叉樹）深度（二叉樹）= MAX（葉子結(jié)點(diǎn)所在層次的最大值）（葉子結(jié)

59、點(diǎn)所在層次的最大值） 先序算法先序算法6.4void BiTreeDepth(BiTree T, int h, int &depth) / h為為T指向結(jié)點(diǎn)所在層次，指向結(jié)點(diǎn)所在層次，T指向根，則指向根，則h的初值為的初值為1， / depth為當(dāng)前求得的最大層次為當(dāng)前求得的最大層次,其初值為其初值為0 if(T) if (hdepth) depth=h; BiTreeDepth(T-lchild, h+1, depth); BiTreeDepth(T-rchild, h+1, depth); / if/ BiTreeDepth 最初的調(diào)用語句為：最初的調(diào)用語句為： d=0; BiTr

60、eeDepth(r,1,d);6.2.3 二叉樹遍歷應(yīng)用舉例二叉樹遍歷應(yīng)用舉例D=0D=0H=1H=1D=1D=1H=1H=1D=2D=2H=2H=2D=3D=3H=3H=3D=3D=3H=2H=2D=4D=4H=4H=4D=4D=4H=4H=4D=4D=4H=3H=3D=3D=3H=3H=3D=4D=4D:depthD:depthH:hH:h6.2.3 二叉樹遍歷應(yīng)用舉例二叉樹遍歷應(yīng)用舉例 后序算法后序算法 6.5深度深度 = MAX（左子樹的深度（左子樹的深度,右子樹的深度）右子樹的深度）+1int BiTreeDepth(BiTree T) / 后序遍歷求后序遍歷求T所指二叉樹的深度所指二叉樹的深度 if(!T) return 0; el