1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)/第六章 樹和二叉樹/下面呢，我們就討論第六章、樹和二叉樹。那么我們回憶一下數(shù)據(jù)結(jié)構(gòu)四大類。第一類，線性結(jié)構(gòu)，除了廣義表以外，我們都討論完了。現(xiàn)在我們開始討論第二大類，樹形結(jié)構(gòu)，在樹形結(jié)構(gòu)里面呢，我們主要討論兩種結(jié)構(gòu)。一類樹，一類二叉樹(線性結(jié)構(gòu)里頭我們討論了什么？)。首先，我們先看樹的數(shù)據(jù)類型定義。那先看數(shù)據(jù)對象D：具有相同特性的數(shù)據(jù)元素的集合，這就是它的數(shù)據(jù)對象。數(shù)據(jù)元素之間是一個什么樣的關(guān)系呢，我們用下面這段話來描述。如果數(shù)據(jù)對象是一個空集，我們稱之為空樹。從這里

2、看得出來，所有的數(shù)據(jù)結(jié)構(gòu)都這樣一個空的這樣一個結(jié)構(gòu)?？沾⒖毡淼鹊?。空樹的意思是一個數(shù)據(jù)元素都沒有。否則的話，如果這個集合不是一個空集的話，那么在這個數(shù)據(jù)結(jié)構(gòu)里面一定存在一個成為根的數(shù)據(jù)元素root，而且這個數(shù)據(jù)元素一定是唯一的。就是說，一定存在，而且唯一。那么就是說除了空樹以外，如果數(shù)據(jù)集合里面只有一個數(shù)據(jù)元素的話，那么這個數(shù)據(jù)元素，就是這個樹的根。如果說這個數(shù)據(jù)集合里面的元素個數(shù)大于1的話，其余個結(jié)點呢，我們一定可以給它分成m個子集。這些子集互不相交。并且每個子集本身呢，又是一棵符合上面定義的樹。這些子集是樹，而且稱之為根的子樹。我們看一個例子，（畫圖）ABCDEFGIJ 這是一個樹，當(dāng)然

3、它不是空樹，這個樹呢是9個數(shù)據(jù)元素的集合。一定存在這一個叫做根的結(jié)點。這個A呢，我們稱之為樹根，除了這個根以外，我們可以分成這樣三個集合。以B開始的一個子集，以C開始的一個子集，和D開始的一個子集。這三個子集互不相交，每個子集呢又是一棵樹，并且它和根呢，有一個關(guān)系存在，這棵樹叫做根的子樹。這棵樹呢，又存在一個根結(jié)點，這root根和我們子樹根之間，存在這一個這樣一個前驅(qū)后繼的關(guān)系，一般畫樹，我們不畫箭頭，但是我們討論的是有向樹，是有箭頭的。就是說BCD是A的后繼。那對于B的這樣一個子樹，又是符合我們定義的子樹，那就是說它有一個根結(jié)點，它有兩顆子樹。在根結(jié)點和子樹根之間呢，又存在一個前驅(qū)和后繼的關(guān)

4、系，那對E、F來說，它們本身又是一顆樹。對于E這棵樹來說，它的數(shù)據(jù)元素只有一個，所以它是僅含有根結(jié)點的一顆子樹。在定義的時候我們說還有空樹的，但是在實際使用的時候，是沒有意義的。由于我們數(shù)據(jù)結(jié)構(gòu)和離散數(shù)學(xué)還是有一定的關(guān)系的，在離散數(shù)學(xué)中，為了一些數(shù)學(xué)上的完整性的定義，才有空樹這樣的定義，在我們數(shù)據(jù)結(jié)構(gòu)中也有定義，單實際上用處不大。這就是樹的類型的一個結(jié)構(gòu)特性。下面我們本來就該討論基本操作了，但是對于樹來講呢，還有一些基本術(shù)語介紹一下，以便我們對基本操作的理解。下面就看有關(guān)樹的基本術(shù)語?，F(xiàn)在先來看一下有關(guān)樹的術(shù)語。樹當(dāng)中，它的基本單位是一個結(jié)點：什么叫結(jié)點呢：數(shù)據(jù)元素+若干指向子樹的分支比如剛才

5、我們舉的那個例子，一個數(shù)據(jù)元素A+指向BCD的子樹的分支，那就稱一個結(jié)點。結(jié)點的度：結(jié)點上指向分支的個數(shù)（在樹上面每個結(jié)點的度可能是不一樣的，比如我們分解到只含有一個根結(jié)點的子樹時，它沒有子樹也沒有分支，那它的度就是零。對于剛才的根結(jié)點，它的度就是3.）整個樹的度; 我們定義為：整個樹當(dāng)中所有結(jié)點的度的最大值。對于我們剛才的那棵樹呢，這棵樹的度呢，就是3，因為，結(jié)點最大的度是3.葉子結(jié)點：對樹來說，分解到最后，對于子樹來說就一個根節(jié)點，度為零的結(jié)點。（也就是只有一個根結(jié)點的子樹。對于這樣的一個結(jié)點，是沒有子樹的，它對于整個樹來說，是很特殊的，叫做葉子結(jié)點。除了葉子結(jié)點，其他的結(jié)點的度都是大與零

6、的。）反過來我們把它叫做分支結(jié)點：就是那些度大于零的結(jié)點。對于一棵樹來說呢，我們經(jīng)常要談到的是，根結(jié)點，葉子結(jié)點、分支結(jié)點。當(dāng)然了，根結(jié)點也是分支結(jié)點的一種。樹呢，我們看是一個層次的結(jié)構(gòu)，那從根結(jié)點，沿著分支呢，能走到任何一個結(jié)點。從根到這個結(jié)點所經(jīng)過的分支和結(jié)點，構(gòu)成了一條路徑。這條路徑叫從根到這個結(jié)點的路徑。在樹里面還有一些術(shù)語，根我們族譜里面的術(shù)語差不多。因為，樹這樣的一個結(jié)構(gòu)，最早就是從族譜中的來的。有孩子結(jié)點、雙親結(jié)點、前面我們講到了根和子樹根的關(guān)系，是父子關(guān)系，或者是雙親和孩子的關(guān)系。對于樹根來說，是樹根的孩子，那么反過來，這個跟對子樹根來說，它是雙親。兄弟結(jié)點呢，是有相同的根的子

7、樹，這些子樹根之間的關(guān)系呢，就是兄弟關(guān)系了。它們有相同的雙親。有了兄弟結(jié)點，呢我們還可以得到堂兄弟結(jié)點。祖先結(jié)點的定義呢，我們說從根到結(jié)點有一條路徑，這條路徑有若干個結(jié)點，這些結(jié)點都是它的祖先。包括它的祖父、太祖父、等這些都是它的祖先。那子孫結(jié)點就是，在這棵根以下的結(jié)點，都是它的子孫結(jié)點。樹是一個層次的關(guān)系：所以在樹上的結(jié)點呢，它有它的層次，我們假設(shè)根結(jié)點的層次為1 以下的結(jié)點呢，就依次類推了。那也就是說第l層的結(jié)點的子樹根結(jié)點的層次為l+1層。從剛才這棵樹看，A是第一層的，BCD是第二層的。EFG是第三層，的 IJ是第四層。葉子結(jié)點最大的層次數(shù)，我們稱之為樹的深度。樹的深度：樹中葉子結(jié)點所在

