數(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 二叉樹的幾個基本性質(zhì)二叉樹的幾個基本性質(zhì) 6.2.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) 6.2 遍歷二叉樹和線索二叉遍歷二叉樹和線索二叉樹樹 6.2.1 問題的提出問題的提出 6.2.2 遍歷算法描述遍歷算法描述 6.2.3 二叉樹遍歷應用舉例二叉樹遍歷應用舉例

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 樹的應用樹的應用n 6.4.1 6.4.1 堆排序的實現(xiàn)堆排序的實現(xiàn)n 6.4.2 6.4.2 二叉排序樹二叉排序樹n 6.4.3 6.4.3 赫夫曼樹及其應用赫夫曼樹及其應用6.1 二叉樹二叉樹6.1.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語6.1.2 二叉樹

3、的定義和基本術(shù)語二叉樹的定義和基本術(shù)語6.1.3 二叉樹的幾個基本性質(zhì)二叉樹的幾個基本性質(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)。樹在計算機領(lǐng)域中。樹在計算機領(lǐng)域中得到廣泛應用，如文件管理中的得到廣泛應用，如文件管理中的目錄結(jié)構(gòu)目錄結(jié)構(gòu)、數(shù)、數(shù)據(jù)庫系統(tǒng)中的據(jù)庫系統(tǒng)中的信息組織形式信息組織形式等。樹結(jié)構(gòu)在客觀等。樹結(jié)構(gòu)在客觀世界中也廣泛存在，如人類社會的族

4、譜和各種世界中也廣泛存在，如人類社會的族譜和各種社會組織機構(gòu)都可用樹來形象表示。本章重點社會組織機構(gòu)都可用樹來形象表示。本章重點討論二叉樹的存儲結(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、化，可以把大的復雜的任通過模塊化，可以把大的復雜的任務分成一組小的不太復雜的任務。務分成一組小的不太復雜的任務。模塊化的目標是把軟件系統(tǒng)分成許模塊化的目標是把軟件系統(tǒng)分成許多功能不相關(guān)的部分或模塊以便于多功能不相關(guān)的部分或模塊以便于進行相對獨立的開發(fā)。由于解決幾進行相對獨立的開發(fā)。由于解決幾個小問題比解決大問題更容易一些，個小問題比解決大問題更容易一些，因此模塊化方法可以縮短整個軟件因此模塊化方法可以縮短整個軟件的開發(fā)時間。另外，不同的程序員的開發(fā)時間。另外，不同的程序員可以同時開發(fā)不同的模塊。如果有可以同時開發(fā)不同的模塊。如果有必要，每個模塊可以再細分，從而必要，每個模塊可以再細分，從而得到

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

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

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

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

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

12、stor） 由某結(jié)點由某結(jié)點X到根結(jié)點之路徑上的所有結(jié)點，均稱為到根結(jié)點之路徑上的所有結(jié)點，均稱為X之祖先之祖先樹林（樹林（forest） n=0個樹的集合稱為樹林個樹的集合稱為樹林 若將一樹的根結(jié)點移去，所剩這恰是一樹林若將一樹的根結(jié)點移去，所剩這恰是一樹林.ADCBEFG HIDCBEFGHI6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語A6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語例例1：只有根結(jié)點的樹：只有根結(jié)點的樹A例例2：一般的樹：一般的樹1.此樹此樹Tree-A 共有共有13個結(jié)點個結(jié)點,是由三棵子樹組成：是由三棵子樹組成：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又分為兩個互不相交的又分為兩個互不相交的Tree-E(T11)=E，K，L 和和Tree-F(T12)=FT2又分為一個樹又分為一個樹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：不是一棵樹：不是一棵樹 因為因為:子樹子樹Tree-H=H，M子樹子樹Tree-I=I，M出現(xiàn)了交叉，違出現(xiàn)了交叉，違反樹的定義。反樹的定義。 樹的其它表示形式樹的其它表示形式Tree-A的結(jié)構(gòu)：的結(jié)構(gòu)：結(jié)點結(jié)點A包括包括B,C,D結(jié)點結(jié)點B包括包括E,F結(jié)點結(jié)點C包括包括G結(jié)點結(jié)點D包括包括H,I,J結(jié)點結(jié)點E包括包括K,L結(jié)點結(jié)點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)個數(shù)據(jù)元素的有限集，個數(shù)據(jù)元素的有限集，它或為空集它或為空集(n0)，或者含有唯一的稱為根的元素，且其，或者含有唯一的稱為根的元素，且其余元素分成余元素分成兩個兩個互不相交的子集，每個子集自身也是一棵互不相交的子集，每個子集自身也是一棵二叉樹二叉樹，分別稱為根的，分別稱為根的左子樹左子樹和和右子樹右子樹。 集合為空的樹簡稱為空樹。集合為空的樹簡稱為空樹。 樹中的元素稱為結(jié)點。

