樹和二叉樹的基本知識

1、精選優(yōu)質(zhì)文檔-傾情為你奉上樹和二叉樹的基本知識樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，用它能很好地描述有分支和層次特性的數(shù)據(jù)集合。樹型結(jié)構(gòu)在現(xiàn)實世界中廣泛存在，如把一個家族看作為一棵樹，樹中的結(jié)點(diǎn)為家族成員的姓名及相關(guān)信息，樹中的關(guān)系為父子關(guān)系，即父親是兒子的前驅(qū)，兒子是父親的后繼；把一個國家或一個地區(qū)的各級行政區(qū)劃分看作為一棵樹，樹中的結(jié)點(diǎn)為行政區(qū)的名稱及相關(guān)信息，樹中的關(guān)系為上下級關(guān)系，如一個城市包含有若干個區(qū)，每個區(qū)又包含有若干個街道，每個街道又包含有若干個居委會；把一本書的結(jié)構(gòu)看作是一棵樹，樹中的結(jié)點(diǎn)為書、章、節(jié)的名稱及相關(guān)信息，樹中的關(guān)系為包含關(guān)系。樹在計算機(jī)領(lǐng)域中也有廣泛應(yīng)用，如在編譯系統(tǒng)中，用

2、樹表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，樹型結(jié)構(gòu)是數(shù)據(jù)庫層次模型的基礎(chǔ)，也是各種索引和目錄的主要組織形式。在許多算法中，常用樹型結(jié)構(gòu)描述問題的求解過程、所有解的狀態(tài)和求解的對策等。在樹型結(jié)構(gòu)中，二叉樹是最常用的結(jié)構(gòu)，它的分支個數(shù)確定，又可以為空，具有良好的遞歸特性，特別適宜于程序設(shè)計，因此我們常常將一般樹型結(jié)構(gòu)轉(zhuǎn)換成二叉樹進(jìn)行處理。第一節(jié) 樹一、樹的定義一棵樹（tree）是由n（n>0）個元素組成的有限集合，其中：1每個元素稱為結(jié)點(diǎn)(node)；2有一個特定的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)或樹根（root）；3除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成m（m>=0）個互不相交的有限集合T0,T1,T2,Tm-1

3、，而每一個子集Ti又都是一棵樹（稱為原樹的子樹subtree）。圖1圖1就是一棵典型的樹結(jié)構(gòu)。從樹的定義可以看出：1樹是遞歸定義的，這就決定了樹的操作和應(yīng)用大都是采用遞歸思想來解決； 2一棵樹中至少有1個結(jié)點(diǎn)，這個結(jié)點(diǎn)就是根結(jié)點(diǎn)，如上圖中的結(jié)點(diǎn)1；3只有根結(jié)點(diǎn)沒有前趨結(jié)點(diǎn)，其余每個結(jié)點(diǎn)都有唯一的一個前趨結(jié)點(diǎn)；4所有結(jié)點(diǎn)都可以有0或多個后繼結(jié)點(diǎn)；二、樹的基本概念下面以圖1為例給出樹結(jié)構(gòu)中的一些基本概念：1一個結(jié)點(diǎn)的子樹個數(shù)，稱為這個結(jié)點(diǎn)的度（degree），如結(jié)點(diǎn)1的度為3，結(jié)點(diǎn)3的度為0。度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)（又稱樹葉leaf，如結(jié)點(diǎn)3、5、6、8、9）。度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)（如結(jié)點(diǎn)1

4、、2、4、7）。根結(jié)點(diǎn)以外的分支結(jié)點(diǎn)又稱為內(nèi)部結(jié)點(diǎn)（如結(jié)點(diǎn)2、4、7）。樹中各結(jié)點(diǎn)的度的最大值稱為這棵樹的度（又稱寬度），圖1所示這棵樹的（寬）度為3。2在用上述圖形表示的樹結(jié)構(gòu)中，對兩個用線段（稱為樹枝）連接的相關(guān)聯(lián)的結(jié)點(diǎn)，稱上端的結(jié)點(diǎn)為下端結(jié)點(diǎn)的父結(jié)點(diǎn)，稱下端的結(jié)點(diǎn)為上端結(jié)點(diǎn)的子結(jié)點(diǎn)，稱同一個父結(jié)點(diǎn)的多個子結(jié)點(diǎn)為兄弟結(jié)點(diǎn)。如結(jié)點(diǎn)1是結(jié)點(diǎn)2、3、4的父結(jié)點(diǎn)，結(jié)點(diǎn) 2、3、4都是結(jié)點(diǎn)1的子結(jié)點(diǎn)，它們又是兄弟結(jié)點(diǎn)，同時結(jié)點(diǎn)2又是結(jié)點(diǎn)5、6的父結(jié)點(diǎn)。稱從根結(jié)點(diǎn)到某個子結(jié)點(diǎn)所經(jīng)過的所有結(jié)點(diǎn)為這個子結(jié)點(diǎn)的祖先。如結(jié)點(diǎn)1、4、7是結(jié)點(diǎn)8的祖先。稱以某個結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都是該結(jié)點(diǎn)的子孫。如結(jié)點(diǎn)7

