數(shù)據(jù)結(jié)構(gòu)課件第5

1、第第5 5章章 樹樹 樹形結(jié)構(gòu)是元素之間具有分層關(guān)系的結(jié)構(gòu)，它樹形結(jié)構(gòu)是元素之間具有分層關(guān)系的結(jié)構(gòu)，它類似于自然界中的樹，應(yīng)用廣泛，是一類很重要的類似于自然界中的樹，應(yīng)用廣泛，是一類很重要的非線性數(shù)據(jù)結(jié)構(gòu)。非線性數(shù)據(jù)結(jié)構(gòu)。 在計(jì)算機(jī)應(yīng)用中，常出現(xiàn)嵌套的數(shù)據(jù)，樹結(jié)構(gòu)在計(jì)算機(jī)應(yīng)用中，常出現(xiàn)嵌套的數(shù)據(jù)，樹結(jié)構(gòu)提供了對(duì)該類數(shù)據(jù)的自然表示；提供了對(duì)該類數(shù)據(jù)的自然表示； 利用樹結(jié)構(gòu)，可以有效地解決一些算法問題。利用樹結(jié)構(gòu)，可以有效地解決一些算法問題。 由于結(jié)構(gòu)特征，樹形結(jié)構(gòu)常采用遞歸方式定義。由于結(jié)構(gòu)特征，樹形結(jié)構(gòu)常采用遞歸方式定義。被稱為遞歸數(shù)據(jù)結(jié)構(gòu)。有關(guān)樹的許多算法是遞歸的。被稱為遞歸數(shù)據(jù)結(jié)構(gòu)。有關(guān)樹

2、的許多算法是遞歸的。1 1、樹的基本概念；、樹的基本概念； 給出樹的定義，關(guān)于樹中的一些術(shù)語；給出樹的定義，關(guān)于樹中的一些術(shù)語；2 2、二叉樹的定義、性質(zhì)及其規(guī)范；、二叉樹的定義、性質(zhì)及其規(guī)范；3 3、二叉樹的遍歷等算法的實(shí)現(xiàn)；、二叉樹的遍歷等算法的實(shí)現(xiàn)；4 4、樹和森林的表示、存儲(chǔ)和遍歷；、樹和森林的表示、存儲(chǔ)和遍歷；5 5、二叉樹的應(yīng)用實(shí)例、二叉樹的應(yīng)用實(shí)例 哈夫曼樹和哈夫曼編碼。哈夫曼樹和哈夫曼編碼。 層次結(jié)構(gòu)的數(shù)據(jù)在現(xiàn)實(shí)自然界中大量存在。層次結(jié)構(gòu)的數(shù)據(jù)在現(xiàn)實(shí)自然界中大量存在。國家、省、市、縣和區(qū)。國家、省、市、縣和區(qū)。書的章節(jié)、回目。書的章節(jié)、回目。上級(jí)和下級(jí)。上級(jí)和下級(jí)。整體和部分。

3、整體和部分。祖先和后裔。祖先和后裔。5.1 5.1 樹樹的基本概念的基本概念5.1.1 5.1.1 樹的定義樹的定義第第5 5章章 樹樹5.1 5.1 樹的基本概念樹的基本概念5.2 5.2 二叉樹二叉樹5.3 5.3 二叉樹的遍歷二叉樹的遍歷5.5 5.5 樹和森林樹和森林5.7 5.7 哈夫曼樹和哈哈夫曼樹和哈 夫曼編碼夫曼編碼圖圖5-1 5-1 西歐語言譜系圖西歐語言譜系圖原始印歐語原始印歐語古意大利語古意大利語日耳曼語日耳曼語西日耳曼語西日耳曼語拉丁語拉丁語西西班班牙牙語語法法語語意意大大利利語語希臘語希臘語北日耳曼語北日耳曼語冰冰島島語語瑞瑞典典語語挪挪威威語語英英語語荷荷蘭蘭語語德

4、德語語古希臘語古希臘語樹樹形形結(jié)結(jié)構(gòu)構(gòu)操作系統(tǒng)的目錄結(jié)構(gòu)操作系統(tǒng)的目錄結(jié)構(gòu)1. 1. 樹的定義樹的定義定義定義5.15.1 有根數(shù)或樹的定義有根數(shù)或樹的定義 樹是包括樹是包括n n（n n 1 1）個(gè)元素的有限）個(gè)元素的有限非空非空集合集合D D，R R是是D D中元中元素的序偶的集合，素的序偶的集合，R R滿足以下特性：滿足以下特性： （1 1）有且僅有一個(gè)結(jié)點(diǎn)）有且僅有一個(gè)結(jié)點(diǎn)rDrD，不存在任何結(jié)點(diǎn)，不存在任何結(jié)點(diǎn)vDvD，vrvr，使得，使得RR，稱，稱r r為樹的根。為樹的根。 （2 2）除根）除根r r以外的所有結(jié)點(diǎn)以外的所有結(jié)點(diǎn)uDuD，都有且僅有一個(gè)結(jié)點(diǎn)，都有且僅有一個(gè)結(jié)點(diǎn)v

5、v DD， vuvu，使得，使得RR。這樣定義的樹也稱這樣定義的樹也稱有根樹有根樹，簡(jiǎn)稱，簡(jiǎn)稱樹樹。 樹不為空集合，樹中至少有一個(gè)根結(jié)點(diǎn)，根結(jié)點(diǎn)沒有前樹不為空集合，樹中至少有一個(gè)根結(jié)點(diǎn)，根結(jié)點(diǎn)沒有前驅(qū)，其余結(jié)點(diǎn)都有唯一的前驅(qū)結(jié)點(diǎn)。因此樹形成驅(qū)，其余結(jié)點(diǎn)都有唯一的前驅(qū)結(jié)點(diǎn)。因此樹形成層次層次結(jié)構(gòu)。結(jié)構(gòu)。2. 2. 樹的遞歸定義樹的遞歸定義 定義定義5.25.2 樹樹是包括是包括n n個(gè)結(jié)點(diǎn)的有限個(gè)結(jié)點(diǎn)的有限非空非空集合集合T T，其中一個(gè)特定的結(jié)點(diǎn)其中一個(gè)特定的結(jié)點(diǎn)r r稱為稱為根根，其余結(jié)點(diǎn)（，其余結(jié)點(diǎn)（T-T-rr）劃分成）劃分成m m（m0m0）個(gè)互）個(gè)互不相交不相交的的子集子集T T1