8、的最大層次，就是樹的深度。這里面我們要強調(diào)一下，數(shù)據(jù)結(jié)構(gòu)在這個樹的層次上來講呢，有時候約定是不一樣的，有的書上把根結(jié)點的層數(shù)設(shè)為0，有的設(shè)為1.我們在這設(shè)定為1. 這個時候呢。樹的深度是不變的，還是最大層次數(shù)，葉子結(jié)點的層數(shù)變了，變成原來的層數(shù)減1. （在看別的書的時候，要看一下說明，如果根節(jié)點層為0的話，深度和最大的葉子節(jié)點層次數(shù)差1）那么在數(shù)據(jù)結(jié)構(gòu)中呢，樹和森林是不一樣的，但又是兩個密切相依賴的兩個概念，森林呢，是M棵互不相交樹的集合。反過來，從另外一個角度，樹的定義可以由森林來定義。就是說 任何一棵非空樹是一個二元組 T=（root，F(xiàn)）都是有一個根和子樹森林構(gòu)成的。 （畫圖）比如（這樣

9、的一個樹，我去掉了根結(jié)點，就可以看作是由3棵樹構(gòu)成的一個森林，這是一二三棵樹。這個森林加上一個根，就是一顆樹。反過來，森林又是樹的集合。這個概念我們以后也會經(jīng)常用到）下面我們看，樹的基本操作。樹的基本操作比較多，我們可以分為三類進行討論，一類是查找，一類是插入，一類是刪除。我們先看查找。查找呢一種是特定的查找一種是按關(guān)系查找，比如我們查樹的根root(T)。或者找樹上的某個結(jié)點返回它的值、或者是給一個值返回樹上的這個結(jié)點。Value(T,cur_e)。一種是按關(guān)系的查找，有找雙親結(jié)點Parent(T,cur_e)。取這個結(jié)點的雙親。 反過來，我們按照孩子的關(guān)系來找。樹呢，有多個孩子，以后，我們

10、會知道，我們是根據(jù)第一個孩子，和兄弟關(guān)系來找的。一個是每一個結(jié)點最左邊的孩子，一個是每一個結(jié)點的右兄弟。那我們看，通過找這個結(jié)點的左孩子LeftChild(T,cur_e)，在找這個孩子結(jié)點的右兄弟RightSibling(T,cur_e)，當(dāng)把有兄弟找完之后，這個結(jié)點的孩子結(jié)點就完全找到了。還有就是對樹的特性進行的操作，一個是看樹是不是為空TreeEmpty(T)。一個是樹的深度TreeDepth(T)，還有一個樹的重要操作呢，是樹的遍歷TraverseTree(T,Visit()。以上是根查找相關(guān)的操作。第二呢，我們看插入的操作，一，我們看初始化一個空樹InitTree(&T)。二、還有根

11、據(jù)定義來建立一顆樹CreateTree(&T,definition)，這個定義呢，可以有各種給法，比如給一個root和一個森林?；蛘吣兀医o樹上的每個結(jié)點，結(jié)點的每個孩子結(jié)點，一直到葉子結(jié)點為止，這樣也可以定義一個樹。所以呢，我可以根據(jù)一個定義，創(chuàng)建一棵樹。三、給樹的某個結(jié)點賦予一個值A(chǔ)ssign(T,cur_e, value)。第四個呢，插入一個孩子結(jié)點InsertChild(&T,&p, i, c)。就是在T這棵書上，在p所指的這個結(jié)點上，插入一個c的一個子樹，位置呢，由i來確定。第三個呢，是關(guān)于刪除的操作，這些操作包括，清空樹ClearTree(&T)、銷毀樹DestroyTree(&T

12、)，把樹T中p結(jié)點的第i個孩子刪除, DeleteChild(&T, &p, i).這是樹的基本操作的定義。我們討論的樹呢我們要說明一下，我們討論的樹呢，是一個有向樹。雖然我們畫圖的時候不畫箭頭，但是我們根和子樹之間呢，有一個前驅(qū)和后繼的關(guān)系，所以每一棵樹 1） 有確定的根，2）樹根和子樹根之間有為有向的關(guān)系。一般就叫樹，但實際上，討論的是有向樹。但是我們討論的樹和子樹之間呢可以有次序，也可以無次序，子樹之間是否存在次序關(guān)系，決定了我們這棵樹是有序樹，還是無序樹。子樹之間存在次序則是有序樹，子樹之間不存在次序則是無序樹。我們看最早的例子，這里我們再畫一顆樹。這兩棵樹的差別在于哪里呢，差別不在于

13、結(jié)構(gòu)，9個元素，三個棵子樹。只不過子樹的次序位置變化了。如果你討論的是無序樹，那么這兩棵樹是相同的，如果你討論的是有序樹，那么這兩棵樹就不等同，通常我們討論的樹呢，都是無序樹（除了你特殊說明以外）。因為我們樹這個結(jié)構(gòu)在我們非數(shù)值型程序領(lǐng)域，主要描述我們?nèi)粘Ｉ钪械倪@種層次關(guān)系，也就是上下級的關(guān)系，而對同級來說呢，是不講次序的。因此，我們討論的主要是無序樹，那也就是說在無序樹底下，這兩棵樹是等同的。這個呢，我們說是有關(guān)樹的一些定義?，F(xiàn)在，我們把樹這樣一個結(jié)構(gòu)呢，和線性結(jié)構(gòu)來比較一下，首先我們看，線性結(jié)構(gòu)，它肯定存在一個沒有前驅(qū)的第一個數(shù)據(jù)元素，那么在樹形結(jié)構(gòu)里面，也存在這一個沒有前驅(qū)的元素，就是

14、這個根結(jié)點。這一點呢，和順序結(jié)構(gòu)是類似的。都存在一個沒有前驅(qū)的數(shù)據(jù)元素。在線性結(jié)構(gòu)里面，只有一個沒有后繼的線性數(shù)據(jù)元素， 我們稱之為最后一個元素，那么在樹結(jié)構(gòu)里面呢，就是度為零的結(jié)點，我們稱之為葉子結(jié)點，在樹里面，葉子結(jié)點就不是一個了。而可以有多個。其他的元素呢，在線性結(jié)構(gòu)里面呢，都唯一有一個前驅(qū)，一個后繼。樹中的其他結(jié)點呢，分支節(jié)點，有一個前驅(qū)，可能有多個后繼。所以我們說線性結(jié)構(gòu)呢，是一種一對一的結(jié)構(gòu)，而樹形結(jié)構(gòu)呢，是一種一對多的結(jié)構(gòu)。從根開始，它可以有多個子樹根，而每一個子樹根上面只有一個雙親，底下呢，可以有多個孩子結(jié)點。一直到葉子結(jié)點呢，它沒有后繼。這就是從線性結(jié)構(gòu)一對一的關(guān)系，擴展到樹

