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

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

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

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

4、譜和各種世界中也廣泛存在，如人類(lèi)社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)都可用樹(shù)來(lái)形象表示。本章重點(diǎn)社會(huì)組織機(jī)構(gòu)都可用樹(shù)來(lái)形象表示。本章重點(diǎn)討論二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及各種操作，并研究樹(shù)討論二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及各種操作，并研究樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換關(guān)系。和森林與二叉樹(shù)的轉(zhuǎn)換關(guān)系。第第6章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù) 到目前為止，我們已經(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ù)之間可能有祖先-后后代、上級(jí)代、上級(jí)-下屬、整體下屬、整體-部分

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

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

7、如圖所示的用樹(shù)形表示的模塊得到如圖所示的用樹(shù)形表示的模塊層次結(jié)構(gòu)。該樹(shù)給出了某文字處理層次結(jié)構(gòu)。該樹(shù)給出了某文字處理器的一種可行的模塊分解圖。器的一種可行的模塊分解圖。第第6章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù) 例例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é)科教材科教材科 何謂樹(shù)狀結(jié)構(gòu)何謂樹(shù)狀結(jié)構(gòu) 樹(shù)是樹(shù)是n(n0)個(gè)結(jié)點(diǎn)的有限集。個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹(shù)中在任意一棵非空樹(shù)中：(1)有有且僅有一個(gè)特定的稱(chēng)為

8、根的結(jié)且僅有一個(gè)特定的稱(chēng)為根的結(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è)集合本身又是一棵樹(shù)，并且個(gè)集合本身又是一棵樹(shù)，并且稱(chēng)為根的子樹(shù)。稱(chēng)為根的子樹(shù)。 若一棵樹(shù)中的結(jié)點(diǎn)可以有若一棵樹(shù)中的結(jié)點(diǎn)可以有n個(gè)子結(jié)點(diǎn)，則稱(chēng)這樣的樹(shù)為個(gè)子結(jié)點(diǎn)，則稱(chēng)這樣的樹(shù)為n元樹(shù)，例如二叉樹(shù)中的結(jié)點(diǎn)，元樹(shù)，例如二叉樹(shù)中的結(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ù)語(yǔ)樹(shù)的定義和基本術(shù)語(yǔ) 樹(shù)的相關(guān)名稱(chēng)及意義樹(shù)的相關(guān)名稱(chēng)及意

9、義 根結(jié)點(diǎn)（根結(jié)點(diǎn)（root node）一棵樹(shù)中沒(méi)有父結(jié)點(diǎn)的結(jié)點(diǎn)，稱(chēng)為根結(jié)點(diǎn)一棵樹(shù)中沒(méi)有父結(jié)點(diǎn)的結(jié)點(diǎn)，稱(chēng)為根結(jié)點(diǎn) 葉（子）結(jié)點(diǎn)葉（子）結(jié)點(diǎn)leaf node或終端結(jié)點(diǎn)或終端結(jié)點(diǎn)terminal node一棵樹(shù)中沒(méi)有子結(jié)點(diǎn)的結(jié)點(diǎn)，稱(chēng)為葉（子）結(jié)點(diǎn)或終端結(jié)點(diǎn)一棵樹(shù)中沒(méi)有子結(jié)點(diǎn)的結(jié)點(diǎn)，稱(chēng)為葉（子）結(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)，稱(chēng)為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)除了葉（子）結(jié)點(diǎn)以外的其他結(jié)點(diǎn)，稱(chēng)為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn) ADCBEFGHI葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)根結(jié)點(diǎn)根結(jié)點(diǎn)6.1 樹(shù)的定義和基本術(shù)語(yǔ)樹(shù)的定義和基本術(shù)語(yǔ)非終端結(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為樹(shù)根的子樹(shù)為樹(shù)根的子樹(shù), 則則x為為y的父結(jié)點(diǎn)（父親），而的父結(jié)點(diǎn)（父親），而y為為x的子結(jié)點(diǎn)（孩子）。的子結(jié)點(diǎn)（孩子）。 兄弟（兄弟（sibling） 同一個(gè)父結(jié)點(diǎn)之子結(jié)點(diǎn)，稱(chēng)為兄弟同一個(gè)父結(jié)點(diǎn)之子結(jié)點(diǎn)，稱(chēng)為兄弟如圖如圖B、C、D的父結(jié)點(diǎn)均為的父結(jié)點(diǎn)均為A，故，故B、C、D互為兄弟互為兄弟 結(jié)點(diǎn)的度（結(jié)點(diǎn)的度（degree）結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)，稱(chēng)為結(jié)點(diǎn)的度。結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)，稱(chēng)為結(jié)點(diǎn)的度。如圖，如圖，A的度為的度為3，B的度為的度為3，C的度為的度為1，最大的度值為，最大的度值為