5、、8、9都是結(jié)點(diǎn)4的子孫。3定義一棵樹的根結(jié)點(diǎn)的層次（level）為1，其它結(jié)點(diǎn)的層次等于它的父結(jié)點(diǎn)的層次數(shù)加1。如結(jié)點(diǎn)2、3、4的層次為2，結(jié)點(diǎn)5、6、7的層次為3，結(jié)點(diǎn)8、9的層次為4。一棵樹中所有結(jié)點(diǎn)的層次的最大值稱為樹的深度（depth），圖1所示這棵樹的深度為4。4若樹中各結(jié)點(diǎn)的子樹是按照一定的次序從左向右安排的，它們之間的次序不能互換，這樣的樹稱之為有序樹，否則稱之為無序樹。所以，樹雖然是非線性結(jié)構(gòu)，但也是有序結(jié)構(gòu)。例如，對于下面圖2中的兩棵樹，若看作為無序樹，則是相同的；若看作為有序樹，則是不同的，因為根結(jié)點(diǎn)A的兩棵子樹的次序不同。又如對于一棵反映了父子關(guān)系的家族樹，兄弟結(jié)點(diǎn)之間

6、是按照排行大小而有序排列的，所以它是一棵有序樹。因為任何無序樹都可以當(dāng)作具有任一次序的有序樹來處理，所以下面如果不特別指明，均認(rèn)為樹是有序的。圖25.對于一棵子樹中的任意兩個不同的結(jié)點(diǎn)，如果從一個結(jié)點(diǎn)出發(fā)，按層次自上而下沿著一個個樹枝能到達(dá)另一結(jié)點(diǎn)，稱它們之間存在著一條路徑?？捎寐窂剿?jīng)過的結(jié)點(diǎn)序列表示路徑，路徑的長度等于路徑上的結(jié)點(diǎn)個數(shù)減1。如圖1中，結(jié)點(diǎn)1和結(jié)點(diǎn)8之間存在著一條路徑，并可用（1、4、7、8）表示這條路徑，該條路徑的長度為3。從根結(jié)點(diǎn)出發(fā)，到樹中的其余結(jié)點(diǎn)一定存在著一條路徑。注意，不同子樹上的結(jié)點(diǎn)之間不存在路徑。但是，如果把樹看成是一個圖的話(可以把樹理解為是圖的一個子類)，

7、那么我們就可以繼承圖的路徑的定義，認(rèn)為不同子樹上的兩個結(jié)點(diǎn)應(yīng)該是有路徑的（圖論意義上的路徑）。6森林（forest）是m(m>=0)棵互不相交的樹的集合。三、樹的表示方法和存儲結(jié)構(gòu)樹的表示方法有多種，如圖1采用的就是一種形象的樹形表示法；另外還有一種常用的表示方法“括號表示法”，它的表示方法歸納如下：先將整棵樹的根結(jié)點(diǎn)放入一對圓括號中，然后把它的子樹由左至右放入括號中，同層子樹用圓括號括在一起（同層子樹之間用逗號隔開），而對子樹也采用同樣的方法處理，直到所有的子樹都只有一個根結(jié)點(diǎn)為止。用括號表示法表示圖1的步驟如下：=（T）=（1（T1，T2 ，T3 ） A是根結(jié)點(diǎn)，有3棵子樹，用逗號隔

8、開=（1（2（T11，T12），3，4（T31） 分別對3棵子樹做同樣的操作=（1（2（5，6），3，4（7（T311，T312）=（1（2（5，6），3，4（7（8，9）實際上，以上方法是按照樹的層次逐步展開，直到所有結(jié)點(diǎn)都已列出。樹的存儲結(jié)構(gòu)也有多種形式，其中使用較多的采是鏈?zhǔn)酱鎯Y(jié)構(gòu)，下面給出幾種常見的存儲樹的數(shù)據(jù)結(jié)構(gòu)。1父親表示法：定義一個數(shù)組，每個數(shù)組元素為一個記錄，除了存放一個結(jié)點(diǎn)的數(shù)據(jù)信息外，還存放該結(jié)點(diǎn)的父結(jié)點(diǎn)編號。數(shù)據(jù)結(jié)構(gòu)定義如下：Const m=10； 樹的結(jié)點(diǎn)數(shù)Type node=Record data:Integer； 數(shù)據(jù)域 parent:Integer； 指針域 E

9、nd；Var tree:Array1.m Of node；這種方法充分利用了樹中除根結(jié)點(diǎn)外每個結(jié)點(diǎn)都有唯一的父結(jié)點(diǎn)這個性質(zhì)，很容易找到樹根（可以規(guī)定根結(jié)點(diǎn)的父結(jié)點(diǎn)為0），但找孩子時卻需要遍歷整個線性表。2孩子表示法：利用單鏈表，每個結(jié)點(diǎn)包括一個數(shù)據(jù)域和若干個指針域，每個指針都指向一個孩子結(jié)點(diǎn)。由于一般樹的各個結(jié)點(diǎn)的孩子數(shù)不確定，所以指針數(shù)應(yīng)該等于整棵樹的度。當(dāng)樹的度越大時，空指針域所占比例也越大，給存儲空間造成很大浪費(fèi)。假設(shè)樹的度為10，樹的結(jié)點(diǎn)僅存放字符，則這棵樹的數(shù)據(jù)結(jié)構(gòu)定義如下：Const m=10； 樹的度Type tree=node； node=Record data:Char； 數(shù)