15、結(jié)構(gòu)1對多的關(guān)系。以后我們會知道將樹的結(jié)構(gòu)再擴展到圖的結(jié)構(gòu)。那么這個就是關(guān)于樹的類型定義。當(dāng)然我們一般情況下，就該討論樹的實現(xiàn)和操作了，但是由于樹的結(jié)構(gòu)有它的不確定性，就是說它每個結(jié)點的度呢是可以不同的，它處理起來呢，相對來說比較麻煩一些。在這種情況下，我們就討論一種結(jié)構(gòu)相對固定的樹，也就是下面我們要將的二叉樹，在以后我們會知道對樹的這樣一種結(jié)構(gòu)我們會轉(zhuǎn)化為二叉樹來討論的。所以我們下面就要從新看一下二叉樹的類型的定義。第二個問題，二叉樹的類型定義。二叉樹的定義呢，我們就不按照數(shù)據(jù)對象、和數(shù)據(jù)關(guān)系來說了，簡單的看一下文字的描述就可以了，這樣比較簡潔。二叉樹或為空樹；或是由一個根結(jié)點加上兩棵分別稱

16、為左子樹和右子樹的、互不相交的二叉樹組成的。（畫一個二叉樹的例子）二叉樹也一定有一個根結(jié)點。除了根結(jié)點以外，其他結(jié)點分成兩個互不相交的結(jié)點的集合。每一個集合是根的子樹，同時它本身又是滿足定義的一顆二叉樹。二叉樹的定義上有非常重要的一句話。就是這棵二叉樹叫做根的左子樹。這棵二叉樹叫做根的右子樹。那么我們再看二叉樹的定義，雖然每個根結(jié)點只有兩棵子樹，這兩棵子樹都有特定的含義，一個叫左子樹，一個叫右子樹。當(dāng)然這個左、右子樹本身又可以是空樹。比如B這個二叉樹，它是由一個空的左子樹和一個不空的右子樹組成的。二C這個二叉樹是由一個不空的左子樹和空的右子樹構(gòu)成的。同樣對于D這棵樹，它是由左右都為空的二叉樹構(gòu)

17、成的。所以從上面的定義來看呢，二叉樹有五種基本形態(tài)，（畫圖）一種是空樹，第二種是僅含有一個空節(jié)點的樹、第三種是左子樹不空，右子樹為空的樹第四種是右子樹不空，左子樹為空的樹，第五種那就是左右子樹都不空的樹。左子樹為空和右子樹為空這兩個概念是不同的,不能完全等同，這與我們樹里面的有序無序樹的情況是不同的。比如有序樹，只有一顆子樹（畫圖），對于二叉樹來說沒有這樣的二叉樹。對于二叉樹來說，你必須明確到底是左子樹空，還是右子樹空。這一點是很重要的概念，在以后我們講樹的轉(zhuǎn)化的時候呢，我們就會體會到左右的重要性了。二叉樹的基本操作呢，跟樹一樣，我們也分查找、插入、刪除三種來看。查找分特定的查找，比如說找根，

18、差值為e的某個節(jié)點。也可以按關(guān)系來查找，找這個元素的雙親，找結(jié)點的左孩子（也就是左子樹根），右子樹根。如果本身是左子樹根，那它就存在右兄弟。如果它本身就是右子樹根，那它可能存在左兄弟。還有一些對樹的狀態(tài)的一些操作，比如判樹是不是空樹，求二叉樹的深度。對于二叉樹呢，還有四種遍歷的操作。插入：初始化、改變二叉樹上某個結(jié)點的值、根據(jù)一個定義生成一個二叉樹，比如給出一個根，一個左子樹，一棵右子樹，我們可以構(gòu)造一個二叉樹。插入，在某個結(jié)點上插入一顆以C為根結(jié)點的二叉樹。插入的位置可以是左子樹也可以是右子樹。刪除：把二叉樹清空，銷毀二叉樹、還有刪除某個結(jié)點的一顆左或右子樹。一般沒有刪除一個節(jié)點的操作，和樹

19、也一樣，要刪就刪除一顆子樹。二叉樹是非常重要的，因為它的結(jié)構(gòu)比較固定，因而有一些重要的特性；我們現(xiàn)在來看一下：性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點（i=1）.怎么證明呢，我們用歸納法：（畫圖）。I=1的時候，顯然成立，只有一個根結(jié)點。2的零次方等于1.我們現(xiàn)在假設(shè)i在第k層滿足這樣的條件就是i=k時，它的結(jié)點數(shù)呢，滿足最多也就是2 k-1個。那當(dāng)i=k+1時，由于這一層的結(jié)點是上一層結(jié)點的子樹根。每一個結(jié)點最多有兩個子樹根。那在i=k+1層，結(jié)點數(shù)最多也就是上一層結(jié)點數(shù)2.就是2 k-1 *2=2 k =2 (k+1)-1 性質(zhì)2：它是說，深度為h的二叉樹。它的結(jié)點數(shù)最多為2 h -

20、1。深度為h的二叉樹呢共有h層，我們讓每一層取得結(jié)點數(shù)最多?？匆豢磆曾最多有多少。從第一層20+21+22+。+2h-1 = 2 h -1（等比數(shù)列的求和公式）。所以深度為k的二叉樹上至多還有2 k -1。這個性質(zhì)是由性質(zhì)1得到的。性質(zhì)3：對于任何一顆二叉樹，如果它含有n0個葉子節(jié)點。n2個度為2的結(jié)點。那么它必然存在一個關(guān)系式：n0=n2+1. ( 二叉樹上的節(jié)點只有三種， 有多少個度為1的結(jié)點，度為0的結(jié)點和度為2的結(jié)點一定滿足這樣的關(guān)系。（畫圖，假定二叉樹上度為零的結(jié)點是n0.）度為1的結(jié)點的個數(shù)是n1. 度為2的結(jié)點個數(shù)為n2。那么總的和肯定是二叉樹上總的結(jié)點數(shù)目n=n0+n1+n2,

21、 如果二叉樹上分支的數(shù)目等于b的話，我們分支的數(shù)目和節(jié)點的數(shù)目的關(guān)系是什么呢？（畫圖說明）對于二叉樹的結(jié)點來說，除了根結(jié)點，其他的結(jié)點都能找到它的雙親，有一個雙親說明有一個分支，那意味著結(jié)點數(shù)比分支數(shù)多了一個，也就是n=b+1。那么我們看這些分支是誰產(chǎn)生的呢，我們反過來看， 度為1的結(jié)點產(chǎn)生一個分支，度為2的結(jié)點產(chǎn)生兩個分支。度為零的結(jié)點不產(chǎn)生分支。因此b=2n2+n1那n=2n2+n1+1) 。這樣我們就得到了兩個式子，一個是n=n0+n1+n2這是從結(jié)點的度的類型這個方面來看。而第二式子則表明了這些所有節(jié)點n和分支數(shù)目的關(guān)系，而這個分支數(shù)目是度為1和度為2的結(jié)點產(chǎn)生的。因此，把上面兩個式子

22、聯(lián)立一下，相減：得到n0-1-n2=0。這就是n0=n2+1。 那這個式子的意思就是，不管二叉樹上有多少個度為1的結(jié)點，度為零的結(jié)點和度為2的結(jié)點存在著這樣一個關(guān)系。后面兩種重要特性呢，涉及到兩種特殊的樹。一種叫滿二叉樹：它指的是深度為k且含有2k-1個結(jié)點的二叉樹。那也就是說什么是滿二叉樹，那就是說這個二叉樹上面不存在度為1的結(jié)點。而且除了葉子結(jié)點以外，每個結(jié)點都有兩棵子樹。而且只有最后一層是葉子結(jié)點。其他都是分支結(jié)點。就是每一層都取它最大的結(jié)點數(shù)。那么就是一個滿二叉樹。對于滿二叉樹，我們可以從上到下，從左到右這樣進行編號，進行編號以后呢，我們就引出了完全二叉樹的概念：樹中所含有的n個結(jié)點和