6、1，T T2 2，.T.Tm m，其中，每個(gè)子集都是樹，被稱為，其中，每個(gè)子集都是樹，被稱為樹根樹根r r的的子樹子樹。 定義定義5.25.2是遞歸的，用子樹來定義樹，也就是是遞歸的，用子樹來定義樹，也就是說，在樹的定義中引用了樹概念本身，所以，說，在樹的定義中引用了樹概念本身，所以，樹被稱為遞歸數(shù)據(jù)結(jié)構(gòu)。樹被稱為遞歸數(shù)據(jù)結(jié)構(gòu)。EAFGBCDLJMN結(jié)點(diǎn)結(jié)點(diǎn)(node)(node)：樹中的元素。：樹中的元素。 E E、A A、F F、B B、G G、C C、D D、L L、J J、M M、N N均為結(jié)點(diǎn)。均為結(jié)點(diǎn)。5.1.2 5.1.2 基本術(shù)語基本術(shù)語EAFGBCDLJMN路徑路徑(path

7、)(path)：從某個(gè)結(jié)點(diǎn)沿樹中的：從某個(gè)結(jié)點(diǎn)沿樹中的邊可到達(dá)另一個(gè)結(jié)點(diǎn)，則稱這兩個(gè)邊可到達(dá)另一個(gè)結(jié)點(diǎn)，則稱這兩個(gè)結(jié)點(diǎn)之間存在一條路徑。結(jié)點(diǎn)之間存在一條路徑。E E和和N N之間存在一條路徑。之間存在一條路徑。根結(jié)點(diǎn)和它的子樹根（如果存在）根結(jié)點(diǎn)和它的子樹根（如果存在）之間形成一條之間形成一條邊邊。路徑路徑(path)(path)：從某個(gè)結(jié)點(diǎn)沿樹中的：從某個(gè)結(jié)點(diǎn)沿樹中的邊可到達(dá)另一個(gè)結(jié)點(diǎn)，則稱這兩個(gè)邊可到達(dá)另一個(gè)結(jié)點(diǎn)，則稱這兩個(gè)結(jié)點(diǎn)之間存在一條路徑。結(jié)點(diǎn)之間存在一條路徑。E E和和N N之間存在一條路徑。之間存在一條路徑。EAFGBCDLJMN路徑路徑(path)(path)：從某個(gè)結(jié)點(diǎn)沿樹中

8、的：從某個(gè)結(jié)點(diǎn)沿樹中的邊可到達(dá)另一個(gè)結(jié)點(diǎn)，則稱這兩個(gè)邊可到達(dá)另一個(gè)結(jié)點(diǎn)，則稱這兩個(gè)結(jié)點(diǎn)之間存在一條路徑。結(jié)點(diǎn)之間存在一條路徑。E E和和N N之間存在一條路徑。之間存在一條路徑。雙親雙親(parent)(parent)：若一個(gè)結(jié)點(diǎn)有子樹，那么該結(jié)點(diǎn)稱為：若一個(gè)結(jié)點(diǎn)有子樹，那么該結(jié)點(diǎn)稱為子樹根的雙親。子樹根的雙親。A A、F F、B B的雙親是的雙親是E E。C C、D D的雙親是的雙親是F F。孩子孩子(child)(child)：某結(jié)點(diǎn)子樹的根是：某結(jié)點(diǎn)子樹的根是該結(jié)點(diǎn)的孩子。該結(jié)點(diǎn)的孩子。E E有三個(gè)孩子：有三個(gè)孩子：A A、F F、B B。D D有一個(gè)孩子：有一個(gè)孩子：J J。兄弟兄弟(

9、sibling)(sibling)：有相同雙親的結(jié)：有相同雙親的結(jié)點(diǎn)互為兄弟。點(diǎn)互為兄弟。A A、F F、B B互為兄弟，互為兄弟，C C和和D D互為兄弟?；樾值?。結(jié)點(diǎn)結(jié)點(diǎn)G和和C互為兄弟否？互為兄弟否？EAFGBCDLJMN后裔后裔(decendent)(decendent)：一個(gè)結(jié)點(diǎn)的：一個(gè)結(jié)點(diǎn)的所有子樹上的任何結(jié)點(diǎn)都是該結(jié)所有子樹上的任何結(jié)點(diǎn)都是該結(jié)點(diǎn)的后裔。點(diǎn)的后裔。結(jié)點(diǎn)結(jié)點(diǎn)C C的后裔為：的后裔為：L L、M M、N N。EAFGBCDLJMN祖先祖先(ancestor)(ancestor)：從根結(jié)點(diǎn)到：從根結(jié)點(diǎn)到某個(gè)結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)某個(gè)結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)都是該結(jié)點(diǎn)的祖

10、先。都是該結(jié)點(diǎn)的祖先。結(jié)點(diǎn)結(jié)點(diǎn)L L的祖先為：的祖先為：E E、F F、C C。結(jié)點(diǎn)的度結(jié)點(diǎn)的度(degree)(degree)：結(jié)點(diǎn)擁有的子樹數(shù)。：結(jié)點(diǎn)擁有的子樹數(shù)。結(jié)點(diǎn)結(jié)點(diǎn)E E的度為的度為3 3，結(jié)點(diǎn)，結(jié)點(diǎn)F F的度為的度為2 2，結(jié)點(diǎn)結(jié)點(diǎn)A A的度為的度為1 1，結(jié)點(diǎn)，結(jié)點(diǎn)G G的度為的度為0 0。葉子葉子(leaf)(leaf)：度為零的結(jié)點(diǎn)。：度為零的結(jié)點(diǎn)。B B、G G、J J、M M、N N均為葉子結(jié)點(diǎn)。均為葉子結(jié)點(diǎn)。EAFGBCDLJMN分支結(jié)點(diǎn)分支結(jié)點(diǎn)(branch)(branch)：度不為零的結(jié)點(diǎn)。：度不為零的結(jié)點(diǎn)。E E、A A、F F、C C等為分支結(jié)點(diǎn)。等為分支結(jié)點(diǎn)