10、據(jù)域 child:Array1.m Of tree 指針域，指向若干孩子結(jié)點(diǎn) End；Var t:tree；注：空間上的浪費(fèi)其實可以用“虛開實用”的方法完美地解決，在FreePascal等環(huán)境下可以用Getmem、Freemem等過程達(dá)到這個目的，這樣建立一棵普通樹的時間復(fù)雜度也是很不錯的。有興趣的同學(xué)可以參考有關(guān)書籍與程序。由于每個結(jié)點(diǎn)都只存放各自孩子結(jié)點(diǎn)的編號，所以這種方法只能從根（父）結(jié)點(diǎn)遍歷到子結(jié)點(diǎn)，不能從某個子結(jié)點(diǎn)返回到它的父結(jié)點(diǎn)。3父親孩子表示法：利用雙鏈表結(jié)構(gòu)，每個結(jié)點(diǎn)包括一個數(shù)據(jù)域和二個指針域，一個指向該結(jié)點(diǎn)的若干孩子結(jié)點(diǎn)，一個指向其父結(jié)點(diǎn)?？朔松鲜龅?種存儲方法的缺點(diǎn)，假設(shè)

11、樹的度為10，樹的結(jié)點(diǎn)僅存放字符，則這棵樹的數(shù)據(jù)結(jié)構(gòu)定義如下：Const m=10；Type tree=node； node=Record data:Char； child:Array1.m Of tree； father:treeEnd；Var t:tree；4孩子兄弟表示法：有些程序中需要對兄弟結(jié)點(diǎn)進(jìn)行處理，這種情況下，可以使用另外一種雙鏈表結(jié)構(gòu)，每個結(jié)點(diǎn)包括一個數(shù)據(jù)域和二個指針域，一個指針指向該結(jié)點(diǎn)的第一個孩子結(jié)點(diǎn)，一個指針指向該結(jié)點(diǎn)的下一個兄弟結(jié)點(diǎn)?？朔松鲜龅?種存儲方法的缺點(diǎn)，假設(shè)樹的度為10，樹的結(jié)點(diǎn)僅存放字符，則這棵樹的數(shù)據(jù)結(jié)構(gòu)定義如下：Type tree=node； node

12、=Record data:Char； firstchild,next: tree； End；Var t:tree；四、樹的遍歷在應(yīng)用樹結(jié)構(gòu)解決問題時，往往需要按照某種次序獲得樹中全部結(jié)點(diǎn)的信息，這種操作叫做“樹的遍歷”。遍歷一般按照從左向右的順序，常用的遍歷方法有：1先序（根）遍歷：先訪問根結(jié)點(diǎn)，再從左到右按照先序思想遍歷各棵子樹。圖1先序遍歷的結(jié)果為：1，2，5，6，3，4，7，8，9；2后序（根）遍歷：先從左到右遍歷各棵子樹，再訪問根結(jié)點(diǎn)。圖1后序遍歷的結(jié)果為：5，6，2，3，8，9，7，4，1；3層次遍歷：按層次從小到大逐個訪問，同一層次按照從左到右的次序。圖1層次遍歷的結(jié)果為：1，2，

13、3，4，5，6，7，8，9；4葉結(jié)點(diǎn)遍歷：有時我們把所有的數(shù)據(jù)信息都存放在葉結(jié)點(diǎn)中，而其余結(jié)點(diǎn)都是用來表示數(shù)據(jù)之間的某種分支或?qū)哟侮P(guān)系，這種情況就用這種方法。圖1按照這個思想訪問的結(jié)果為：5，6，3，8，9；很明顯，先序遍歷和后序遍歷兩種方法的定義是遞歸的，所以在程序?qū)崿F(xiàn)時往往也是采用遞歸的思想，既通常所說的“深度優(yōu)先搜索”。按照先序遍歷思想編寫的遞歸過程如下：Procedure tra1(t,m) 訪問以t為根結(jié)點(diǎn)的含有m棵子樹的過程BeginIf t <>Nil Then Begin Write(t.data, )； 訪問根結(jié)點(diǎn) For I:=1 To m Do 前序遍歷各子樹

14、tra1(t.childI,m)；End；End；也可以用堆棧的方法編寫這個程序，留給讀者作為練習(xí)。層次遍歷應(yīng)用也較多，實際上就是我們所說的“廣度優(yōu)先搜索”。思想如下：若某個結(jié)點(diǎn)被訪問，則該結(jié)點(diǎn)的子結(jié)點(diǎn)應(yīng)被記錄下來，等待被訪問。順序訪問各層次上結(jié)點(diǎn)，直至不再有未訪問過的結(jié)點(diǎn)。為此，引入一個隊列來存儲等待訪問的子結(jié)點(diǎn)，設(shè)一個隊首和隊尾指針分別表示出隊、進(jìn)隊的下標(biāo)。程序框架如下：Const n=100；Var head,tail,i:integer； q:array1.n of tree； p:tree；Begin tail:=1；head:=1； 初始化 qtail:=t；tail:=tail+