23、滿二叉樹中編號為1至n的結(jié)點一一對應(yīng)。下面我們畫一個圖來表示。這是一棵滿二叉樹、我對它進行編號，從1到15.。什么是完全二叉樹呢，就是說如果完全二叉樹有5個結(jié)點。那么這五個結(jié)點應(yīng)該和滿二叉樹的1到5個結(jié)點對應(yīng)。如果有6個結(jié)點、7個結(jié)點。那也就是說完全二叉樹有這樣一個特性，上面每一層都是滿二叉樹。只有最后一層不滿。而且不滿也是按照順序從左到右的依次出現(xiàn)。完全二叉樹，在以后的應(yīng)用中呢，是經(jīng)常會用到的，所以對于完全二叉樹有兩個重要的特性。（如一個節(jié)點和編號10對應(yīng)而是和編號11對應(yīng)了）性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為logn+1。我們看這個的證明。（畫圖）假定這個完全二叉樹的深度是k。那么它

24、的節(jié)點數(shù)最大不會超過2k-1，最小呢一定大于深度為k-1的滿二叉樹，因為你至少的在深度為k的這一層有一個結(jié)點。即 2k-1-1n=2k-1那也可以這樣寫：就是2k-1=n2k 這樣，我們給這個不等式兩邊取對數(shù)。k-1=log2nn，則該結(jié)點無左孩子，否則，編號為2i的結(jié)點為其左孩子結(jié)點；(3) 若2i+1n，則該結(jié)點無右孩子結(jié)點，否則，編號為2i+1的結(jié)點為其右孩子結(jié)點。下面我們就來證明這三個特性，我們先看對于編號為i的結(jié)點如果左孩子存在的話，一定是編號為2i，如果右孩子存在的話一定是2i+1. 我們看對于i=1的時候，我們可以看到如果有左右孩子的話，（畫圖）一定是2i和2i+1?，F(xiàn)在我們看一

25、般的情況，對某一層，假設(shè)為第k層某一個結(jié)點的編號。對于完全二叉樹來說，也就是說前面k-1層是滿的。這個k-1層結(jié)點的個數(shù)呢，是2的k-1次方減1.因此這個節(jié)點的編號一定是2的k-1次方。下面，我們看它的下一層，這意味著前面k層的個數(shù)是滿的，一定是2的k次方減1.也就是說這個結(jié)點的編號是2的k次方。那么它的兄弟結(jié)點呢，一定是2的k次方加1.那么就是說，如果這兩個結(jié)點存在的話，也就是說2的k次方加1小于n的話，那么這個就成立的。我們用歸納法，對于第i個結(jié)點滿足這個關(guān)系，就是I 左孩子是2i，右孩子是2i+1. 那么我們看它的兄弟，它的兄弟呢，編號一定是i+1. 它的兄弟的左孩子的編號，顯然是這個2

26、i+1結(jié)點緊挨著的下一個編號。也就是2i+1的堂兄弟應(yīng)該是2i+2，它的右孩子呢，應(yīng)該是2i+3. 2i+2=2(i+1)，2i+3=2(i+1)+1 所以呢我們這個假設(shè)就是成立的，由歸納證明就可以得到。那反過來由這個關(guān)系我們很容易得到，如果這個結(jié)點的編號是i的話，那它的雙親就是i/2。那如果這個結(jié)點是i的話，那么他的雙親就是i/2取下整。這個關(guān)系呢，是我們以后經(jīng)常會用到的。 關(guān)于二叉樹的概念呢，我們就講到這里。 下面我們看一下，二叉樹的存儲結(jié)構(gòu)。二叉樹有各種存儲表示法，第一種呢，叫二叉樹的順序存儲表示。我們用C語言來描述它，就是把二叉樹的這個結(jié)點呢，存儲在一維數(shù)組中間。這個一維數(shù)組的最大值呢

27、，我們設(shè)定為100. 二叉樹結(jié)點的個數(shù)呢，由具體的二叉樹的結(jié)點個數(shù)來定。那么如何把這個層次的關(guān)系、左右子樹的關(guān)系用一個一維數(shù)組來表示它呢。我們知道一維數(shù)組就存儲ABCDEF這樣的結(jié)點。我們知道順序存儲結(jié)構(gòu)僅僅存儲的這些ABCDEF結(jié)點，而不存儲他們之間的關(guān)系，他們的關(guān)系用固定的的一個位置上的相鄰來表示。如果我們把這棵樹看成是滿二叉樹或完全二叉樹的一部分。那也就是說把根結(jié)點放在一維數(shù)組的第一個分量里面，編號為1.的話，那么BD就應(yīng)該是2.3.。這樣的話，我們用含有六個元素的二叉樹呢，我們用一個14個分量的一維數(shù)組就可以完全表示了。如下圖所示：那么也就是說為了表示這樣一個具體的二叉樹的結(jié)點呢，每個

28、結(jié)點不是挨著存儲。而是按照它的編號是多少而存在相應(yīng)的數(shù)組分量里面。顯然，這種存儲方式呢，僅適合與完全二叉樹。因為對于完全二叉樹來說，前面的元素都是滿的。而這個二叉樹呢，為了把這個樹的左右關(guān)系表示出來，我們必須空出很多的空間，所以就很浪費空間了。因此，對于任意的一個二叉樹呢，我們不用這樣的存儲方式。但是對于完全二叉樹呢，用這一種方式是相當(dāng)方便的。這是第一種順序存儲表示。由于二叉樹有兩個后繼，我們經(jīng)常的用兩個指針指向它的后繼，下面呢，我們就看看二叉樹的鏈式存儲表示。二叉樹的鏈式存儲表示，由于結(jié)點的不同，可以有各種的存儲表示方法。其中最簡單的是二叉鏈表，所謂二叉鏈表，就是二叉樹的結(jié)點里面含有兩個指針

29、域，一個數(shù)據(jù)域。整個樹呢，我們就用指向根結(jié)點的指針就可以表示了。我們簡單的畫一棵二叉樹。（畫圖） 每個結(jié)點呢，有兩個指針域，左邊的指示它左子樹的根，右邊的指示它右子樹的根，對A來說，它的左子樹根是B，B的左子樹根為空，右子樹根是C。而C是葉子結(jié)點。葉子結(jié)點的指針為空，整個二叉樹用指向根結(jié)點的一個指針就可以表示了。每個結(jié)點呢，都有指向左子樹和指向右子樹的根，那它的雙親關(guān)系呢，是當(dāng)我找到這個結(jié)點是某一個結(jié)點的左子樹或右子樹的話，那反過來這個結(jié)點就是這個結(jié)點的雙親，所以雙親的信息，我們也包含著，只是是一個隱含的信息，而不是顯著的。那么如果某些情況下你想把雙親結(jié)點的信息表示出來的話，那么很簡單，我們就

30、在指針域里面加一個指針，加一個指針域指向它的雙親，那么根結(jié)點的雙親域顯然是空的，B的雙親是A，這個結(jié)點雙親也是A，這個結(jié)點雙親是B。這樣的話結(jié)點里面有三個指針了，我們把這就叫做三叉鏈表。三叉鏈表和剛才二叉鏈表的差別呢，僅僅是多設(shè)了一個指針域。整個二叉樹呢，還是由指向根結(jié)點的一個指針來表示了。那么我們可以只指示左右子樹，隱含著雙親信息，反過來我們也可以僅僅表示雙親信息，讓左右子樹的信息隱含在內(nèi)，來表示這個二叉樹。但是對于二叉樹來說，它的子樹根呢，一定是有左右之分的。因此如果只含有雙親信息的話，表示是不完備的。那么這個結(jié)點呢我們就用一個數(shù)據(jù)域，指向雙親的指針，和左右孩子標志域來表示。整個二叉樹呢，