11、。樹的度樹的度：樹中結(jié)點(diǎn)的最大的度。：樹中結(jié)點(diǎn)的最大的度。該樹的度為該樹的度為3 3。結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次：根結(jié)點(diǎn)的層次為：根結(jié)點(diǎn)的層次為1 1，其余結(jié)點(diǎn)的層次等于其，其余結(jié)點(diǎn)的層次等于其雙親結(jié)點(diǎn)的層次加雙親結(jié)點(diǎn)的層次加1 1。結(jié)點(diǎn)結(jié)點(diǎn)E E的層次為的層次為1 1。結(jié)點(diǎn)結(jié)點(diǎn)M M的層次為的層次為5 5。樹的高度樹的高度：樹中結(jié)點(diǎn)的：樹中結(jié)點(diǎn)的最大層次。最大層次。樹中結(jié)點(diǎn)的最大樹中結(jié)點(diǎn)的最大層次為層次為5 5。樹的高度為樹的高度為5 5。12345EAFGBCDLJMNAG無序樹無序樹：如果樹中結(jié)點(diǎn)的各子樹之間的次序是不重要的，：如果樹中結(jié)點(diǎn)的各子樹之間的次序是不重要的，可以交換位置?？梢越粨Q位

12、置。下列是下列是同一棵同一棵無序樹：無序樹：將左邊樹中所有結(jié)點(diǎn)的子樹互換次序就是右邊的樹。將左邊樹中所有結(jié)點(diǎn)的子樹互換次序就是右邊的樹。EAFGBCDLJMNEFBCDLJNM有序樹有序樹：如果樹中結(jié)點(diǎn)的各棵子樹看成是從左到右有次序：如果樹中結(jié)點(diǎn)的各棵子樹看成是從左到右有次序的，則稱該樹為有序樹。的，則稱該樹為有序樹。有序樹的各子樹從左到右為第一棵子樹、第二棵，有序樹的各子樹從左到右為第一棵子樹、第二棵，如果下列是有序樹，則二者是如果下列是有序樹，則二者是二棵不同的樹二棵不同的樹AGEAFGBCDLJMNEFBCDLJNM森林森林：是樹的集合。：是樹的集合。0 0個(gè)或多個(gè)不相交的樹組成森林。個(gè)

13、或多個(gè)不相交的樹組成森林。果園或有序森林果園或有序森林：有序樹的有序集合。：有序樹的有序集合。 森林與樹只有很小的差別，若將樹中的根去掉，森林與樹只有很小的差別，若將樹中的根去掉，則得到根的子樹組成的森林。則得到根的子樹組成的森林。 BEAGFCDLJMNE 若增加一個(gè)結(jié)點(diǎn)，將森林中各樹的根作為新增結(jié)點(diǎn)的若增加一個(gè)結(jié)點(diǎn)，將森林中各樹的根作為新增結(jié)點(diǎn)的孩子，則森林即成為樹。孩子，則森林即成為樹。 遞歸遞歸1.1.遞歸的定義遞歸的定義函數(shù)直接（間接）調(diào)用自已，稱為函數(shù)的遞歸調(diào)用。函數(shù)直接（間接）調(diào)用自已，稱為函數(shù)的遞歸調(diào)用。2.2.簡(jiǎn)單實(shí)例簡(jiǎn)單實(shí)例以下是一個(gè)最簡(jiǎn)單的遞歸函數(shù)以下是一個(gè)最簡(jiǎn)單的遞歸函

14、數(shù) 。void func()void func() func(); func(); 修改為：修改為：void func(int n)void func(int n) if (n=0) return ; if (n=0) return ; func(n-); func(n-); 3.3.遞推關(guān)系遞推關(guān)系可以把要解決的問題轉(zhuǎn)化為一個(gè)新問題，而這可以把要解決的問題轉(zhuǎn)化為一個(gè)新問題，而這個(gè)新的問題的解決方法仍與原來的個(gè)新的問題的解決方法仍與原來的解決方法相解決方法相同同，只是所處理對(duì)象的，只是所處理對(duì)象的規(guī)模規(guī)模有規(guī)律地遞增或遞有規(guī)律地遞增或遞減，即要找到對(duì)象之間的減，即要找到對(duì)象之間的遞推關(guān)系遞推關(guān)

15、系。 方法相同，規(guī)模變化方法相同，規(guī)模變化4.4.遞歸的結(jié)束條件遞歸的結(jié)束條件要有一個(gè)明確的要有一個(gè)明確的結(jié)束遞歸結(jié)束遞歸的條件，一定要能夠的條件，一定要能夠在適當(dāng)?shù)牡胤皆谶m當(dāng)?shù)牡胤浇Y(jié)束遞歸調(diào)用結(jié)束遞歸調(diào)用，不然可能導(dǎo)致系，不然可能導(dǎo)致系統(tǒng)崩潰統(tǒng)崩潰int func(int n)if (n=1) return 1;return func(n-1)*n;例如：采用例如：采用遞歸計(jì)算遞歸計(jì)算N！正整數(shù)正整數(shù)N！N*(N-1)*(N-2)*2*1， 階乘序列可轉(zhuǎn)換為階乘序列可轉(zhuǎn)換為 N！N*(N-1)!，而而(N-1)!以可轉(zhuǎn)換為以可轉(zhuǎn)換為(N-1)!=(N-1)*(N-2)! (N-2)!=(N-

16、2)*(N-3)! ， 2!=2*1! 1!=1 遞推關(guān)系：遞推關(guān)系： N！N*(N-1)! 結(jié)束條件：結(jié)束條件：N等于等于1int func(int n)if (n=1) return 1;return func(n-1)*n;n=3 if(n=1) .func(n-1)*nn=2if(n=1) .func(n-1)*nn=1if(n=1)return 11func(n-1)func(n-1)n=2n=12執(zhí)行過程：執(zhí)行過程：設(shè)計(jì)遞歸算法，求有設(shè)計(jì)遞歸算法，求有n個(gè)元素的整數(shù)數(shù)組個(gè)元素的整數(shù)數(shù)組A中的最大值。中的最大值。 a a0 0 a a1 1 a ai i a an-2 n-2 a a

17、n-1n-10 1 0 1 i i n-2 n-1 n-2 n-1 a(n-1)Max(n)Max(n-1) a a0 0 a a1 1 a ai i a an-3 n-3 a an-2 n-2 a an-1n-10 1 0 1 i i n-2 n-1 n-2 n-1 a(n-2)Max(n-1)Max(n-2)設(shè)計(jì)遞歸算法，求整數(shù)數(shù)組設(shè)計(jì)遞歸算法，求整數(shù)數(shù)組An中的最大值。中的最大值。 a a0 0 a a1 1 a ai i a an-3 n-3 a an-2 n-2 a an-1n-10 1 0 1 i i n-2 n-1 n-2 n-1 a(1)Max(2)Max(1)遞推關(guān)系：遞推關(guān)