15、1； t進(jìn)隊 While ( head<tail) do Begin 隊列非空 p:=qhead；head:=head+1； 取出隊首結(jié)點(diǎn) Write(p.data, )； 訪問某結(jié)點(diǎn) For i:=1 To m Do 該結(jié)點(diǎn)的所有子結(jié)點(diǎn)按順序進(jìn)隊 If p.childi<>Nil Then Begin qtail:=p.childI；tail:=tail+1； End； End；End；例1：單詞查找樹問題描述 在進(jìn)行文法分析的時候，通常需要檢測一個單詞是否在我們的單詞列表里。為了提高查找和定位的速度，通常都畫出與單詞列表所對應(yīng)的單詞查找樹，其特點(diǎn)如下：1根結(jié)點(diǎn)不包含字母，

16、除根結(jié)點(diǎn)外每一個結(jié)點(diǎn)都僅包含一個大寫英文字母；2從根結(jié)點(diǎn)到某一結(jié)點(diǎn)，路徑上經(jīng)過的字母依次連起來所構(gòu)成的字母序列，稱為該結(jié)點(diǎn)對應(yīng)的單詞。單詞列表中的每個單詞，都是該單詞查找樹某個結(jié)點(diǎn)所對應(yīng)的單詞；3在滿足上述條件下，該單詞查找樹的結(jié)點(diǎn)數(shù)最少。4例如圖3左邊的單詞列表就對應(yīng)于右邊的單詞查找樹。注意，對一個確定的單詞列表，請統(tǒng)計對應(yīng)的單詞查找樹的結(jié)點(diǎn)數(shù)（包含根結(jié)點(diǎn)）。問題輸入 輸入文件名為word.in，該文件為一個單詞列表，每一行僅包含一個單詞和一個換行/回車符。每個單詞僅由大寫的英文字母組成，長度不超過63個字母 。文件總長度不超過32K，至少有一行數(shù)據(jù)。問題輸出 輸出文件名為word.out，

17、該文件中僅包含一個整數(shù)，該整數(shù)為單詞列表對應(yīng)的單詞查找樹的結(jié)點(diǎn)數(shù)。 樣例輸入 AANASPASASCASCIIBASBASIC 樣例輸出 13 圖3算法分析首先要對建樹的過程有一個了解。對于當(dāng)前被處理的單詞和當(dāng)前樹：在根結(jié)點(diǎn)的子結(jié)點(diǎn)中找單詞的第一位字母，若存在則進(jìn)而在該結(jié)點(diǎn)的子結(jié)點(diǎn)中尋找第二位如此下去直到單詞結(jié)束，即不需要在該樹中添加結(jié)點(diǎn)；或單詞的第n位不能被找到，即將單詞的第n位及其后的字母依次加入單詞查找樹中去。但，本問題只是問你結(jié)點(diǎn)總數(shù)，而非建樹方案，且有32K文件，所以應(yīng)該考慮能不能通過不建樹就直接算出結(jié)點(diǎn)數(shù)？為了說明問題的本質(zhì)，我們給出一個定義：一個單詞相對于另一個單詞的差：設(shè)單詞1

18、的長度為L，且與單詞2從第N位開始不一致，則說單詞1相對于單詞2的差為L-N+1，這是描述單詞相似程度的量?？梢?，將一個單詞加入單詞樹的時候，須加入的結(jié)點(diǎn)數(shù)等于該單詞樹中已有單詞的差的最小值。單詞的字典順序排列后的序列則具有類似的特性，即在一個字典順序序列中，第m個單詞相對于第m-1個單詞的差必定是它對于前m-1個單詞的差中最小的。于是，得出建樹的等效算法： 讀入文件； 對單詞列表進(jìn)行字典順序排序； 依次計算每個單詞對前一單詞的差，并把差累加起來。注意：第一個單詞相對于“空”的差為該單詞的長度； 累加和再加上1（根結(jié)點(diǎn)），輸出結(jié)果。就給定的樣例，按照這個算法求結(jié)點(diǎn)數(shù)的過程如下表：表1原單詞列表

19、排序后的列表差值總計輸出AA11213ANAN1ASPAS1ASASC1ASCASCII2ASCIIASP1BASBAS3BASICBASIC2數(shù)據(jù)結(jié)構(gòu) 先確定32K（32*1024=32768字節(jié)）的文件最多有多少單詞和字母。當(dāng)然應(yīng)該盡可能地存放較短的單詞。因為單詞不重復(fù)，所以長度為1的單詞（單個字母）最多26個；長度為2的單詞最多為26*26=676個；因為每個單詞后都要一個換行符（換行符在計算機(jī)中占2個字節(jié)），所以總共已經(jīng)占用的空間為：（1+2）*26+（2+2）*676=2782字節(jié)；剩余字節(jié)（32768-2782=29986字節(jié)）分配給長度為3的單詞（長度為3的單詞最多有 26*26