31、我們是把這些所有的結(jié)點放在一個一維數(shù)組里面來表示的。加上結(jié)點的數(shù)目，和根結(jié)點的位置，就形成了這樣二叉樹的一個表示方法。這個表示方法，我們稱之為雙親鏈表。例如我們對剛才這棵二叉樹，我們有四個結(jié)點ABCD，每個結(jié)點呢，在數(shù)組里面有一個下標，結(jié)點本身的有一個數(shù)據(jù)域，還有一個雙親域，這個雙親域我們不是給出雙親結(jié)點的數(shù)據(jù)，而是給出他的雙親結(jié)點在這個一維數(shù)組里面所在的位置，它是在零的分量里面，所以它的雙親結(jié)點就是零。同時B呢是A的左孩子，D是A的右孩子。C呢，是B的右孩子，C的雙親就是1。用-1來表示沒有雙親。那么整個二叉樹呢，是用這樣一個結(jié)點類型的一個一維數(shù)組來表示的。同時，我們還要用，根結(jié)點的位置0.

32、和整個結(jié)點的數(shù)目4來表示。那也就是說，我們從0到3的這個數(shù)組里面的分量呢，存儲著這個結(jié)點里面的信息。這就是雙親鏈表。因為我們樹呢，是從根往下的一個有向樹，因此我們只用一個指示根的指針和一個二叉鏈表呢，就可以完全確定這二叉樹了。雙親鏈表呢，如果我們只用一個指向雙親的指針的話，那每個結(jié)點就是孤立的。分散的。所以我們要把它和起來，和在一個一維數(shù)組里面。才能夠整個來表示它。二叉樹的鏈式存儲表示呢，還有一種線索鏈表，我們等以后講到線索樹的時候再講。前面，我們討論了三個問題，一個是樹的類型定義，二叉樹的類型定義，以及二叉樹的特性，還有二叉樹的存儲結(jié)構(gòu)。下面我們要討論這一章的一個主要的問題，叫做二叉樹的遍歷

33、。那么在這一節(jié)里面，我們準備討論這樣五個問題。這五個問題從問題的提出，到遍歷算法的描述，一直到遍歷算法的應(yīng)用。我們首先看，問題的提出。也就是什么是遍歷：順著某一條搜索路徑巡訪二叉樹中的結(jié)點，使得每個結(jié)點均被訪問一次，而且僅僅被訪問一次。這個訪問的含義呢，可以是各種個樣的。 比如說，輸出結(jié)點信息，或?qū)Y(jié)點進行賦值。那么這樣一個結(jié)點遍歷的問題呢，對于任何一個結(jié)構(gòu)都是存在的。遍歷是任何一個結(jié)構(gòu)的基本操作，但為什么我們前面沒有強調(diào)呢，因為對線性結(jié)構(gòu)來說，每個結(jié)點只有一個后繼，因此從第一個結(jié)點出發(fā)，它只有唯一的一個搜索路徑，這是很自然的，所以我們就不需要重點的討論，自然就會實現(xiàn)這樣一個遍歷的操作了。但是

34、二叉樹不一樣，二叉樹是一個非線性結(jié)構(gòu)。每個結(jié)點有兩個后繼，那么就存在著按什么樣的搜索路徑來進行遍歷的問題了。對于二叉樹來說，它有兩個后繼，它可以有這樣三條搜索路徑。第一條是先上后下的按層次的遍歷。先訪問根結(jié)點，然后訪問根節(jié)點的子樹根。對于每一層來說呢，先左后右。那么先訪問它的根結(jié)點，如果有左子樹，訪問它的左子樹，如果沒有左子樹，訪問它的右子樹。然后在訪問它子樹的子樹。一層一層的往下遍歷，這是一種搜索路徑。第二種：先左后右的遍歷，二叉樹不是有兩棵子樹嗎？整個二叉樹的遍歷就可以看作是，對左子樹的遍歷和對右子樹的遍歷的和。 那么對于根結(jié)點的遍歷，就是根結(jié)點就有一個結(jié)點，直接訪問呢就好了。 那么左右子

35、樹呢，有一個先一個后的問題。一種搜索路徑呢，是我先左后右，我先去遍歷左子樹，然后在遍歷右子樹上所有的結(jié)點。反過來，還有就是先訪問右子樹上的結(jié)點，然后再訪問左子樹上的結(jié)點。這兩條路徑呢是相反，單是完全對稱的。我們討論其中一條就可以了。下面我們就重點討論先左后右的遍歷。先左后右的遍歷算法有先根、中根、后根三種遍歷算法。那我們首先來看一看什么是先序的遍歷算法，什么是中序的遍歷算法，什么是后序的遍歷算法。我們現(xiàn)在有這樣一顆二叉樹。（郵遞員模擬的問題）下面看先根序遍歷算法的描述，很簡單：如果二叉樹為空樹，則空操作，什么就不用做了，否則，的話，訪問根結(jié)點先序遍歷左子樹先序遍歷右子樹中根序遍歷算法的描述，很