18、系：max(n)等于等于max(n-1)與與an-1之間的大者之間的大者結(jié)束條件：結(jié)束條件：n等于等于1時(shí)，時(shí)，Max(1)的值即為的值即為a0，所以不再向下遞推，所以不再向下遞推int Max (int a,int n) int temp;if (n=1) return a0; else temp=Max (a,n-1); if (tempan-1) return an-1; else return temp; 遞推關(guān)系：遞推關(guān)系：max(n)等于等于max(n-1)與與an-1之間的大者之間的大者結(jié)束條件：結(jié)束條件：n等于等于1時(shí)，時(shí)，Max(1)的值即為的值即為a0，所以不再向下遞推，所

19、以不再向下遞推int Max (int a,int n) int temp;if (n=1) return a0; else temp=Max (a,n-1); if (tempan-1) return an-1; else return temp; 8 8 9 10 10 0 1 2 0 1 2 n=3 if(n=1) .Max(a,2)a2n=2if(n=1) .Max(a,1)0h0時(shí)，利用時(shí)，利用性質(zhì)性質(zhì)1 1，高度為，高度為h h的二叉樹中結(jié)點(diǎn)的總數(shù)最多為：的二叉樹中結(jié)點(diǎn)的總數(shù)最多為：1012112(222.2)21hihhi12311.1nnaaaaaa補(bǔ)充：等比數(shù)列的求和公式是1

20、 (1)21ii i 性質(zhì) 二叉樹的第層上至多有個(gè)結(jié)點(diǎn)。性質(zhì)性質(zhì)1 1、2 2的圖形解釋的圖形解釋性質(zhì)性質(zhì)5.35.3 包含包含n n個(gè)元素的二叉樹的高度個(gè)元素的二叉樹的高度至少至少為為 loglog2 2 (n+1)(n+1) 根據(jù)根據(jù)性質(zhì)性質(zhì)2 2，高度為，高度為h h的二叉樹最多有的二叉樹最多有2 2h h 1 1個(gè)結(jié)點(diǎn)（性質(zhì)個(gè)結(jié)點(diǎn)（性質(zhì)2 2），因而），因而n n 2 2h h 1, 1, 則有則有h h loglog2 2(n+1)(n+1)。 由于由于h h是整數(shù)，所以是整數(shù)，所以h h loglog2 2 (n+1)(n+1) 。性質(zhì)性質(zhì)5.45.4 任意一棵二叉樹中，若葉結(jié)點(diǎn)的

21、個(gè)數(shù)為任意一棵二叉樹中，若葉結(jié)點(diǎn)的個(gè)數(shù)為n n0 0，度為，度為2 2的結(jié)點(diǎn)的個(gè)數(shù)為的結(jié)點(diǎn)的個(gè)數(shù)為n n2 2，則必有，則必有n n0 0=n=n2 2+1+1。設(shè)二叉樹的度為設(shè)二叉樹的度為1 1的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n n1 1，樹中結(jié)點(diǎn)總數(shù)為，樹中結(jié)點(diǎn)總數(shù)為n n，則，則n=nn=n0 0+n+n1 1+n+n2 2 （二叉樹中只有度為二叉樹中只有度為0 0、1 1、2 2三種類型的結(jié)點(diǎn)）三種類型的結(jié)點(diǎn)）設(shè)分支數(shù)為設(shè)分支數(shù)為B B，n n個(gè)結(jié)點(diǎn)的二叉樹，除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)的二叉樹，除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有一個(gè)分支進(jìn)入，則都有一個(gè)分支進(jìn)入，則B=n-1B=n-1；分支是由度為；分支

22、是由度為1 1或者度為或者度為2 2的的射出的，又有射出的，又有B=2nB=2n2 2+n+n1 1；則有：則有：n-1=2nn-1=2n2 2+n+n1 1 n=2nn=2n2 2+n+n1 1+1+1由由 可得到：可得到：n n0 0+n+n1 1+n+n2 2=2n=2n2 2+n+n1 1+1 +1 n n0 0+n+n2 2=2n=2n2 2 +1 +1即即n n2 2=n=n0 0-1-1。定義定義5.45.4 高度為高度為h h的二叉樹恰好有的二叉樹恰好有2 2h h 1 1個(gè)結(jié)點(diǎn)時(shí)稱為個(gè)結(jié)點(diǎn)時(shí)稱為滿二叉樹滿二叉樹。0123456789101112 1314(a)滿二叉樹滿二叉樹

23、圖圖5.6 幾種特殊的二叉樹幾種特殊的二叉樹性質(zhì)性質(zhì)5.2 高度為高度為h的二叉樹上的二叉樹上至多至多有有2h1個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。0123456789(b)完全二叉樹完全二叉樹圖圖5.6 幾種特殊的二叉樹幾種特殊的二叉樹9定義定義5.5 一棵二叉樹中，只有一棵二叉樹中，只有最下面兩層結(jié)點(diǎn)最下面兩層結(jié)點(diǎn)的度可以小的度可以小于于2，并且最下一層的，并且最下一層的葉結(jié)點(diǎn)葉結(jié)點(diǎn)集中在集中在靠左靠左的若干位置上。的若干位置上。這樣的二叉樹稱為這樣的二叉樹稱為完全二叉樹完全二叉樹。定義定義5.65.6 擴(kuò)充二叉樹也稱擴(kuò)充二叉樹也稱2-2-樹，其中除樹，其中除葉子葉子結(jié)點(diǎn)外，其余結(jié)點(diǎn)都必須有兩個(gè)孩子。結(jié)點(diǎn)外，

24、其余結(jié)點(diǎn)都必須有兩個(gè)孩子。532330111213173589完全二叉樹的性質(zhì)完全二叉樹的性質(zhì)性質(zhì)性質(zhì)5.55.5 具有具有n n個(gè)結(jié)點(diǎn)的完全二叉樹的高度為個(gè)結(jié)點(diǎn)的完全二叉樹的高度為 loglog2 2 (n+1)(n+1) 。證明：根據(jù)性質(zhì)證明：根據(jù)性質(zhì)2 2高度為高度為h-1h-1的完全二叉樹結(jié)點(diǎn)個(gè)數(shù)最多為的完全二叉樹結(jié)點(diǎn)個(gè)數(shù)最多為2 2h-1h-1-1-1高度為高度為h h的完全二叉樹結(jié)點(diǎn)個(gè)數(shù)最多為的完全二叉樹結(jié)點(diǎn)個(gè)數(shù)最多為2 2h h-1-1高度為高度為h h的完全二叉樹結(jié)點(diǎn)個(gè)數(shù)取值范圍的完全二叉樹結(jié)點(diǎn)個(gè)數(shù)取值范圍22h-1 h-1 , 2, 2h h) )2 2h-1 h-1 - 1