20、*26=17576個）有29986/（3+2）5997。所以單詞數(shù)量最多為26+676+5997=6699。定義一個數(shù)組：a：array1.32767 of char；把所有單詞連續(xù)存放起來，文件中每個單詞后的換行符轉(zhuǎn)換成數(shù)組中的一個“空格”字符。這樣既省略了一個存放單詞長度的數(shù)組，又方便且節(jié)省了一點(diǎn)空間。另外為了排序，再設(shè)一個數(shù)組index:array1. 6700 of integer；存放每個單詞在a中的起始位置。這樣，排序時用a比較，但只要交換index的值就可以了。參考程序Program p1(Input, Output)；Var a:Array1.32767 Of Char； in

21、dex:Array1.6700 Of Integer； n,k,i,j,tot,t:Integer； s,pre,now:String；Function cmp(i, j:Longint):Boolean；比較從ai開始的字符串和從aj開始的字符串Begin 大小，小于則返回False，否則返回True While (ai=aj) And (Ord(ai)<>32) And (Ord(aj)<>32) Do Begin Inc(i)；Inc(j)；End； If (ai<aj) Then cmp := False Else cmp := True；End；Begi

22、n main Assign(Input,'word.in')； Reset(Input)； Assign(Output,'word.out')；Rewrite(Output)； Fillchar(a, sizeof(a), 0)； n := 0；單詞個數(shù) k := 0；下標(biāo) While (Not Eof) Do 讀入文件中的單詞并且存儲到數(shù)組中 Begin Readln(s)； n := n+1； indexn := k+1；第n個單詞的首字母起點(diǎn)下標(biāo) For i:=1 To Length(s) Do 存入一個單詞 ak+i := si； k := k+i+1；

23、 為下個單詞的下標(biāo)設(shè)定好初值,i即為當(dāng)前單詞的長度 End； For i:=1 To n Do n個單詞的字典排序 For j:=i+1 To n Do If cmp(indexi, indexj) Then Begin t := indexi；indexi := indexj；indexj := t；End； tot := 0； 計數(shù)器 pre := ''； 前一個單詞 For i:=1 To n Do 統(tǒng)計 Begin now := ''； j := indexi； 第i個單詞的首字母在a數(shù)組中的下標(biāo)為j While (Ord(aj)<>0) D

24、o 換行符換成了空格 Begin now := now + aj；j := j+1；End； 當(dāng)前處理的單詞存入now中 j := 1； While (prej=nowj) And (j<=length(pre) Do Inc(j)；求兩個單詞的差 tot := tot+(Length(now)-j+1)； 累加 pre := now；把當(dāng)前單詞作為下次比較的前一個單詞 End； Writeln(tot+1)； Close(Input)；Close(Output)；End.第二節(jié) 二叉樹一、二叉樹的概念二叉樹（binary tree,簡寫成BT）是一種特殊的樹型結(jié)構(gòu)，它的特點(diǎn)是每個結(jié)點(diǎn)至

25、多只有二棵子樹，即二叉樹中不存在度大于2的結(jié)點(diǎn)，而且二叉樹的子樹有左子樹、右子樹之分，孩子有左孩子、右孩子之分，其次序不能顛倒，所以二叉樹是一棵有序樹。它有如下5種基本形態(tài)：圖4第一節(jié)講述的樹的一些術(shù)語、概念也基本適用于二叉樹，但二叉樹與樹也有很多不同，如：二叉樹的每個結(jié)點(diǎn)至多只能有兩個結(jié)點(diǎn)，二叉樹一定是有序的，二叉樹可以為空（但樹不能為空，至少要有1個結(jié)點(diǎn)）。二、二叉樹的性質(zhì)：性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點(diǎn)（i>=1）。性質(zhì)2：深度為k的二叉樹至多有2k 1個結(jié)點(diǎn)（k>=1）。特別地，一棵深度為k且有2k 1個結(jié)點(diǎn)的二叉樹稱為滿二叉樹。圖5是深度為4的滿二叉樹，這

26、種樹的特點(diǎn)是每層上的結(jié)點(diǎn)數(shù)都達(dá)到了最大值。圖5可以對滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號，約定編號從根結(jié)點(diǎn)起，自上而下，從左到右，由此引出完全二叉樹的定義：深度為k，有n個結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1到n的結(jié)點(diǎn)一一對應(yīng)時，稱為完全二叉樹。 如圖6就是一個深度為4，結(jié)點(diǎn)數(shù)為12的完全二叉樹。圖6完全二叉樹具有如下特征：葉結(jié)點(diǎn)只可能出現(xiàn)在最下面兩層上；對任一結(jié)點(diǎn)，若其右子樹深度為m，則其左子樹的深度必為m或m+1。圖7和圖8所示的兩棵二叉樹就不是完全二叉樹，請讀者思考為什么？ 圖7 圖8性質(zhì)3：對任何一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則一定滿足：n0

27、=n2+1。性質(zhì)4：具有n個結(jié)點(diǎn)的完全二叉樹的深度為trunc(LOG2n)+1 （trunc為取整函數(shù)）性質(zhì)5：一棵n個結(jié)點(diǎn)的完全二叉樹，對于任一編號為i結(jié)點(diǎn)，有：1如果i=1,則結(jié)點(diǎn)i為根，無父結(jié)點(diǎn)；如果i>1,則其父結(jié)點(diǎn)編號為trunc(i/2)。2如果2*i>n，則結(jié)點(diǎn)i為葉結(jié)點(diǎn)；否則左孩子編號為2*i。3如果2*i+1>n，則結(jié)點(diǎn)i無右孩子；否則右孩子編號為2*i+1。三、 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)與普通樹的存儲結(jié)構(gòu)基本相同，有鏈?zhǔn)胶晚樞虼鎯煞N方法。1鏈?zhǔn)酱鎯Y(jié)構(gòu):單鏈表結(jié)構(gòu)或雙鏈表結(jié)構(gòu)，基本數(shù)據(jù)結(jié)構(gòu)定義如下：Type tree=node； 單鏈表結(jié)構(gòu) n