36、簡單：如果二叉樹為空樹，則空操作，否則：中序遍歷左子樹訪問根結(jié)點中序遍歷右子樹后根序遍歷算法的描述，很簡單：如果二叉樹為空樹，則空操作，否則：后序遍歷左子樹后序遍歷右子樹訪問根結(jié)點這里需要注意的是如果你整個二叉樹是后序遍歷，那么你遍歷子樹的時候也是什么樣的遍歷。（中序、先序是一樣的。）上面呢，我們給出了遍歷的定義。下面也就是第三個問題，我們看一下算法的遞歸描述。我們用C語言呢，來把剛才的算法描述一下。整個算法的描述呢，主要有遞歸和非遞歸的算法，我們主要看一下遞歸的算法。如果二叉樹是空樹，什么也不做了，所以我們先序遍歷是在二叉樹不空的前提底下。、void Preorder (BiTree T,

37、void( *visit)(TElemType& e) / 先序遍歷二叉樹 if (T) visit(T-data); / 訪問結(jié)點Preorder(T-lchild, visit); / 遍歷左子樹Preorder(T-rchild, visit); / 遍歷右子樹其他的中序和后序遍歷。與這個是非常類似的，只要你調(diào)整這三個語句的位置就可以了。要注意的是，還是采用遞歸的方式來進行遍歷的。第四個問題，有的時候呢，我們還需要有非遞歸的算法的描述。我們現(xiàn)在就看一下，中序遍歷算法的非遞歸算法是怎么樣的。我們首先分析一下，中序遍歷算法的規(guī)律。中序遍歷，對于每個結(jié)點來說，都是先遍歷它的左子樹，因此對于這個

38、二叉樹來說呢，對于A來說，先遍歷左子樹。同樣對于B子樹來說，也是先遍歷左子樹。什么時候訪問它本身呢，就是在左子樹空的時候，才接著訪問B結(jié)點。所以我們從A開始中序訪問遍歷的第一個結(jié)點一定是B.也就是說我們從根節(jié)點出發(fā)，一直往左走，如果這個結(jié)點還有左子樹還往左走，走到這個結(jié)點的左子樹是空為止。那這個結(jié)點B就是我遍歷訪問的第一個結(jié)點。那么我一直往左走，我將來還是一定要回來的。也就是說我要能在訪問完左子樹的情況下，退回到這個根結(jié)點。也就是說我要能夠退回到A.也就是說能夠順著原路退回，因此我們要把路過的結(jié)點給保留下來。那也就是什么啊，先走到的后訪問，后走到的先訪問。顯然保留這些結(jié)點的一個數(shù)據(jù)結(jié)構(gòu)呢，就應(yīng)

39、該是一個棧了。假定我們現(xiàn)在有一個棧在這里。現(xiàn)在我們從A出發(fā)，往左走。A呢，就要入棧。入棧以后，我們就到了B。例如有一個指針指向B了。這時候，我們發(fā)現(xiàn)B呢，沒有左子樹。那么我們就直接對B進行訪問。應(yīng)該是遍歷右子樹。那現(xiàn)在有右子樹，就進行遍歷。所以我們就將p指過來，遍歷以右子樹為根的一個二叉樹。對于C來說它也有左子樹，它也要入棧?，F(xiàn)在指針走到D。走到D以后，發(fā)現(xiàn)D沒有左子樹。所以就對他進行訪問，D訪問完了以后應(yīng)該是去遍歷右子樹，但是現(xiàn)在右子樹是空，說明以D為根的這個二叉樹已經(jīng)遍歷完了。遍歷完了以后，我們要往回退，退到哪里呢，退到C。退到C呢。我們知道這個C退出來，肯定是從左子樹回來的。所以對它進行

40、訪問。訪問完了以后，我們要遍歷右子樹。現(xiàn)在右子樹是空的。那么以C為根的子樹也遍歷完了。顯然應(yīng)該還是往回退。根據(jù)棧頂?shù)闹甘荆屯说絘了。退到A后呢，就應(yīng)該對它進行訪問了。訪問完了以后，我們還要遍歷以它的右子樹根為根的這樣一個二叉樹。從新往左走，它現(xiàn)在它的左子樹是空的。所以我們就直接對他進行訪問了。訪問完了以后呢我們要遍歷以F為根的一顆二叉樹。這時候F存在左子樹。F入棧，往左走。G存在左子樹。G入棧，往左走。H沒有左子樹，所以對他進行訪問。然后往右走，但是右子樹是空。然后根據(jù)棧頂?shù)闹羔槪覀兺嘶氐紾，然后對G進行訪問。K沒有左子樹，對K進行訪問。然后往右走，沒有右子樹，又退回去，退到哪里，根據(jù)棧頂

41、指示退到F。對F進行訪問，右子樹為空，這時候，棧為空了，說明整個中序遍歷就結(jié)束了。也就是我沒有一個結(jié)點，它的右子樹還沒有遍歷。那么從這個我們指針走的過程中，發(fā)現(xiàn)一個基本操作。就是往左走入棧。有一個這樣一直往左走，入棧的基本操作。下面看到的就是這樣一個一直往左走的這樣的操作，從指針T所指的這個根結(jié)點出發(fā)，一直向左走，走到哪里呢，走到一個左子樹為空的結(jié)點，拿指向這個左子樹為空的這樣一個結(jié)點的指針返回。走的過程中呢，把那些含有左子樹的結(jié)點都入棧。那也就是說，如果我們T是空的話，就是一棵空樹，返回的NULL。如果這個T本身不空，那么我就看它左子樹是不是空。如果左子樹空，那就返回它本身了。如果左子樹不空

42、的話，那么本身這個結(jié)點的指針入棧。然后順著左指針呢，往左走。 一直走到左子樹根為空的那個結(jié)點返回。那么再有了這個向左走的基本操作以后，這樣一個二叉樹的非遞歸的算法。這個T是指向二叉樹根結(jié)點的指針。首先就是一直往左走，如果二叉樹是空，返回NULL這樣整個遍歷就結(jié)束了。否則的話，一定返回一個指針是不空的。那么就對這個指針所指的結(jié)點進行訪問。如果它右子樹結(jié)點不空，再從他右子樹的根結(jié)點出發(fā)，一直往左走。走到一個左子樹為空的結(jié)點，進行訪問。然后再從這個結(jié)點的右子樹的根出發(fā)，往左走。那如果這個結(jié)點的右子樹是空的話，那我們要看看棧是否為空。如果?？照麄€遍歷就結(jié)束了。如果棧不空的話，就從棧里退出來，退出來以后

43、，這個結(jié)點要進行訪問。然后再往右走。當(dāng)棧為空的時候呢，整個中序遍歷就結(jié)束了。前面我們介紹了二叉樹的遍歷算法，包括問題的提出，算法的遞歸描述、以及中序算法的非遞歸描述。整個遍歷呢是非常簡單的，大家主要掌握它的遞歸形式的算法。整個二叉樹的遍歷算法是二叉樹操作的一個核心。其實二叉樹的應(yīng)用呢，有很多的操作都是在二叉樹遍歷的基礎(chǔ)上進行的。下面我們就看看如何利用二叉樹的遍歷操作完成其他的一些操作的例子。第一個例子呢，是統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)。我們用先序遍歷來做。二叉樹的葉子結(jié)點呢，是左右子樹為空的度為0的結(jié)點。那么這個題呢，就是看二叉樹上有多少個葉子結(jié)點。我們首先分析一下這個問題，二叉樹基本上有三種情

44、況。1，假定二叉樹是空樹，那么葉子節(jié)點的數(shù)目肯定為零。2假定二叉樹上只有一個根結(jié)點，那這個根結(jié)點本身就是葉子結(jié)點，所以它的葉子結(jié)點數(shù)目就是1.3第三種情況就是二叉樹的結(jié)點數(shù)大于二的情況。那么這個二叉樹的葉子結(jié)點的個數(shù)，就是左子樹上葉子結(jié)點的個數(shù)和右子樹上葉子結(jié)點數(shù)之和。那我們看一下這個程序。首先 這個函數(shù)有兩個參數(shù)，現(xiàn)在統(tǒng)計以這個T指針所指的二叉樹上葉子結(jié)點的個數(shù)。個數(shù)的和呢，累加到這個count變量里面。這個變量的初值呢，等于零。如果這個二叉樹是空的話，那么就什么都不做，count還是零。第二種情況，我們說本身這個樹不空，但是左右子樹都為空，證明它是一個葉子結(jié)點，那么count數(shù)加1 。如果

45、左右不空，那么我們就遞歸調(diào)用這個函數(shù)，統(tǒng)計左子樹上葉子結(jié)點的個數(shù)，在統(tǒng)計右子樹上的葉子結(jié)點的個數(shù)，最終我們會得到整個樹的葉子結(jié)點的個數(shù)。那這個過程呢，其實就是一個遍歷操作，先遍歷左子樹，把葉子節(jié)點的個數(shù)累加上去，再遍歷右子樹，把結(jié)點的個數(shù)累加上去。我們看這樣一顆左子樹的葉子結(jié)點的計算過程。簡單的走上一邊給出統(tǒng)計二叉樹葉子結(jié)點的遍歷如果二叉樹不是葉子節(jié)點，那么它的葉子結(jié)點個數(shù)等于左子樹葉子結(jié)點個數(shù)和右子樹葉子結(jié)點的個數(shù)。這里我們要注意遞歸調(diào)用就是說對于每一個結(jié)點的操作都是相同的。第二個例子呢，我們求二叉樹的深度。同樣我們先分析一下二叉樹深度的定義。 二叉樹的深度我們定義為：葉子結(jié)點的最大的層次數(shù)