16、樹中的元素稱為結(jié)點。ADCBEFBDE左子樹左子樹CF右子樹右子樹6.1.2 二叉樹的定義和基本術(shù)語二叉樹的定義和基本術(shù)語 根以外的任意兩個結(jié)點不可能同根以外的任意兩個結(jié)點不可能同時在同一棵子樹中出現(xiàn)。時在同一棵子樹中出現(xiàn)。 二叉樹的子樹有左右之分，不能二叉樹的子樹有左右之分，不能任意顛倒。任意顛倒。 如圖所示如圖所示 A為根結(jié)點為根結(jié)點 D、G、H、J為葉子結(jié)點為葉子結(jié)點 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)練習：如果只有三個結(jié)點，形態(tài)如何？練習：如果只有三個結(jié)點，形態(tài)如何？左、右子樹左、右子樹具全的二叉樹具全的二叉樹左子樹為空左子樹為空的二叉樹的二叉樹空的二叉樹空的二叉樹僅有根結(jié)點僅有根結(jié)點的二叉樹的二叉樹右子樹為空右子樹為空的二叉樹的二叉樹 滿二叉樹（滿二叉樹（full binary tree） 若二叉樹中所有的分支結(jié)點的度數(shù)都為若二叉樹中所有的分支結(jié)點的度數(shù)都為2，且葉子，且葉子結(jié)點都在同一層次上，則稱這類二叉樹為滿二叉樹。結(jié)點都在同一層次上，則稱這類二叉樹為滿二叉樹。若

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

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

20、母曾祖母曾祖父曾祖父曾祖母曾祖母外曾祖母外曾祖母外曾祖父外曾祖父外曾祖父外曾祖父祖父祖父外祖父外祖父祖母祖母外祖母外祖母父親父親母親母親女方女方家庭家庭1家庭家庭2不能有相同結(jié)點，不能有相同結(jié)點，否則為否則為近親近親結(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中某個結(jié)點。中某個結(jié)點。n操作結(jié)果：若操作結(jié)果：若e是是T的非根結(jié)點，則返回它的雙親，的非根結(jié)點，則返回它的雙親， 否則返回否則返回“空空”。LeftChiild(T,e)n初始條件：二叉樹初始條件：二叉樹T存在，存在，e是是T中某個結(jié)點。中某個結(jié)點。n操作結(jié)果：返回操作結(jié)果：返回e的左孩子。若的左孩子。若e無左孩子，則返回無左孩子，則返回“空空”。RightChild(T,e)n初始條件：二叉樹初始條件：二叉樹T存在，存在，e是是T中某個結(jié)點。中某個結(jié)點。n操作結(jié)果：返回操作結(jié)果：返回e的右孩子。若的右孩子。若e

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

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

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

26、-1個結(jié)點（個結(jié)點（i 1）利用數(shù)學歸納法證明：利用數(shù)學歸納法證明： i =1時，只有一個根結(jié)點，顯然時，只有一個根結(jié)點，顯然2i-1 = 20 =1是對的。是對的。 現(xiàn)在假定對所有現(xiàn)在假定對所有j（1jn0 =n2+16.1.3 二叉樹的幾個基本性質(zhì)二叉樹的幾個基本性質(zhì)性質(zhì)性質(zhì)4 具有具有n個結(jié)點的完全二叉樹的深度為個結(jié)點的完全二叉樹的深度為證明：證明：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é)點，則其雙親結(jié)點parent(i)