28、ode=Record data:Char； 數(shù)據(jù)域 lchild,rchild:tree 指針域：分別指向左、右孩子 End；Var bt:tree；Type tree=node； 雙鏈表結(jié)構(gòu) node=Record data:Char； 數(shù)據(jù)域 lchild,rchild,father:tree 指針域：分別指向左、右孩子及父結(jié)點(diǎn) End；Var bt:tree；如圖9左邊所示的一棵二叉樹用單鏈表就可以表示成右邊的形式。 bt圖92順序存儲結(jié)構(gòu):即幾個數(shù)組加一個指針變量，一般用在滿二叉樹和完全二叉樹中，將每個結(jié)點(diǎn)編號后作為數(shù)組的下標(biāo)變量值，基本數(shù)據(jù)結(jié)構(gòu)定義如下：Const n=10； 最多1

29、0個結(jié)點(diǎn)Var data:Array1.n Of Char； n個結(jié)點(diǎn)的數(shù)據(jù)域 lchild:Array1.n Of Integer； n個結(jié)點(diǎn)的左孩子 rchild:Array1.n Of Integer； n個結(jié)點(diǎn)的右孩子 bt:Integer； 根結(jié)點(diǎn)指針這種結(jié)構(gòu)可以很方便地從根結(jié)點(diǎn)往下遍歷，但是如果想從某個分支結(jié)點(diǎn)或葉結(jié)點(diǎn)遍歷整棵樹，則還需設(shè)置一個父結(jié)點(diǎn)數(shù)組，操作也教麻煩。其實如果樹的結(jié)點(diǎn)較少，也可采用鄰接矩陣的方法，這樣操作起來也很方便。二叉樹在處理表達(dá)式時經(jīng)常用到，一般用葉結(jié)點(diǎn)表示運(yùn)算數(shù)，分支結(jié)點(diǎn)表示運(yùn)算符。這樣的二叉樹稱為表達(dá)式樹，如表達(dá)式（a+b/c）*(d-e)就可以表示成圖

30、10。 bt 圖10例2：醫(yī)院設(shè)置 問題描述 設(shè)有一棵二叉樹（如圖11），其中圈中的數(shù)字表示結(jié)點(diǎn)中居民的人口，圈邊上數(shù)字表示結(jié)點(diǎn)編號?，F(xiàn)在要求在某個結(jié)點(diǎn)上建立一個醫(yī)院，使所有居民所走的路程之和為最小，同時約定，相鄰接點(diǎn)之間的距離為1。就本圖而言，若醫(yī)院建在1處，則距離和=4+12+2*20+2*40=136；若醫(yī)院建在3處，則距離和=4*2+13+20+40=81輸入格式 輸入文件名為hospital.in，其中第一行一個整數(shù)n，表示樹的結(jié)點(diǎn)數(shù)（n<=100）。接下來的n行每行描述了一個結(jié)點(diǎn)的狀況，包含三個整數(shù)，整數(shù)之間用空格（一個或多個）分隔，其中：第一個數(shù)為居民人口數(shù)；第二個數(shù)為左鏈

31、接，為0表示無鏈接；第三個數(shù)為右鏈接。輸出格式 輸出文件名為hospital.out，該文件只有一個整數(shù)，表示最小距離和。 樣例輸入513 2 34 0 012 4 520 0 040 0 0樣例輸出81問題分析 這是一道簡單的二叉樹應(yīng)用問題，問題中的結(jié)點(diǎn)數(shù)并不多，數(shù)據(jù)規(guī)模也不大，采用鄰接矩陣存儲，用Floyed法求出任意兩結(jié)點(diǎn)之間的最短路徑長，然后窮舉醫(yī)院可能建立的n個結(jié)點(diǎn)位置，找出一個最小距離的位置即可。當(dāng)然也可以用雙鏈表結(jié)構(gòu)或帶父結(jié)點(diǎn)信息的數(shù)組存儲結(jié)構(gòu)來解決，但實際操作稍微麻煩了一點(diǎn)。參考程序Program p2(Input, Output)；Var a : Array 1.100 Of

32、 Longint； g : Array 1.100, 1.100 Of Longint； n, i, j, k, l, r, min, total : Longint；Begin Assign(Input, 'hospital.in')； Reset(Input)；Assign(Output, 'hospital.in')； Rewrite(Output)； Readln(n)； For i := 1 To n Do 圖11 For j := 1 To n Do gij := ； For i := 1 To n Do 讀入、初始化 Begin gii := 0；