11、3，故樹(shù)為，故樹(shù)為3元元樹(shù)。樹(shù)。 層次（層次（level）層次為結(jié)點(diǎn)之特性值，將根結(jié)點(diǎn)之層次設(shè)為層次為結(jié)點(diǎn)之特性值，將根結(jié)點(diǎn)之層次設(shè)為1，其子結(jié)點(diǎn)為，其子結(jié)點(diǎn)為2，依此類(lèi)推。，依此類(lèi)推。如圖，層次為如圖，層次為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ù)語(yǔ)樹(shù)的定義和基本術(shù)語(yǔ)ADCBEFG HI深度（深度（depth）或高度（）或高度（height）葉子結(jié)點(diǎn)的最大層次數(shù)稱(chēng)為樹(shù)葉子結(jié)點(diǎn)的最大層次數(shù)稱(chēng)為樹(shù)的深度的深度。 如圖，葉子最大層次值為如圖，葉子最大層次值為3，故樹(shù)，故樹(shù) T的深度為的深度為3祖先（祖先（ance

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

13、T2) = C，GTree-D(T3) = D，H，I，J，MB、C、D為三棵子樹(shù)的根，且互不相交為三棵子樹(shù)的根，且互不相交2. T1又分為兩個(gè)互不相交的又分為兩個(gè)互不相交的Tree-E(T11)=E，K，L 和和Tree-F(T12)=FT2又分為一個(gè)樹(shù)又分為一個(gè)樹(shù)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每棵子樹(shù)的結(jié)構(gòu)均符合上

14、述定義每棵子樹(shù)的結(jié)構(gòu)均符合上述定義6.1 樹(shù)的定義和基本術(shù)語(yǔ)樹(shù)的定義和基本術(shù)語(yǔ) 例例3：不是一棵樹(shù)：不是一棵樹(shù) 因?yàn)橐驗(yàn)?子樹(shù)子樹(shù)Tree-H=H，M子樹(shù)子樹(shù)Tree-I=I，M出現(xiàn)了交叉，違出現(xiàn)了交叉，違反樹(shù)的定義。反樹(shù)的定義。 樹(shù)的其它表示形式樹(shù)的其它表示形式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樹(shù)的表示形式樹(shù)的表示形式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ù)語(yǔ)二叉樹(shù)的定義和基本術(shù)語(yǔ) 二叉樹(shù)（二叉樹(shù)（binary tree）是）是n(n0)個(gè)數(shù)據(jù)元素的有限集，個(gè)數(shù)據(jù)元素的有限集，它或?yàn)榭占驗(yàn)榭占?n0)，或者含有唯一的稱(chēng)為根的元素，且其，或者含有唯一的稱(chēng)為根的元素，且其余元素分成余元素分成兩個(gè)兩個(gè)互不相交的子集，每個(gè)子集自身也是一棵互不相交的子集，每個(gè)子集自身也是一棵二叉樹(shù)二叉樹(shù)，分別稱(chēng)為根的，分別稱(chēng)為根的左子樹(shù)左子樹(shù)和和右子樹(shù)右子樹(shù)。 集合為空的樹(shù)簡(jiǎn)稱(chēng)為空樹(shù)。集合為空的樹(shù)簡(jiǎn)稱(chēng)為空樹(shù)。 樹(shù)中的元素稱(chēng)為結(jié)點(diǎn)。

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

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

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

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

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

22、度。Parent(T,e)n初始條件：二叉樹(shù)初始條件：二叉樹(shù)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初始條件：二叉樹(shù)初始條件：二叉樹(shù)T存在，存在，e是是T中某個(gè)結(jié)點(diǎn)。中某個(gè)結(jié)點(diǎn)。n操作結(jié)果：返回操作結(jié)果：返回e的左孩子。若的左孩子。若e無(wú)左孩子，則返回?zé)o左孩子，則返回“空空”。RightChild(T,e)n初始條件：二叉樹(shù)初始條件：二叉樹(shù)T存在，存在，e是是T中某個(gè)結(jié)點(diǎn)。中某個(gè)結(jié)點(diǎn)。n操作結(jié)果：返回操作結(jié)果：返回e的右孩子。若的右孩子。若e

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

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