25、- 1 n 2n 2h h 1 1loglog2 2(n+1) h(n+1) hloglog2 2(n+1)+1(n+1)+1h = h = loglog2 2 (n+1)(n+1) 結(jié)論：結(jié)論： n n個(gè)結(jié)點(diǎn)的二叉樹中完全二叉樹最矮，高度為個(gè)結(jié)點(diǎn)的二叉樹中完全二叉樹最矮，高度為 loglog2 2 (n+1) (n+1) 。 n n個(gè)結(jié)點(diǎn)的完全二叉樹和二叉判定樹的高度是一樣的個(gè)結(jié)點(diǎn)的完全二叉樹和二叉判定樹的高度是一樣的2log1n2 2h-1h-1nn2 2h hh-1logh-1log2 2n nh hhh是整數(shù)是整數(shù) h=h=2log1n性質(zhì)性質(zhì)2 2 高度為高度為h h的二叉樹上至多有

26、的二叉樹上至多有2 2h h 1 1個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。性質(zhì)性質(zhì)5.65.6 假定對(duì)一棵有假定對(duì)一棵有n n個(gè)結(jié)點(diǎn)的完全二叉樹中的結(jié)點(diǎn)，按從上個(gè)結(jié)點(diǎn)的完全二叉樹中的結(jié)點(diǎn)，按從上到下、從左到右的順序，從到下、從左到右的順序，從0 0到到n-1n-1編號(hào)（見圖編號(hào)（見圖5.6(c)5.6(c)），設(shè)樹中），設(shè)樹中一個(gè)結(jié)點(diǎn)的序號(hào)為一個(gè)結(jié)點(diǎn)的序號(hào)為i i，0 0 i i n n ，則有以下關(guān)系成立：，則有以下關(guān)系成立：（1 1）當(dāng)）當(dāng)i=0i=0時(shí)，該結(jié)點(diǎn)為二叉樹的根。時(shí)，該結(jié)點(diǎn)為二叉樹的根。（2 2）若）若i0i0，則該結(jié)點(diǎn)的雙親的序號(hào)為，則該結(jié)點(diǎn)的雙親的序號(hào)為 ( (i-1)/2i-1)/2 （3 3

27、）若）若2i+12i+1n n，則該結(jié)點(diǎn)的左孩子的序號(hào)為，則該結(jié)點(diǎn)的左孩子的序號(hào)為2i+12i+1，否則該結(jié)點(diǎn)，否則該結(jié)點(diǎn)無左孩子。無左孩子。（4 4）若）若2i+22i+2n n，則該結(jié)點(diǎn)的右孩子的序號(hào)為，則該結(jié)點(diǎn)的右孩子的序號(hào)為2i+22i+2，否則該結(jié)點(diǎn)，否則該結(jié)點(diǎn)無右孩子。無右孩子。0123456789(b)(b)完全二叉樹完全二叉樹ADT ADT BinaryTreeBinaryTree Data:Data: 二叉樹是結(jié)點(diǎn)的有限集合，該集合或者為空集，或者是由一個(gè)根二叉樹是結(jié)點(diǎn)的有限集合，該集合或者為空集，或者是由一個(gè)根和兩個(gè)互不相交的稱為該根的左子樹和右子樹的二叉樹組成。和兩個(gè)互不

28、相交的稱為該根的左子樹和右子樹的二叉樹組成。 Operations:Operations: Create() Create()： 創(chuàng)建一棵空二叉樹。創(chuàng)建一棵空二叉樹。 Destroy(): Destroy(): 撤銷一棵二叉樹。撤銷一棵二叉樹。 IsEmpty()IsEmpty()：若二叉樹空，則返回：若二叉樹空，則返回truetrue，否則返回，否則返回falsefalse。 Clear(): Clear(): 移去所有結(jié)點(diǎn)，成為空二叉樹。移去所有結(jié)點(diǎn)，成為空二叉樹。 Root(x)Root(x)：?。喝 x為根結(jié)點(diǎn)；若操作成功，則返回為根結(jié)點(diǎn)；若操作成功，則返回truetrue，否則返回

29、，否則返回falsefalse MakeTree(x,left MakeTree(x,left，right)right)：創(chuàng)建一棵二叉樹，：創(chuàng)建一棵二叉樹，x x為根結(jié)點(diǎn)，為根結(jié)點(diǎn)，leftleft為為 左子樹，左子樹，rightright為右子樹。為右子樹。 BreakTree(x ,left, right)BreakTree(x ,left, right)：拆分二叉樹為三部分，：拆分二叉樹為三部分，x x為根的值，為根的值， leftleft和和rightright分別為原樹的左右子樹分別為原樹的左右子樹 PreOrderPreOrder： 使用函數(shù)使用函數(shù)VisitVisit訪問結(jié)點(diǎn)，先

30、序遍歷二叉樹。訪問結(jié)點(diǎn)，先序遍歷二叉樹。 InOrderInOrder： 使用函數(shù)使用函數(shù)VisitVisit訪問結(jié)點(diǎn)，中序遍歷二叉樹。訪問結(jié)點(diǎn)，中序遍歷二叉樹。 PostOrderPostOrder：使用函數(shù)：使用函數(shù)VisitVisit訪問結(jié)點(diǎn)，后序遍歷二叉樹。訪問結(jié)點(diǎn)，后序遍歷二叉樹。 5.2.3 5.2.3 二叉樹二叉樹ADTADT1. 1. 完全二叉樹的順序表示完全二叉樹的順序表示 完全二叉樹中的結(jié)點(diǎn)可以按層次順序存儲(chǔ)在一片連完全二叉樹中的結(jié)點(diǎn)可以按層次順序存儲(chǔ)在一片連續(xù)的存儲(chǔ)單元中。根結(jié)點(diǎn)保存在編號(hào)為續(xù)的存儲(chǔ)單元中。根結(jié)點(diǎn)保存在編號(hào)為0 0的位置上。的位置上。注意：一般的二叉樹不適