33、 Readln(ai, l, r)； If l > 0 Then Begin gil := 1；gli := 1 End； If r > 0 Then Begin gir := 1；gri := 1 End； End； For k := 1 To n Do 用Floyed法求任意兩結(jié)點(diǎn)之間的最短路徑長 For i := 1 To n Do If i <> k Then For j := 1 To n Do If (i <> j) And (k <> j) And (gik + gkj < gij) Then gij := gik + gkj

34、； min := Maxlongint； For i := 1 To n Do 窮舉醫(yī)院建在N個結(jié)點(diǎn)，找出最短距離 Begin total := 0； For j := 1 To n Do Inc(total, gij * aj)； If total < min Then min := total； End； Writeln(min)；Close(Input)；Close(Output)；End.后記 在各種競賽中經(jīng)常遇到這樣的問題：N-1條公路連接著N個城市，從每個城市出發(fā)都可以通過公路到達(dá)其它任意的城市。每個城市里面都有一定數(shù)量的居民，但是數(shù)量并不一定相等，每條公路的長度也不一定相等

35、。X公司（或者是政府）決定在某一個城市建立一個醫(yī)院/酒廠/游樂場，問：將它建在哪里，可以使得所有的居民移動到那里的總耗費(fèi)最??？這種題目都是本題的“變型”，一般稱為“樹的中心點(diǎn)問題”。除了簡單的窮舉法外，還有更好的時間復(fù)雜度為O(n)的算法，我們講在后面的章節(jié)中繼續(xù)討論。四、普通樹轉(zhuǎn)換成二叉樹由于二叉樹是有序的，而且操作和應(yīng)用更廣泛，所以在實際使用時，我們經(jīng)常把普通樹轉(zhuǎn)換成二叉樹進(jìn)行操作。如何轉(zhuǎn)換呢？一般方法如下：1將樹中每個結(jié)點(diǎn)除了最左邊的一個分支保留外，其余分支都去掉；2從最左邊結(jié)點(diǎn)開始畫一條線，把同一層上的兄弟結(jié)點(diǎn)都連起來；3以整棵樹的根結(jié)點(diǎn)為軸心，將整棵樹順時針大致旋轉(zhuǎn)45度。第一節(jié)中的

36、圖1所示的普通樹轉(zhuǎn)換成二叉樹的過程如圖12所示：圖12同樣我們可以把森林也轉(zhuǎn)換成二叉樹處理，假設(shè)F=T1，T2，Tm是森林，則可按如下規(guī)則轉(zhuǎn)換成一棵二叉樹B=(root,lb,rb)。1若F為空，即m=0，則 B為空樹；2若F非空，即m<>0，則B的根root即為森林中第一棵樹的根root(T1)；B的左子樹lb是從T1中根結(jié)點(diǎn)的子樹森林F1=T11，T12，T1m1轉(zhuǎn)換而成的二叉樹；其右子樹rb是從森林F =T2，T3，Tm轉(zhuǎn)換而成的二叉樹。五、二叉樹的遍歷在二叉樹的應(yīng)用中，常常要求在樹中查找具有某種特征的結(jié)點(diǎn)，或者對全部結(jié)點(diǎn)逐一進(jìn)行某種處理,這就是二叉樹的遍歷問題。所謂二叉樹的

37、遍歷是指按一定的規(guī)律和次序訪問樹中的各個結(jié)點(diǎn)，而且每個結(jié)點(diǎn)僅被訪問一次?！霸L問”的含義很廣，可以是對結(jié)點(diǎn)作各種處理，如輸出結(jié)點(diǎn)的信息等。遍歷方法共有3種：先序（根）遍歷，中序（根）遍歷， 圖13后序（根）遍歷。下面以圖13所示的二叉樹為例分別講解這3種方法。1先序遍歷的操作定義如下： 若二叉樹為空，則空操作，否則 訪問根結(jié)點(diǎn) 先序遍歷左子樹 先序遍歷右子樹很明顯，這是一種遞歸定義，下面給出一種手工方法（括號法）求先序遍歷的結(jié)果。=1，2，3，4，5，6，7，8，9 所有結(jié)點(diǎn)=1，2，4，5，7，3，6，8，9 按先序思想遍歷，將根結(jié)點(diǎn)單獨(dú)列出，左右子樹分別用括號括起來=1，2，4，7，5，3，

38、6，8，9 再對以2、3結(jié)點(diǎn)為根的樹先序遍歷=1，2，4，7，5，3，6，8，9 再對以4、5、6結(jié)點(diǎn)為根的樹先序遍歷，遇到無左、右子樹的情況就用一對空括號，遇到葉子結(jié)點(diǎn)就脫到本層括號，遇到空括號就省略=1，2，4，7，5，3，6，8，9 去掉內(nèi)層所有括號，得到結(jié)果2中序遍歷的操作定義如下：若二叉樹為空，則空操作，否則 中序遍歷左子樹 訪問根結(jié)點(diǎn) 中序遍歷右子樹可以根據(jù)以上方法，得出上圖中序遍歷的結(jié)果為：7，4，2，5，1，3，8，6，93后序遍歷的操作定義如下：若二叉樹為空，則空操作，否則 后序遍歷左子樹 后序遍歷右子樹 訪問根結(jié)點(diǎn)可以根據(jù)以上方法，得出上圖后序遍歷的結(jié)果為：7，4，5，2，