25、DeleteChild(T,p,LR)n初始條件：二叉樹(shù)初始條件：二叉樹(shù)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)的左或右子樹(shù)。子樹(shù)。Traverse（T）n初始條件：二叉樹(shù)初始條件：二叉樹(shù)T存在存在n操作結(jié)果：依某條搜索路徑遍歷操作結(jié)果：依某條搜索路徑遍歷T，對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行一次，對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行一次且僅一次訪問(wèn)（例如輸出結(jié)點(diǎn)元素值）且僅一次訪問(wèn)（例如輸出結(jié)點(diǎn)元素值）6.1.3 二叉樹(shù)的幾個(gè)基本性質(zhì)二叉樹(shù)的幾個(gè)基本性質(zhì) 性質(zhì)性質(zhì)1 在二叉樹(shù)的第在二叉樹(shù)的第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是對(duì)的。是對(duì)的。 現(xiàn)在假定對(duì)所有現(xiàn)在假定對(duì)所有j（1jn0 =n2+16.1.3 二叉樹(shù)的幾個(gè)基本性質(zhì)二叉樹(shù)的幾個(gè)基本性質(zhì)性質(zhì)性質(zhì)4 具有具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為證明：證明：n 假設(shè)深度為假設(shè)深度為k，則根據(jù)性質(zhì)，則根據(jù)性質(zhì)2和完全二叉樹(shù)的定義有和完全二叉樹(shù)的定義有 2k-1-1 n 2k -1，或，或2k-1 n 2k n 取對(duì)數(shù)便有取對(duì)數(shù)便有k-1 log2n 1，則其雙親結(jié)點(diǎn)，則其雙親結(jié)點(diǎn)parent(i)

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

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

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

30、存儲(chǔ)結(jié)構(gòu)（從下標(biāo)為順序存儲(chǔ)結(jié)構(gòu)（從下標(biāo)為1的單元開(kāi)始存儲(chǔ)）的單元開(kāi)始存儲(chǔ)）假設(shè)父結(jié)點(diǎn)編號(hào)為假設(shè)父結(jié)點(diǎn)編號(hào)為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 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.1.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 2. 鏈?zhǔn)酱鎯?chǔ)表示鏈?zhǔn)酱?/p>

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

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

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

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