27、的編號是的編號是（2）如果）如果2in，則編號為，則編號為i的結(jié)點無左孩子（編號為的結(jié)點無左孩子（編號為i的結(jié)點為葉子結(jié)點）；否則其左孩子結(jié)點的結(jié)點為葉子結(jié)點）；否則其左孩子結(jié)點lChild(i)的編的編號是號是2i（3）如果）如果2i+1n，則編號為，則編號為i的結(jié)點無右左孩子；否的結(jié)點無右左孩子；否則其右孩子結(jié)點則其右孩子結(jié)點rChild(i)的編號是的編號是2i+1 1log2 n 2/ i 1log2 n6.1.3 二叉樹的幾個基本性質(zhì)二叉樹的幾個基本性質(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é)點，為葉子結(jié)點 1.1.順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) 用一組地址連續(xù)的存儲單元存儲二叉樹中的數(shù)據(jù)元素用一組地址連續(xù)的存儲單元存儲二叉樹中的數(shù)據(jù)元素 將完全二叉樹編號為的結(jié)點存儲在一維數(shù)組下標為的單元中將完全二叉樹編號為的結(jié)點存儲在一維數(shù)組下標為的單元中 一般二叉樹可能浪費大量存儲空間一般二叉樹可能浪費大量存儲空間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é)點數(shù)最大值結(jié)點數(shù)最大值typedef struct TElemType *data; /存儲空間基址存儲空間基址 int nodenum; /樹中結(jié)點數(shù)樹中結(jié)點數(shù)SqBiTree; /完全二叉樹的順序存儲結(jié)構(gòu)完全二叉樹的順序存儲結(jié)構(gòu) 1.順序

30、存儲結(jié)構(gòu)（從下標為順序存儲結(jié)構(gòu)（從下標為1的單元開始存儲）的單元開始存儲）假設(shè)父結(jié)點編號為假設(shè)父結(jié)點編號為n，可以得到：，可以得到： （1）左子結(jié)點為父結(jié)點乘以）左子結(jié)點為父結(jié)點乘以2：2*n （2）右子結(jié)點為父結(jié)點乘以）右子結(jié)點為父結(jié)點乘以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. 鏈式存儲表示鏈式存