39、8，9，6，3，1顯然，以上3種遍歷方法都是采用遞歸的思想，下面以先序遍歷為例給出遞歸算法：Procedure preorder(bt:tree)；先序遍歷根結(jié)點(diǎn)為bt的二叉樹的遞歸算法Begin If bt<>Nil Then BeginWrite(bt.data)；preorder(bt.lchild)；preorder(bt.rchild)； End；End；我們也可以把遞歸過程改成用棧實現(xiàn)的非遞歸過程，下面給出先序遍歷的非遞歸過程。Procedure inorder(bt:tree)； 先序遍歷bt所指的二叉樹 Var stack:Array1.n Of tree； 棧to

40、p:integer； 棧頂指針p:tree；Begintop:=0；While Not (bt=Nil)And(top=0) DoBegin While bt<>Nil Do Begin 非葉結(jié)點(diǎn)Write(bt.data)； 訪問根top:=top+1； 右子樹壓棧stacktop:=bt.rchild；bt:=bt.lchild； 遍歷左子樹End；If top<>0 Then Begin 棧中所有元素出棧，遍歷完畢 b:=stacktop；top:=top-1； End； End； End；關(guān)于前面講的表達(dá)式樹，我們可以分別用先序、中序、后序的遍歷方法得出完全不同

41、的遍歷結(jié)果，對于圖14采用三種遍歷后的結(jié)果如下，它們正好對應(yīng)著表達(dá)式的三種表示方法： -+a*b-cd/ef (前綴表示、波蘭式)a+b*c-d-e/f (中綴表示、代數(shù)式)abcd-*+ef/- (后綴表示、逆波蘭式) 圖14六、二叉樹的其它重要操作：除了“遍歷”以外，二叉樹的其它重要操作還有：建立一棵二叉樹、插入一個結(jié)點(diǎn)到二叉樹中、刪除結(jié)點(diǎn)或子樹等，下面分別給出基本算法框架。1建立一棵二叉樹Procedure pre_crt(Var bt:tree)；按先序次序輸入二叉樹中結(jié)點(diǎn)的值，Begin 生成二叉樹的單鏈表存儲結(jié)構(gòu) Read(ch)； If ch= Then bt:=Nil 表示空樹

42、 Else Begin New(bt)； 建根結(jié)點(diǎn) bt.data:=ch； pre_crt(bt.lchild)； 建左子樹 pre_crt(bt.rchild)； 建右子樹 End；End； 2刪除二叉樹Procedure dis(Var bt:tree)； Begin If bt<>Nil Then BeginDis(bt.lchild)； 刪左子樹Dis(bt.rchild)； 刪右子樹Dispose(bt)； 釋放父結(jié)點(diǎn) End；End；3插入一個結(jié)點(diǎn)到二叉樹中Procedure insert(Var bt:tree；n:Integer)； Begin If bt=Nil

43、 Then Begin 空樹，則為根結(jié)點(diǎn)New(bt)； bt.data:=n； bt.lchild:=Nil；bt.rchild:=Nil； End Else If n<bt.data Then insert(bt.lchild,n) <，左 Else If n>bt.data Then insert(bt.rchild,n)； >，右End；4在二叉樹中查找一個數(shù)，找到返回該結(jié)點(diǎn),否則返回nilFunction find(bt:tree；n:Integer):tree； Begin If bt=Nil Then find:=Nil Else If n<bt.d

44、ata Then find(bt.lchild,n)Else If n>bt.data Then find(bt.rchild,n) Else find:=bt；End；5用嵌套括號表示法輸出二叉樹Procedure print(bt:tree)；Begin If bt<>Nil Then BeginWrite(bt.data)；If (bt.lchild<>nil) Or (bt.rchild<>nil) Then Begin Write()；print(bt.lchild)； If bt.rchild<>Nil Then Write(,

45、)； print(bt.rchild)；Write()； End； End；End；七、二叉樹的計數(shù)問題在實際應(yīng)用中經(jīng)常需要求“具有n個結(jié)點(diǎn)的不同形態(tài)的二叉樹有多少棵？具有n個結(jié)點(diǎn)的不同形態(tài)的樹有多少棵？”要解決上述問題，首先要了解下面兩個概念：“相似二叉樹”是指兩者都為空樹或者兩者均不為空樹，且它們的左右子樹分別相似?！暗葍r二叉樹”是指兩者不僅相似，而且所有對應(yīng)結(jié)點(diǎn)上的數(shù)據(jù)元素均相同。二叉樹的計數(shù)問題就是討論具有n個結(jié)點(diǎn)、互不相似的二叉樹的數(shù)目Bn。在n很小時，很容易得出，B0=1，B1=1，B2=2，B3=5（見圖15）。圖15一般情況，一棵具有n(n>0)個結(jié)點(diǎn)的二叉樹可以看成是由一個根結(jié)點(diǎn)、一棵具有i個