數據結構中的樹

1、 第六章第六章 樹和二叉樹樹和二叉樹（ Tree & Binary tree Tree & Binary tree ） 主講：李耀國主講：李耀國第六章第六章 樹和二叉樹樹和二叉樹 6.1 樹的定義和基本術語樹的定義和基本術語 6.1.2 二叉樹二叉樹 6.2.1 二叉樹的定義和基本術語二叉樹的定義和基本術語 6.2.2 二叉樹的幾個基本性質二叉樹的幾個基本性質 6.2.3 二叉樹的存儲結構二叉樹的存儲結構 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 樹和森林的存儲結構樹和森林的存儲結構n 6.3.3 6.3.3 樹、森林與二叉樹的轉換樹、森林與二叉樹的轉換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 樹的定義和基本術語樹的定義和基本術語6.1.2 二叉樹

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

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

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

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

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

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

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

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

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

12、stor） 由某結點由某結點X到根結點之路徑上的所有結點，均稱為到根結點之路徑上的所有結點，均稱為X之祖先之祖先樹林（樹林（forest） n=0個樹的集合稱為樹林個樹的集合稱為樹林 若將一樹的根結點移去，所剩這恰是一樹林若將一樹的根結點移去，所剩這恰是一樹林.ADCBEFG HIDCBEFGHI6.1 樹的定義和基本術語樹的定義和基本術語A6.1 樹的定義和基本術語樹的定義和基本術語例例1：只有根結點的樹：只有根結點的樹A例例2：一般的樹：一般的樹1.此樹此樹Tree-A 共有共有13個結點個結點,是由三棵子樹組成：是由三棵子樹組成：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每棵子樹的結構均符合上

14、述定義每棵子樹的結構均符合上述定義6.1 樹的定義和基本術語樹的定義和基本術語 例例3：不是一棵樹：不是一棵樹 因為因為:子樹子樹Tree-H=H，M子樹子樹Tree-I=I，M出現(xiàn)了交叉，違出現(xiàn)了交叉，違反樹的定義。反樹的定義。 樹的其它表示形式樹的其它表示形式Tree-A的結構：的結構：結點結點A包括包括B,C,D結點結點B包括包括E,F結點結點C包括包括G結點結點D包括包括H,I,J結點結點E包括包括K,L結點結點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 二叉樹的定義和基本術語二叉樹的定義和基本術語 二叉樹（二叉樹（binary tree）是）是n(n0)個數據元素的有限集，個數據元素的有限集，它或為空集它或為空集(n0)，或者含有唯一的稱為根的元素，且其，或者含有唯一的稱為根的元素，且其余元素分成余元素分成兩個兩個互不相交的子集，每個子集自身也是一棵互不相交的子集，每個子集自身也是一棵二叉樹二叉樹，分別稱為根的，分別稱為根的左子樹左子樹和和右子樹右子樹。 集合為空的樹簡稱為空樹。集合為空的樹簡稱為空樹。 樹中的元素稱為結點。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

32、 F C C I I G G H H J J6.1.4 二叉樹的存儲結構二叉樹的存儲結構 2. 鏈式存儲鏈式存儲表示表示 三叉鏈表三叉鏈表 typedef struct BiTNode TElemType data; /結點數據結點數據 struct BiTNode *parent,*lchild,*rchild; BiTNode,*BiTree; /完全二叉樹的三叉鏈表結完全二叉樹的三叉鏈表結構構lchildlchildparentparentdatadatarchildrchilddatadataparentparentlchildlchildrchildrchild6.1.4 二叉樹的存

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

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

35、二叉樹其樹狀結構與結構數組表示法如下：例如，有一棵二叉樹其樹狀結構與結構數組表示法如下：圖中根結點為圖中根結點為A，故，故A在結構數組索引值為之處，其左子結點在結構數組索引值為之處，其左子結點B在索引值在索引值1，右子結點，右子結點B在索引值在索引值2，故結點，故結點A的的left字段和字段和right字段分別為字段分別為1和和2，而結點，而結點C的的right字段值為字段值為-1，表示其沒有右子，表示其沒有右子結點，而結點結點，而結點D和和E都是葉結點（都是葉結點（leaf node ）沒有子結點，故）沒有子結點，故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）：如何按某條搜索路徑）：如何按某條搜索路徑巡訪樹中每個結點，使得每個結點均被訪問到且僅被訪問一次。巡訪樹中每個結點，使得每個結點均被訪問到且僅被訪問一次。 訪問：存取操作、打印等加工處

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

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

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

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

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

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

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

44、遍歷二叉樹的步驟如下：后序遍歷二叉樹的步驟如下：if 二叉樹為空二叉樹為空 then 遍歷結束遍歷結束else （1）后序訪問左子樹）后序訪問左子樹 （2）后序訪問右子樹）后序訪問右子樹 （3）訪問當前結點）訪問當前結點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); / 通過函數指針通過函數指針*visit訪問根結點，訪問根結點， 以便靈活完成相應的操作以便靈活完

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、; / 通過函數指針通過函數指針*visit訪問根結點，訪問根結點， 以便靈活完成相應的操作以便靈活完成相應的操作 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); / 通過函數指針通過函數指針*visit訪問根結點，訪問根結點， 以便靈活完成相應的操作以便靈活完成相應的操作 6.2.2 遍歷算法描述遍歷算法描述 堆棧遍歷算法：堆棧遍歷算法：typedef enum Travel=1,Visit=0 TaskType;/為為Travel時工作狀態(tài)是遍歷，為時工作狀態(tài)是遍歷，為Visit時是訪問時是訪問typedef struct BiTree ptr; /指向二叉樹結點的指針指向二叉樹結點的指針 TaskType task;/任務的性質任務的性

51、質SElemType;/棧元素的類型定義棧元素的類型定義6.2.2 遍歷算法描述遍歷算法描述 先序堆棧算法：先序堆棧算法：void PreOrder_iter( BiTree BT，void(*visit)( BiTree ) ) / 利用棧實現(xiàn)中序遍歷二叉樹，利用棧實現(xiàn)中序遍歷二叉樹，T為指向二叉樹的根結點的頭指針為指向二叉樹的根結點的頭指針 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為指向二叉樹的根結點的頭指針為指向二叉樹的根結點的頭指針 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、樹的根結點的頭指針為指向二叉樹的根結點的頭指針 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 二叉樹遍歷應用舉例二叉樹遍歷應用舉例二叉樹的遍歷是二叉樹各種操作的基礎，例如求結點二叉樹的遍歷是二叉樹各種操作的基礎，例如求結點雙親、結點的孩子、判定結點所在層次等，甚至建立雙親、結點的孩子、判定結點所在層次等，甚至建立二叉樹都要利用遍歷。二叉樹都要利用遍歷。6.2.3.1 建立二叉鏈表建立二叉

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

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

59、點所在層次的最大值） 先序算法先序算法6.4void BiTreeDepth(BiTree T, int h, int &depth) / h為為T指向結點所在層次，指向結點所在層次，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 最初的調用語句為：最初的調用語句為： 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