31、儲表示二叉樹結(jié)點的邏輯結(jié)構(gòu)二叉樹結(jié)點的邏輯結(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. 鏈式存儲鏈式存儲表示表示 三叉鏈表三叉鏈表 typedef struct BiTNode TElemType data; /結(jié)點數(shù)據(jù)結(jié)點數(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個字段，其中個字段，其中一個字段是用來存放結(jié)點的數(shù)據(jù)內(nèi)容，而另兩個字段則是分別一個字段是用來存放結(jié)點的數(shù)據(jù)內(nèi)容，而另兩個字段則是分別存放左子樹和右子樹在數(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é)點置于數(shù)組結(jié)構(gòu)中索引值為，會將根結(jié)點置于數(shù)組結(jié)構(gòu)中索引值為0之處，將結(jié)點值存在之處，將結(jié)點值存在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é)點為圖中根結(jié)點為A，故，故A在結(jié)構(gòu)數(shù)組索引值為之處，其左子結(jié)點在結(jié)構(gòu)數(shù)組索引值為之處，其左子結(jié)點B在索引值在索引值1，右子結(jié)點，右子結(jié)點B在索引值在索引值2，故結(jié)點，故結(jié)點A的的left字段和字段和right字段分別為字段分別為1和和2，而結(jié)點，而結(jié)點C的的right字段值為字段值為-1，表示其沒有右子，表示其沒有右子結(jié)點，而結(jié)點結(jié)點，而結(jié)點D和和E都是葉結(jié)點（都是葉結(jié)點（leaf node ）沒有子結(jié)點，故）沒有子結(jié)點，故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 二叉樹遍歷應用舉例二叉樹遍歷應用舉例6.2.4 線索二叉樹線索二叉樹6.2.1 問題的提出問題的提出 遍歷二叉樹（遍歷二叉樹（Traversing binary tree）：如何按某條搜索路徑）：如何按某條搜索路徑巡訪樹中每個結(jié)點，使得每個結(jié)點均被訪問到且僅被訪問一次。巡訪樹中每個結(jié)點，使得每個結(jié)點均被訪問到且僅被訪問一次。 訪問：存取操作、打印等加工處

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

38、種遍歷方式： 先序遍歷方式先序遍歷方式 中序遍歷方式中序遍歷方式 后序遍歷方式后序遍歷方式6.2.1 問題的提出問題的提出先序遍歷（先序遍歷（Preorder traversal）是是先遍歷先遍歷根根結(jié)點，再遍歷結(jié)點，再遍歷左子樹左子樹，最后，最后遍歷遍歷右子樹右子樹，若一棵二叉樹如右圖，若一棵二叉樹如右圖，則先序遍歷的順序為：則先序遍歷的順序為：DLR,也就是說也就是說每當遍歷一個結(jié)點就先處理該結(jié)點，每當遍歷一個結(jié)點就先處理該結(jié)點，之后先向左方前進，直到無法前進才之后先向左方前進，直到無法前進才往右方走。往右方走。左圖中從根結(jié)點左圖中從根結(jié)點A開始，先往左開始，先往左子樹子樹B再到再到D，由

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

40、 （2）先序訪問左子樹）先序訪問左子樹 （3）先序訪問右子樹）先序訪問右子樹6.2.1 問題的提出問題的提出中序遍歷（中序遍歷（Inorder traversal）是先遍是先遍歷歷左子樹左子樹，再，再根根結(jié)點，最后才遍歷結(jié)點，最后才遍歷右子右子樹樹，若一棵二叉樹如右圖，則中序遍歷，若一棵二叉樹如右圖，則中序遍歷的順序為：的順序為：LDR，也就是說一開始先往，也就是說一開始先往左方前進，直到無法前進才處理結(jié)點，左方前進，直到無法前進才處理結(jié)點，之后再往右方前進。之后再往右方前進。ADCBGEFHI左圖中從根結(jié)點左圖中從根結(jié)點A開始，一直開始，一直往左走到往左走到D無法再前進，則處理無法再前進，則

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

42、左子樹 （2）訪問當前結(jié)點）訪問當前結(jié)點 （3）中序訪問右子樹）中序訪問右子樹6.2.1 問題的提出問題的提出后序遍歷（后序遍歷（Postorder traversal）是是先遍歷先遍歷左子樹左子樹，再遍歷，再遍歷右子樹右子樹，最后，最后才遍歷才遍歷根根結(jié)點，若一棵二叉樹如右圖，結(jié)點，若一棵二叉樹如右圖，則后序遍歷的順序為：則后序遍歷的順序為：LRD，也就是，也就是說一開始先往左方前進，直到無法前說一開始先往左方前進，直到無法前進才處再往右方前進，最后才處理結(jié)進才處再往右方前進，最后才處理結(jié)點。點。左圖中從根結(jié)點左圖中從根結(jié)點A開始，一直往左開始，一直往左走到走到D無法再前進，則往無法再前進，

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

44、遍歷二叉樹的步驟如下：后序遍歷二叉樹的步驟如下：if 二叉樹為空二叉樹為空 then 遍歷結(jié)束遍歷結(jié)束else （1）后序訪問左子樹）后序訪問左子樹 （2）后序訪問右子樹）后序訪問右子樹 （3）訪問當前結(jié)點）訪問當前結(jié)點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遍歷練習遍歷練習ADCBGFIJEH先序：先序：ABDGEHCFIJAB

45、DGEHCFIJ中序：中序：DGBEHACIFJDGBEHACIFJ后序：后序：GDHEBIJFCAGDHEBIJFCA遍歷練習遍歷練習 已知某二叉樹的先序序列為已知某二叉樹的先序序列為: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遍歷練習遍歷練習 已知某二叉樹的后序序列為已知某二叉樹的后序序列為: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時，二叉樹為空樹，不做任何操作時，二叉樹為空樹，不做任何操作 visit(T); / 通過函數(shù)指針通過函數(shù)指針*visit訪問根結(jié)點，訪問根結(jié)點， 以便靈活完成相應的操作以便靈活完

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

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

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

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

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

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

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

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

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

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

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

59、點所在層次的最大值） 先序算法先序算法6.4void BiTreeDepth(BiTree T, int h, int &depth) / h為為T指向結(jié)點所在層次，指向結(jié)點所在層次，T指向根，則指向根，則h的初值為的初值為1， / depth為當前求得的最大層次為當前求得的最大層次,其初值為其初值為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 二叉樹遍歷應用舉例二叉樹遍歷應用舉例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 二叉樹遍歷應用舉例二叉樹遍歷應用舉例 后序算法后序算法 6.5深度深度 = MAX（左子樹的深度（左子樹的深度,右子樹的深度）右子樹的深度）+1int BiTreeDepth(BiTree T) / 后序遍歷求后序遍歷求T所指二叉樹的深度所指二叉樹的深度 if(!T) return 0; el