31、合用這種存儲(chǔ)結(jié)構(gòu)。注意：一般的二叉樹不適合用這種存儲(chǔ)結(jié)構(gòu)。0 01 12 23 34 45 56 67 78 89 90 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 9圖圖6.5 6.5 圖圖6.4(b)6.4(b)完全二叉樹的順序表示完全二叉樹的順序表示0123456789圖圖6.4(b) 6.4(b) 完全二叉樹完全二叉樹5.2.4 5.2.4 二叉樹的存儲(chǔ)表示二叉樹的存儲(chǔ)表示elementelement2. 2. 二叉樹的鏈接表示二叉樹的鏈接表示ABCDEFA AB B C C D D E E F F (a)(a)二叉樹二叉樹(b)(b)二叉樹的鏈接表示二叉樹的

32、鏈接表示圖圖6-6 6-6 二叉樹的鏈接表示二叉樹的鏈接表示lChildrChild二叉樹的二叉鏈表結(jié)構(gòu)有利于從二叉樹的二叉鏈表結(jié)構(gòu)有利于從雙親到孩子雙親到孩子方向的訪問。采方向的訪問。采取從取從根根開始，遍歷整個(gè)二叉樹。開始，遍歷整個(gè)二叉樹。root 如果應(yīng)用程序需要經(jīng)常執(zhí)行從如果應(yīng)用程序需要經(jīng)常執(zhí)行從孩子到雙親孩子到雙親訪問，訪問，可在二叉鏈表結(jié)點(diǎn)中增加一個(gè)可在二叉鏈表結(jié)點(diǎn)中增加一個(gè)parentparent域，令它指域，令它指向該結(jié)點(diǎn)的雙親結(jié)點(diǎn)。這就實(shí)現(xiàn)了從孩子到雙親，向該結(jié)點(diǎn)的雙親結(jié)點(diǎn)。這就實(shí)現(xiàn)了從孩子到雙親，以及從雙親到孩子的雙向鏈接結(jié)構(gòu)，形成以及從雙親到孩子的雙向鏈接結(jié)構(gòu)，形成多重鏈

33、多重鏈表表。templatetemplatestruct struct BTNode /BTNode /樹結(jié)點(diǎn)樹結(jié)點(diǎn) BTNode() lChild = rChild = NULL; BTNode() lChild = rChild = NULL; BTNode(const T& x) BTNode(const T& x) element =x; element =x; lChild = rChild = NULL; lChild = rChild = NULL; BTNode(const T& x, BTNode BTNode(const T& x, BTNo

34、de* * l, BTNode l, BTNode* * r) r) element = x; element = x; lChild = l; lChild = l; rChild = r; rChild = r; T T elementelement; ; BTNode BTNode* * lChildlChild, , * *rChildrChild; ;5.2.5 5.2.5 二叉樹類二叉樹類templatetemplateclass class BinaryTreeBinaryTree public:public: BinaryTree()root = NULL; BinaryTre