46、。反過來，我們對二叉樹的深度可以這么來看。如果二叉樹是空樹，那么它的深度就等于零。如果只有一個根結(jié)點的話，那么它的深度就是1. 假定我們這樣一棵樹，假定左子樹的深度為d1，右子樹的深度為d2.那么對于整個二叉樹來說。它的深度是不是應(yīng)該是這兩個深度的最大值加1.所以我們對于二叉樹來說呢，分析問題呢，可以用二叉樹本身遞歸的定義來分析，二叉樹是一個根結(jié)點加上兩顆子樹，那么我們求樹的深度，就可以先求子樹的深度，然后加1，就可以了，但是對于子樹呢，我們還是先求子樹的子樹深度然后加1.所以呢我們這個過程其實還是一個遞歸的過程。我們求二叉樹的深度呢，我們用后序遍歷來求，如果二叉樹是空樹，那么它的深度為零，如

47、果二叉樹不空，我們就認為它一定有一個左子樹、一定有一個右子樹，分別求它左子樹的深度和右子樹的深度。整個樹的深度呢，就是左右子樹深度的最大值，再加上1. 二叉樹的很多操作呢，都是在二叉樹遞歸定義的基礎(chǔ)上，利用遍歷來完成。你用什么樣的遍歷呢，則根據(jù)問題的性質(zhì)不同而不同。統(tǒng)計二叉樹的葉子結(jié)點的個數(shù)，我們只要用先序遍歷就可以，當(dāng)然你也可以用后序遍歷，一般我們能用先序遍歷的話，就用先序遍歷。而我們求樹的深度呢，必須在左右子樹的深度已知的基礎(chǔ)上，才能求得樹的深度。因此，必須用后序遍歷，在求得左右子樹深度的基礎(chǔ)上，最大值加1，才是樹的深度。第三個例子，就是復(fù)制二叉樹。所謂復(fù)制二叉樹，就是按照原來的二叉樹的存

48、儲結(jié)構(gòu)，我另外再生成一個二叉樹，這個二叉樹和原來的二叉樹是一模一樣的。那我們只要按照原來的二叉樹的結(jié)點呢，再生成一個。假如這個樹用二叉鏈表來表示。那么我們用指向根的一個指針就可以表示這個樹。這個根結(jié)點里面有三個域，一個數(shù)據(jù)域，一個指向左子樹，一個指向右子樹。復(fù)制操作呢，就是要我們生成一個結(jié)點，數(shù)據(jù)域相同，把原來的拷貝過來就可以了。 同樣這個復(fù)制過來的樹的左子樹要跟我們原來的樹的左子樹相同。同樣我們復(fù)制得到右子樹。那么指向這個結(jié)點的指針，就是我得到的新的二叉樹的根指針。那這個復(fù)制左子樹和右子樹的做法，和我們的樹的遍歷一樣。對于左子樹本身呢有一個數(shù)據(jù)域和左子樹右子樹的指針域。復(fù)制的最基本的操作呢，

49、是生成一個結(jié)點。這個結(jié)點的三個域由原來的結(jié)點的三個域相對而來的。對于數(shù)據(jù)域就復(fù)制值就可以了，對于指針域，我們首先得知道左右子樹的情況后，完全建立這樣一個結(jié)點。那這樣哦復(fù)制二叉樹與我們哪種遍歷類似呢? (后序遍歷)下面我們就看一下復(fù)制二叉樹的算法,首先要生成一個結(jié)點.那么一個結(jié)點有三個值,根據(jù)這三個值才能構(gòu)成一個結(jié)點.首先由系統(tǒng)生成一個空間,然后,給這個數(shù)據(jù)域賦值，將左右指針指向傳遞過來的兩個指針。然后返回指向新生成的結(jié)點指針。下面才是復(fù)制的算法，這個算法呢，也是一個遞歸的算法，在左子樹和右子樹都復(fù)制完的基礎(chǔ)上呢，我們才能生成一個這樣的結(jié)點并返回指向根結(jié)點的指針。這個算法呢，我們知道是一個后序遍

50、歷。首先我先復(fù)制左子樹，如果左子樹是空，那么左子樹指針就是空，如果我左子樹不空，我根據(jù)左子樹得到一顆二叉樹，同樣我也會得到一棵右子樹復(fù)制過來的二叉樹。最后我們得到一個根結(jié)點返回。第四個例子，建立二叉樹的存儲結(jié)構(gòu)，一般來說，我們都是建立一個二叉樹的二叉鏈表的存儲結(jié)構(gòu)。那么怎么建立二叉鏈表的存儲結(jié)構(gòu)呢。我們在將二叉樹的基本操作里面呢，我們知道二叉樹的創(chuàng)建時根據(jù)定義來創(chuàng)建的。那其實我們剛才的復(fù)制二叉樹就是建立二叉樹的一個方法。也就是說我從底下到上面，把二叉樹的根結(jié)點建立完了以后呢，整個二叉樹就算建立完了。這樣的建立，就是根據(jù)一個已有的二叉樹，建立一個二叉樹的方法，那么我們還可以根據(jù)其他的定義來建立一

51、個二叉樹的二叉鏈表。那么我們就根據(jù)幾種不同的定義來建立二叉樹的二叉鏈表方法。但是你得注意，對于給出的定義，相對的信息也必須是完備的。就是說你給出的信息，建立的必須是唯一的一棵二叉樹。而不能建立出不同的二叉樹來。第一種方法是按給定的先序序列建立二叉鏈表。對于這種情況，我們其實還是建立一個根的結(jié)點。把左子樹的根賦值給它，右子樹的根給它。那么整個二叉樹就建立完了。二叉樹我們說是有三部分構(gòu)成的，一個根結(jié)點，一個左子樹、一個右子樹。那這個二叉樹呢，可以用根結(jié)點的一個字符、加上左子樹的一個字符序列，右子樹的一個字符序列。也就是整個二叉樹呢，可以用一個字符序列來表示。第一個是根。那什么是空樹呢，我們用一個空

52、白字符來表示。那從二叉樹的一個分析呢，我們始終不要忘了對于二叉樹的空樹的一個表示。那么如果你只給一個空字符的話，一定建立了一棵空樹。那如果我給出一個A-，那么就是一個根結(jié)點，左子樹是空樹，右子樹也是空樹。也就是只含根結(jié)點的一顆二叉樹。那么我們知道如果左字數(shù)不空，那么反過來它一定有一個左子樹有一個右子樹。對于這樣一棵二叉樹我們可以用這樣一個序列來表示，一個根結(jié)點，一個左子樹的字符序列，一個右子樹的字符序列。畫出該圖，并給出字符序列的說明。特別是字符序列中，左右子樹的說明這樣的一顆二叉樹可以由這樣的字符序列來表示，反過來這樣的一個字符序列唯一確定了這樣一顆二叉樹。（解釋說明一下這個唯一性。）同樣我