35、二叉樹(shù)其樹(shù)狀結(jié)構(gòu)與結(jié)構(gòu)數(shù)組表示法如下：例如，有一棵二叉樹(shù)其樹(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，表示其沒(méi)有右子，表示其沒(méi)有右子結(jié)點(diǎn)，而結(jié)點(diǎn)結(jié)點(diǎn)，而結(jié)點(diǎn)D和和E都是葉結(jié)點(diǎn)（都是葉結(jié)點(diǎn)（leaf node ）沒(méi)有子結(jié)點(diǎn)，故）沒(méi)有子結(jié)點(diǎn)，故left 和和right字段均為字段均為-1。索引值索引值leftleftd

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

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

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

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

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

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

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

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

44、遍歷二叉樹(shù)的步驟如下：后序遍歷二叉樹(shù)的步驟如下：if 二叉樹(shù)為空二叉樹(shù)為空 then 遍歷結(jié)束遍歷結(jié)束else （1）后序訪問(wèn)左子樹(shù)）后序訪問(wèn)左子樹(shù) （2）后序訪問(wèn)右子樹(shù)）后序訪問(wèn)右子樹(shù) （3）訪問(wèn)當(dāng)前結(jié)點(diǎn)）訪問(wèn)當(dāng)前結(jié)點(diǎn)6.2.1 問(wèn)題的提出問(wèn)題的提出二叉樹(shù)遍歷過(guò)程示意圖二叉樹(shù)遍歷過(guò)程示意圖 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í) 已知某二叉樹(shù)的先序序列為已知某二叉樹(shù)的先序序列為: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í) 已知某二叉樹(shù)的后序序列為已知某二叉樹(shù)的后序序列為: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為根指針的二叉樹(shù)為根指針的二叉樹(shù) void Preorder (BiTree T，void(*visit)( BiTree ) if(T) / T=NULL時(shí)，二叉樹(shù)為空樹(shù)，不做任何操作時(shí)，二叉樹(shù)為空樹(shù)，不做任何操作 visit(T); / 通過(guò)函數(shù)指針通過(guò)函數(shù)指針*visit訪問(wèn)根結(jié)點(diǎn)，訪問(wèn)根結(jié)點(diǎn)， 以便靈活完成相應(yīng)的操作以便靈活完

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

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

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

51、質(zhì)SElemType;/棧元素的類(lèi)型定義棧元素的類(lèi)型定義6.2.2 遍歷算法描述遍歷算法描述 先序堆棧算法：先序堆棧算法：void PreOrder_iter( BiTree BT，void(*visit)( BiTree ) ) / 利用棧實(shí)現(xiàn)中序遍歷二叉樹(shù)，利用棧實(shí)現(xiàn)中序遍歷二叉樹(shù)，T為指向二叉樹(shù)的根結(jié)點(diǎn)的頭指針為指向二叉樹(shù)的根結(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) / 處理非空樹(shù)的遍歷任務(wù)處理非空樹(shù)的遍歷任務(wù) visit(e.ptr); / p=e.ptr; e.ptr=p-rchild; Push(S,e); / 最不迫切任務(wù)最不迫切任務(wù)(遍歷右子樹(shù)遍歷右子樹(shù))進(jìn)棧進(jìn)棧 e.ptr=p-lchild; /直接處理迫切任務(wù)直接處理迫切任務(wù)(遍歷左子樹(shù)遍歷左子樹(shù)) /if /while/PreOrder_iter6.2.2 遍歷算法描述遍歷算法描述 中序堆棧算法：中序堆棧算法：void InOrder_iter( BiTree BT，void(*visit)( BiTree ) )/ 利用棧實(shí)現(xiàn)中序遍歷二叉樹(shù)，利用棧實(shí)

53、現(xiàn)中序遍歷二叉樹(shù)，T為指向二叉樹(shù)的根結(jié)點(diǎn)的頭指針為指向二叉樹(shù)的根結(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èn)任務(wù)處理訪問(wèn)任務(wù) else if(e.ptr) / 處理非空樹(shù)的遍歷任務(wù)處理非空樹(shù)的遍歷任務(wù) p=e.ptr; e.ptr=p-rchild; Push(S,e); / 最不迫切

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

55、樹(shù)的根結(jié)點(diǎn)的頭指針為指向二叉樹(shù)的根結(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èn)任務(wù)處理訪問(wèn)任務(wù) else if(e.ptr) / 處理非空樹(shù)的遍歷任務(wù)處理非空樹(shù)的遍歷任務(wù) p=e.ptr; e.ptr=p; e.task=Visit; Push(S,e); /處理訪問(wèn)任務(wù)的工作狀態(tài)進(jìn)棧處

56、理訪問(wèn)任務(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ù)(遍歷左子樹(shù)遍歷左子樹(shù))進(jìn)棧進(jìn)棧 /if /while/PostOrder_iter6.2.3 二叉樹(shù)遍歷應(yīng)用舉例二叉樹(shù)遍歷應(yīng)用舉例二叉樹(shù)的遍歷是二叉樹(shù)各種操作的基礎(chǔ)，例如求結(jié)點(diǎn)二叉樹(shù)的遍歷是二叉樹(shù)各種操作的基礎(chǔ)，例如求結(jié)點(diǎn)雙親、結(jié)點(diǎn)的孩子、判定結(jié)點(diǎn)所在層次等，甚至建立雙親、結(jié)點(diǎn)的孩子、判定結(jié)點(diǎn)所在層次等，甚至建立二叉樹(shù)都要利用遍歷。二叉樹(shù)都要利用遍歷。6.2.3.1 建立二叉鏈表建立二叉

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

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

59、點(diǎn)所在層次的最大值） 先序算法先序算法6.4void BiTreeDepth(BiTree T, int h, int &depth) / h為為T(mén)指向結(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)用語(yǔ)句為：最初的調(diào)用語(yǔ)句為： d=0; BiTr

60、eeDepth(r,1,d);6.2.3 二叉樹(shù)遍歷應(yīng)用舉例二叉樹(shù)遍歷應(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 二叉樹(shù)遍歷應(yīng)用舉例二叉樹(shù)遍歷應(yīng)用舉例 后序算法后序算法 6.5深度深度 = MAX（左子樹(shù)的深度（左子樹(shù)的深度,右子樹(shù)的深度）右子樹(shù)的深度）+1int BiTreeDepth(BiTree T) / 后序遍歷求后序遍歷求T所指二叉樹(shù)的深度所指二叉樹(shù)的深度 if(!T) return 0; el