35、e()root = NULL; BinaryTree()Clear();BinaryTree()Clear(); bool IsEmpty()const; bool IsEmpty()const; void Clear(); void Clear(); bool Root(T& x)const; bool Root(T& x)const; void MakeTree(const T& e,BinaryTree& left,BinaryTree& right); void MakeTree(const T& e,BinaryTree& le

36、ft,BinaryTree& right); void BreakTree(T& e,BinaryTree& left,BinaryTree& right); void BreakTree(T& e,BinaryTree& left,BinaryTree& right); void void PreOrderPreOrder(void(void(* *Visit)(T& x); /Visit)(T& x); /公有函數(shù)，用戶接口公有函數(shù)，用戶接口 void InOrder(void(void InOrder(void(*

37、*Visit)(T& x);Visit)(T& x); void PostOrder(void( void PostOrder(void(* *Visit)(T& x);Visit)(T& x); protected:protected: BTNode BTNode* * ; ; /指向根結(jié)點(diǎn)指向根結(jié)點(diǎn) private:private: int Size(BTNode int Size(BTNode* * t); t); void Clear(BTNode void Clear(BTNode* * t); t); void void PreOrder(PreOr

38、der(void(void(* *Visit)(T& x),BTNodeVisit)(T& x),BTNode* * t);/ t);/私有函數(shù)，實(shí)現(xiàn)遍歷私有函數(shù)，實(shí)現(xiàn)遍歷 void InOrder(void(void InOrder(void(* *Visit)(T& x), BTNodeVisit)(T& x), BTNode* * t); t); void PostOrder(void( void PostOrder(void(* *Visit)(T& x), BTNodeVisit)(T& x), BTNode* * t); t);程序程

39、序5.2 5.2 二叉樹類二叉樹類root 本小節(jié)中，我們主要實(shí)現(xiàn)本小節(jié)中，我們主要實(shí)現(xiàn)MakeTreeMakeTree、BreakTreeBreakTree和和RootRoot運(yùn)算，而將二叉樹遍歷算法留待下一小節(jié)專門討論。運(yùn)算，而將二叉樹遍歷算法留待下一小節(jié)專門討論。 Clear()Clear()函數(shù)釋放二叉鏈表中的所有結(jié)點(diǎn)，它需要通過函數(shù)釋放二叉鏈表中的所有結(jié)點(diǎn)，它需要通過遍歷二叉樹來實(shí)現(xiàn)。遍歷二叉樹來實(shí)現(xiàn)。5.2.6 5.2.6 實(shí)現(xiàn)二叉樹基本運(yùn)算實(shí)現(xiàn)二叉樹基本運(yùn)算程序程序5.3 5.3 部分二叉樹運(yùn)算部分二叉樹運(yùn)算templatetemplatebool BinaryTree:Root

40、(T& x)constbool BinaryTree:Root(T& x)const/取根結(jié)點(diǎn)的數(shù)據(jù)值取根結(jié)點(diǎn)的數(shù)據(jù)值 if(root) if(root) x = root-element; x = root-element; return true; return true; else return false; else return false; ABCDEFroottemplatevoid BinaryTree:MakeTree(const T& x, BinaryTree& left,BinaryTree& right) if(root|&am

41、p;left=&right) return; root = new BTNode(x, left.root, right.root); left.root = right.root = NULL; D DC CE EF FBTNode(const T& x, BTNode* l,BTNode* r) element = x; lChild = l; rChild = r; X Xleftleftrightrightnew BTNode(x, left.root, right.root);函數(shù)功能：函數(shù)功能：以以x為根，為根，left,right為左右子樹構(gòu)建一棵新二叉樹為左右子

42、樹構(gòu)建一棵新二叉樹templatetemplatevoid BinaryTree:BreakTree(T& x, void BinaryTree:BreakTree(T& x, BinaryTree&left,BinaryTree&right) BinaryTree&left,BinaryTree&right) if(!root|&left=&root|left.root|right.root) if(!root|&left=&root|left.root|right.root) return; return; x

43、 = root-element; x = root-element; left.root = root-lChild; left.root = root-lChild; right.root = root-rChild; right.root = root-rChild; delete root; delete root; root = NULL; root = NULL; D DC CE EF FA Aleft.rootleft.rootright.rootright.rootroot=root=root函數(shù)功能：將二叉樹左右子樹拆分成二棵新的二叉樹，根結(jié)點(diǎn)刪除函數(shù)功能：將二叉樹左右子樹拆分

44、成二棵新的二叉樹，根結(jié)點(diǎn)刪除int main(void) BinaryTreea, b, x, y, z; char e; y.MakeTree(E, a, b); z.MakeTree(F, a, b); x.MakeTree(C, y, z); y.MakeTree(D, a, b); z.MakeTree(B, y, x); z.BreakTree(e, y, x); return 0;程序程序5.4 5.4 mainmain函數(shù)函數(shù)一個(gè)測(cè)試程序一個(gè)測(cè)試程序a b x y zEyCxFzDyBzA AB BD DC CE EF F5.3 5.3 二叉樹的遍歷二叉樹的遍歷遍歷遍歷（trav

45、ersetraverse）一個(gè)有限結(jié)點(diǎn)的集合，意味著對(duì)該集）一個(gè)有限結(jié)點(diǎn)的集合，意味著對(duì)該集合中的每個(gè)結(jié)點(diǎn)訪問且僅訪問一次。合中的每個(gè)結(jié)點(diǎn)訪問且僅訪問一次。二叉樹遍歷算法二叉樹遍歷算法: : (I) (I) 先左后右：先左后右：VLRVLR，LVRLVR，LRVLRV(II)(II)先右后左：先右后左：VRLVRL，RVLRVL，RLV-RLV-逆逆第第5 5章章 樹樹5.1 5.1 樹的基本概念樹的基本概念5.2 5.2 二叉樹二叉樹5.3 5.3 二叉樹的遍歷二叉樹的遍歷5.5 5.5 樹和森林樹和森林5.7 5.7 哈夫曼樹和哈哈夫曼樹和哈 夫曼編碼夫曼編碼 先序遍歷（先序遍歷（VLRV

46、LR）若二叉樹為空，則空操作；若二叉樹為空，則空操作；否則否則 訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； 先序遍歷先序遍歷左子樹；左子樹； 先序遍歷先序遍歷右子樹。右子樹。A AB BD DC CE EF F5.3.1 5.3.1 二叉樹遍歷算法二叉樹遍歷算法先序遍歷先序遍歷序列：序列： A B D C E FA B D C E F 先序遍歷先序遍歷序列：序列： A B D G H E C FA B D G H E C F ttttttt= t= t=t=ttt=t=t=A AB BC CD DE EF FG GH H任意一個(gè)先序遍歷任意一個(gè)先序遍歷序列中，根結(jié)點(diǎn)的位置在哪里？序列中，根結(jié)點(diǎn)的位置在哪里？若二

47、叉樹為空，則空操作；若二叉樹為空，則空操作；否則否則 訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； 先序遍歷先序遍歷左子樹；左子樹； 先序遍歷先序遍歷右子樹。右子樹。 中序遍歷（中序遍歷（LVRLVR）若二叉樹為空，則空操作；若二叉樹為空，則空操作；否則否則 中序遍歷左子樹；中序遍歷左子樹； 訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； 中序遍歷右子樹。中序遍歷右子樹。 A AB BD DC CE EF F中序遍歷中序遍歷序列：序列：B D A E C F B D A E C F 中序遍歷中序遍歷A AB BC CD DE EF FG GH HI IJ JK K 后序遍歷后序遍歷 （LRVLRV） 若二叉樹為空，則空操作；若二叉樹為

48、空，則空操作； 否則否則 后序遍歷左子樹；后序遍歷左子樹； 后序遍歷右子樹；后序遍歷右子樹； 訪問根結(jié)點(diǎn)。訪問根結(jié)點(diǎn)。A AB BD DC CE EF F后序遍歷后序遍歷序列：序列：D B E F C A D B E F C A 后序遍歷后序遍歷A AB BC CD DE EF FG GH HI IJ JK K層次遍歷層次遍歷A AB BC CD DE EF FG GH HI IJ JK K 對(duì)于遍歷運(yùn)算，設(shè)計(jì)了一個(gè)面向用戶的對(duì)于遍歷運(yùn)算，設(shè)計(jì)了一個(gè)面向用戶的公有公有成員成員函數(shù)和一個(gè)具體實(shí)現(xiàn)遍歷操作的遞歸函數(shù)和一個(gè)具體實(shí)現(xiàn)遍歷操作的遞歸私有私有成員函數(shù)，成員函數(shù)，兩者共同完成遍歷運(yùn)算的功能。

49、兩者共同完成遍歷運(yùn)算的功能。 公有成員函數(shù)：非遞歸函數(shù)，作為與用戶的接公有成員函數(shù)：非遞歸函數(shù)，作為與用戶的接 口。它調(diào)用私有的遞歸函數(shù)?？凇Ｋ{(diào)用私有的遞歸函數(shù)。 私有成員函數(shù)：遞歸函數(shù)，具體實(shí)現(xiàn)遍歷操作。私有成員函數(shù)：遞歸函數(shù)，具體實(shí)現(xiàn)遍歷操作。 被公有成員函數(shù)調(diào)用。被公有成員函數(shù)調(diào)用。5.3.2 5.3.2 二叉樹遍歷的遞歸算法二叉樹遍歷的遞歸算法函數(shù)指針格式函數(shù)指針格式：函數(shù)返回類型：函數(shù)返回類型 ( (* *函數(shù)指針名函數(shù)指針名)()(參數(shù)參數(shù)1 1，參數(shù)，參數(shù)2 2) ) #include #include int max(int x,int y)return x y ? x :

50、y;int max(int x,int y)return x y ? x : y;int min(int x,int y)return x y ? x : y;int min(int x,int y)return x y ? x : y;int add(int x,int y)return x + y;int add(int x,int y)return x + y;void process(int x,int y, void process(int x,int y, int (int (* *fun) (int,int)fun) (int,int) int result; int resul

51、t; result = fun(x,y); result = fun(x,y); cout result endl; cout result endl; int main(void)int main(void) int x=1,y=2; int x=1,y=2; process(1,2,min); process(1,2,min); process(1,2,max); process(1,2,max); process(1,2,add); process(1,2,add); return 0; return 0; 程序運(yùn)行結(jié)果：程序運(yùn)行結(jié)果：1 12 23 3指向函數(shù)的指向函數(shù)的指針指針保存一

52、個(gè)函數(shù)的入口地址。保存一個(gè)函數(shù)的入口地址。函數(shù)返回類型函數(shù)返回類型 ( (* *函數(shù)指針名函數(shù)指針名)()(參數(shù)參數(shù)1, 1, 參數(shù)參數(shù)2)2) int ( int (* *fun)(int, int)fun)(int, int)程序程序5.5 5.5 訪問元素函數(shù)訪問元素函數(shù)templatetemplatevoid Visit(T& x) cout x t;void Visit(T& x) cout x t;程序程序5.6 5.6 先序遍歷先序遍歷templatetemplatevoid BinaryTree:void BinaryTree:PreOrderPreOrder(

53、void(void(* *Visit)(T& x)Visit)(T& x)/非遞歸函數(shù)，作為與用戶的接口，調(diào)用遞歸函數(shù)非遞歸函數(shù)，作為與用戶的接口，調(diào)用遞歸函數(shù) PreOrder(Visit,root); PreOrder(Visit,root);templatetemplatevoid BinaryTree:void BinaryTree:PreOrderPreOrder(void(void(* *Visit)(T& x), BTNodeVisit)(T& x), BTNode* * t) t) if(t) if(t) /遞歸函數(shù)，實(shí)現(xiàn)遍歷遞歸函數(shù)，實(shí)現(xiàn)遍歷

54、Visit(t-element); Visit(t-element); PreOrder(Visit, t-lChild); PreOrder(Visit, t-lChild); PreOrder(Visit, t-rChild); PreOrder(Visit, t-rChild); 注：注：1.1.函數(shù)名相同，但參數(shù)不同，不是同一個(gè)函數(shù)。函數(shù)名相同，但參數(shù)不同，不是同一個(gè)函數(shù)。 2.2.使用函數(shù)指針使用函數(shù)指針(*Visit)(T& x)，只是為了增加程序的靈活性，只是為了增加程序的靈活性 templatevoid BinaryTree:PreOrder( BTNode* t) i

55、f(t) coutelement ; PreOrder( t-lChild); PreOrder( t-rChild); templatetemplatevoid BinaryTree:PreOrder(void(void BinaryTree:PreOrder(void(* *VisitVisit)(T& x), BTNode)(T& x), BTNode* * t) t) if(t) / if(t) /遞歸函數(shù)，實(shí)現(xiàn)遍歷遞歸函數(shù)，實(shí)現(xiàn)遍歷 VisitVisit(t-element);(t-element); PreOrder( PreOrder(VisitVisit, t-

56、lChild);, t-lChild); PreOrder( PreOrder(VisitVisit, t-rChild);, t-rChild); 除去函數(shù)指針，以上遞歸的除去函數(shù)指針，以上遞歸的PreOrder函數(shù)可以簡(jiǎn)化為：函數(shù)可以簡(jiǎn)化為：C CE EF Ft-cif(t) coutlChild);PreOrder( t-rChild); t-Eif(t) coutlChild);PreOrder( t-rChild); t-if(t) coutPreOrder( t-lChild);PreOrder( t-rChild); t-if(t) coutPreOrder( t-lChild)

57、;PreOrder( t-rChild); t-Fif(t) coutlChild);PreOrder( t-rChild); t-if(t) coutPreOrder( t-lChild);PreOrder( t-rChild); 補(bǔ)充：中序遍歷補(bǔ)充：中序遍歷templatetemplatevoid BinaryTree:InOrder(void(void BinaryTree:InOrder(void(* *Visit)(T& x)Visit)(T& x) InOrder(Visit,root); InOrder(Visit,root); templatetemplatev

58、oid BinaryTree:InOrder(void(void BinaryTree:InOrder(void(* *Visit)(T& x), BTNodeVisit)(T& x), BTNode* * t) t) if(t) if(t) InOrder(Visit, t-lChild); InOrder(Visit, t-lChild); Visit(t-element);Visit(t-element); InOrder(Visit, t-rChild); InOrder(Visit, t-rChild); 補(bǔ)充：后序遍歷補(bǔ)充：后序遍歷templatetemplatev

59、oid BinaryTree:PostOrder(void(void BinaryTree:PostOrder(void(* *Visit)(T& x)Visit)(T& x) PostOrder(Visit,root); PostOrder(Visit,root); templatetemplatevoid BinaryTree:PostOrder(void(void BinaryTree:PostOrder(void(* *Visit)(T& x), BTNodeVisit)(T& x), BTNode* * t) t) if(t) if(t) PostOr

60、der(Visit, t-lChild); PostOrder(Visit, t-lChild); PostOrder(Visit, t-rChild); PostOrder(Visit, t-rChild); Visit(t-element); 顯然，二叉樹遍歷算法基本操作是訪問結(jié)點(diǎn)顯然，二叉樹遍歷算法基本操作是訪問結(jié)點(diǎn)，不論按何種次序遍歷，對(duì)含有，不論按何種次序遍歷，對(duì)含有n n個(gè)結(jié)點(diǎn)的二叉?zhèn)€結(jié)點(diǎn)的二叉樹，其時(shí)間復(fù)雜度均為樹，其時(shí)間復(fù)雜度均為O(n)O(n)。關(guān)于三種遍歷算法：關(guān)于三種遍歷算法：1.1.給定一棵二叉樹，能寫出它的三種遍歷序列。給定一棵二叉樹，能寫出它的三種遍歷序列。2.2.給出二叉樹的給出二叉樹的先序遍歷先序遍歷序列和序列和中序遍歷中序遍歷序列可以序列可以唯一唯一確確 定一棵二叉樹。定一棵二叉樹。3.3.給出二叉樹的給出二叉樹的后序遍歷后序遍歷序列和序列和中序遍歷中序遍歷序列可以序列可以唯一唯一確確 定一棵二叉樹。定一棵二叉樹。4.4.當(dāng)當(dāng)n1n1時(shí)，給出二叉樹的時(shí)，給出二叉樹的先先序遍歷序遍歷序列和序列和后序遍歷后序遍歷序列序列不可以不可以唯唯一確定一棵二叉樹。一確定一棵二叉樹。例如：例如：先先序序列：序序列：ABAB，后序序列：