53、們可以看到這個序列實際上是我們先序遍歷二叉樹的一個輸出。這樣的話，我們就可以輸入這個字符序列，從給定的先序序列建立一個二叉樹。下面我們看這個程序首先得到一個字符，如果字符不是空，那么這顆樹就不是空樹，這一個肯定是根結(jié)點的數(shù)據(jù)域的字符，然后依次建立它的左子樹根和右子樹根。建立的左子樹根，返回的指針賦給這個T的左指針域。同樣建立的右子樹返回的一個指針賦給這個節(jié)點的右指針域。這樣我們就可以得到一棵二叉樹。這個先序序列與我們前面的先序序列不一樣，這個序列加上了空格。下面我們看第五個例子，按給定的表達式建相應(yīng)二叉樹。 表達式我們在講棧的時候，給大家介紹了表達式的先綴表示、中綴表示、和后綴表示法。那么一個

54、表達式呢，它的基本的成分呢，是由兩個操作數(shù)和一個運算符構(gòu)成的。因此我們說一個表達式可以用二叉樹來表示。（畫圖）表達式=第一操作數(shù)+運算符+第二操作數(shù) 那我們很自然的就能用一個二叉樹來表示。以運算符為根結(jié)點，它的左子樹就是第一操作數(shù)，右子樹就是第二操作數(shù)。那當(dāng)這個第一操作數(shù)本身又是一個表達式的時候，那它就又是一個二叉樹。那么現(xiàn)在我們來看表達式所謂的先綴表示法，和它的后綴表示法，實際上就是對二叉樹進行先序和后序遍歷之后得到的結(jié)構(gòu)。所謂先綴表示法，我們把運算符放在前面，然后是第一操作數(shù)第二操作數(shù)。后綴呢是第一操作數(shù)，第二操作數(shù)，運算符。所以這是先序遍歷的規(guī)則，這是后續(xù)遍歷的規(guī)則。那么如果一個二叉樹夠

55、成了一個表達式，那么這顆二叉樹呢，肯定是上面沒有度為1的結(jié)點的。 比如我們這個例子（a+b）*c-d/e 我們可以用這樣的一個二叉樹來表示：每一個二元運算是一棵二叉樹，而且這顆二叉樹的節(jié)點呢，跟它的運算順序是有關(guān)的。那這個表達式的先綴表達式呢是-+abc/de 順序呢正好是我們先序遍歷二叉樹的輸出的順序-+abc/de。 那么剛才我們表示二叉樹的時候，一定要加上控制符才能表示二叉樹，而現(xiàn)在不加控制符，這樣一個表達式的先綴式，能不能唯一的確定這顆二叉樹。我們看這顆樹上的分支節(jié)點和葉子結(jié)點有什么規(guī)律？所有的操作數(shù)都在葉子節(jié)點上，而且所有的運算符都在分支結(jié)點上。而且第一個操作符呢，肯定是根結(jié)點。那么

56、我們看這個先序序列的話，這個肯定是根結(jié)點的字符。下面緊接著是它的左子樹的根，在下面是它的左子樹的根。碰到abcd的話肯定是葉子結(jié)點。那么我們看看通過這個序列能否建立一個二叉樹。也就是說我們見到字符的話，就表示是一個葉子結(jié)點，見到運算符的話，就表示有一個左子樹有一個右子樹。那這個字符序列不是空的，那么就看第一個是運算符，一定是它的根結(jié)點。左右子樹一定不空，下面我們就遞歸的建立它的左子樹，那么X一定是左子樹的根結(jié)點，表示還是一個運算符，在樹中呢，它還是一顆子樹，有左子樹和右子樹。下面是左子樹根說明它還是一棵子樹。有左子樹有右子樹，一次建立它的左子樹，這時，它的左子樹是一個操作數(shù)，表示是一個葉子結(jié)點

57、。這個結(jié)點的左右指針是空的。對于+來說左子樹建立完了，那么就改建立+的右子樹，同樣它是葉子結(jié)點，就是空。這時候整個以+為根的二叉樹建立完了。這時候就是乘的右子樹了，又是一個葉子結(jié)點。這時候的右子樹完了，后面的一定是的右子樹。因為是運算符，所以它有左子樹右子樹，左右子樹分別為dc。由于表達式我們限定的是一個二元運算符，也就是說碰到一個運算符那么它一定存在著左右子樹。碰到操作數(shù)的情況就是左右子樹都空，所以在這這種情況下，我們可以根據(jù)表達式的先綴來建立這棵二叉樹。那我們現(xiàn)在反過來，已經(jīng)知道表達式的后綴，ab+cde/- 對于這個后綴式，我們求值是很方便的，從左到右掃描，當(dāng)掃描到運算符的時候，那么就對

58、它前面緊挨著的操作數(shù)做運算。那么所謂對它做運算，在我們二叉樹里面呢，實際上就是建立一棵二叉樹?，F(xiàn)在我們又碰到了運算符了，這個乘要對前面兩個做為操作數(shù)做運算，也就是構(gòu)成了這樣一棵樹。后面我們碰到de/ 也就是相當(dāng)于構(gòu)造這棵樹，最后面呢，我們又遇到了，那么對著兩個操作數(shù)來說就又構(gòu)成了一個表達式，對應(yīng)于這樣的一顆樹。那么也就是說，由后綴式很容易求值，而且還很容易構(gòu)造一棵樹。那么如果我們給出的是一個原表達式，（a+b）*c-d/e ，希望從這個原表達式建樹，當(dāng)然你可以將原表達式轉(zhuǎn)換成后綴式然后再建樹，但是我們希望能有一個方法，直接從原表達式建樹。 而不需要變成后綴式。我們知道從原表達式到后綴表達式的過

59、程是需要一個棧，那么我們就看一看能不能利用一個棧直接將原表達式建立成一棵樹。（演示程序說明一下就可以了）。至于算法的源程序?qū)崿F(xiàn)呢，我們簡單的看一下就可以了。剛才呢，我們討論了幾種二叉樹的生成方法。一種呢，是由帶空格的先序序列。第二種我們可以由先綴，后綴得到一棵二叉樹。第三種呢，是根據(jù)表達式的原表達式建樹。對于表達式而言，我們很容易到樹，因為我們知道運算符就是一個度為二的結(jié)點。而操作數(shù)呢就是葉子結(jié)點。所以由它的先綴或是后綴呢，就很容易建立二叉樹。對于任意的二叉樹，我們必須用帶空格的先序序列來建立。那么我想問，我們對于這樣ABCD這樣的先序序列，也就是說一棵二叉樹的先序序列是ABCD，能否得到建造

60、二叉樹呢？ 當(dāng)然可以，但是這樣的二叉樹有很多，不是唯一的。我們可以畫出很多。為什么會有很多呢？我們來看一下，abcd這個序列。 首先a是根結(jié)點沒什么問題，但是對于b是a的左子樹根還是右子樹根，是不是沒有明確說明。因為如果a沒有左子樹，那么b就是它的右子樹，a如果有左子樹，那么b肯定是它的左子樹根。那么我們用這種不帶空格的先序序列是不能唯一的確定一個二叉樹的。那么我們看這棵樹的中序序列，例如左邊的這棵樹是abcd，中間的的序列是badc，右邊這棵樹的中序序列是acdb。 那么我們看這個中序遍歷的序列的特點，特點就是根結(jié)點一定在左子樹和右子樹序列的中間，但是如果只給你一個中序序列，你還是不知道哪一