第3章第1-2節(jié)樹及二叉樹(C++版)

1、第一二節(jié)第一二節(jié) 樹及二叉樹樹及二叉樹簡介簡介 樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，用它能很好地描述有分支和層次特性的數(shù)據(jù)集合。樹型結(jié)構(gòu)在現(xiàn)實世界中廣泛存在，如社會組織機構(gòu)的組織關(guān)系圖就可以用樹型結(jié)構(gòu)來表示。樹在計算機領(lǐng)域中也有廣泛應(yīng)用，如在編譯系統(tǒng)中，用樹表示源程序的語法結(jié)構(gòu)。在數(shù)據(jù)庫系統(tǒng)中，樹型結(jié)構(gòu)是數(shù)據(jù)庫層次模型的基礎(chǔ)，也是各種索引和目錄的主要組織形式。在許多算法中，常用樹型結(jié)構(gòu)描述問題的求解過程、所有解的狀態(tài)和求解的對策等。在這些年的國內(nèi)、國際信息學(xué)奧賽、大學(xué)生程序設(shè)計比賽等競賽中，樹型結(jié)構(gòu)成為參賽者必備的知識之一，尤其是建立在樹型結(jié)構(gòu)基礎(chǔ)之上的搜索算法。 在樹型結(jié)構(gòu)中，二叉樹是最常用的結(jié)構(gòu)，它

2、的分支個數(shù)確定、又可以為空、并有良好的遞歸特性，特別適宜于程序設(shè)計，因此也常常將一般樹轉(zhuǎn)換成二叉樹進行處理。第一節(jié)第一節(jié) 樹的概念樹的概念-樹的定義樹的定義一棵樹是由n（n0）個元素組成的有限集合，其中：（1）每個元素稱為結(jié)點(node)；（2）有一個特定的結(jié)點，稱為根結(jié)點或樹根（root）；（3）除根結(jié)點外，其余結(jié)點能分成m（m=0）個互不相交的有限集合T0,T1,T2,Tm-1。其中的每個子集又都是一棵樹，這些集合稱為這棵樹的子樹。如下圖是一棵典型的樹：樹的基本概念樹的基本概念A(yù). 樹是遞歸定義的；B. 一棵樹中至少有1個結(jié)點。這個結(jié)點就是根結(jié)點，它沒有前驅(qū)，其余每個結(jié)點都有唯一的一個前驅(qū)

3、結(jié)點。每個結(jié)點可以有0或多個后繼結(jié)點。因此樹雖然是非線性結(jié)構(gòu)，但也是有序結(jié)構(gòu)。至于前驅(qū)后繼結(jié)點是哪個，還要看樹的遍歷方法，我們將在后面討論；C. 一個結(jié)點的子樹個數(shù)，稱為這個結(jié)點的度（degree，結(jié)點1的度為3，結(jié)點3的度為0）；度為0的結(jié)點稱為葉結(jié)點（樹葉leaf，如結(jié)點3、5、6、8、9）；度不為0的結(jié)點稱為分支結(jié)點（如結(jié)點1、2、4、7）；根以外的分支結(jié)點又稱為內(nèi)部結(jié)點（結(jié)點2、4、7）；樹中各結(jié)點的度的最大值稱為這棵樹的度（這棵樹的度為3）。D. 在用圖形表示的樹型結(jié)構(gòu)中，對兩個用線段（稱為樹枝）連接的相關(guān)聯(lián)的結(jié)點，稱上端結(jié)點為下端結(jié)點的父結(jié)點，稱下端結(jié)點為上端結(jié)點的子結(jié)點。稱同一個

4、父結(jié)點的多個子結(jié)點為兄弟結(jié)點。如結(jié)點1是結(jié)點2、3、4的父結(jié)點，結(jié)點 2、3、4是結(jié)點1的子結(jié)點，它們又是兄弟結(jié)點，同時結(jié)點2又是結(jié)點5、6的父結(jié)點。稱從根結(jié)點到某個子結(jié)點所經(jīng)過的所有結(jié)點為這個子結(jié)點的祖先。如結(jié)點1、4、7是結(jié)點8的祖先。稱以某個結(jié)點為根的子樹中的任一結(jié)點都是該結(jié)點的子孫。如結(jié)點7、8、9都是結(jié)點4的子孫。 E.定義一棵樹的根結(jié)點的層次（level）為1，其它結(jié)點的層次等于它的父結(jié)點層次加1。如結(jié)點2、3、4的層次為1，結(jié)點5、6、7的層次為2，結(jié)點8、9的層次為3。一棵樹中所有的結(jié)點的層次的最大值稱為樹的深度（depth）。如這棵樹的深度為3。 F.對于樹中任意兩個不同的結(jié)

5、點，如果從一個結(jié)點出發(fā)，自上而下沿著樹中連著結(jié)點的線段能到達另一結(jié)點，稱它們之間存在著一條路徑。可用路徑所經(jīng)過的結(jié)點序列表示路徑，路徑的長度等于路徑上的結(jié)點個數(shù)減1。如上圖中，結(jié)點1和結(jié)點8之間存在著一條路徑，并可用（1、4、7、8）表示這條路徑，該條路徑的長度為3。注意，不同子樹上的結(jié)點之間不存在路徑，從根結(jié)點出發(fā)，到樹中的其余結(jié)點一定存在著一條路徑。 G.森林（forest）是m(m=0)棵互不相交的樹的集合。樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)方法1：數(shù)組，稱為“父親表示法”。const int m = 10; /樹的結(jié)點數(shù)struct node int data, parent; /數(shù)據(jù)域，指針域

6、;node treem;優(yōu)缺點：利用了樹中除根結(jié)點外每個結(jié)點都有唯一的父結(jié)點這個性質(zhì)。很容易找到樹根，但找孩子時需要遍歷整個線性表。 方法2：樹型單鏈表結(jié)構(gòu)，稱為“孩子表示法”。每個結(jié)點包括一個數(shù)據(jù)域和一個指針域（指向若干子結(jié)點）。稱為“孩子表示法”。假設(shè)樹的度為10，樹的結(jié)點僅存放字符，則這棵樹的數(shù)據(jù)結(jié)構(gòu)定義如下：const int m = 10; /樹的度typedef struct node;typedef node *tree;struct node char data; /數(shù)據(jù)域 tree childm; /指針域，指向若干孩子結(jié)點;tree t; 缺陷：只能從根（父）結(jié)點遍歷到子結(jié)

7、點，不能從某個子結(jié)點返回到它的父結(jié)點。但程序中確實需要從某個結(jié)點返回到它的父結(jié)點時，就需要在結(jié)點中多定義一個指針變量存放其父結(jié)點的信息。這種結(jié)構(gòu)又叫帶逆序的樹型結(jié)構(gòu)。方法3：樹型雙鏈表結(jié)構(gòu)，稱為“父親孩子表示法”。每個結(jié)點包括一個數(shù)據(jù)域和二個指針域（一個指向若干子結(jié)點，一個指向父結(jié)點）。假設(shè)樹的度為10，樹的結(jié)點僅存放字符，則這棵樹的數(shù)據(jù)結(jié)構(gòu)定義如下：const int m = 10; /樹的度typedef struct node;typedef node *tree; /聲明tree是指向node的指針類型struct node char data; /數(shù)據(jù)域 tree childm; /

8、指針域，指向若干孩子結(jié)點 tree father; /指針域，指向父親結(jié)點;tree t;方法4：二叉樹型表示法，稱為“孩子兄弟表示法”。也是一種雙鏈表結(jié)構(gòu)，但每個結(jié)點包括一個數(shù)據(jù)域和二個指針域（一個指向該結(jié)點的第一個孩子結(jié)點，一個指向該結(jié)點的下一個兄弟結(jié)點）。稱為“孩子兄弟表示法”。假設(shè)樹的度為10，樹的結(jié)點僅存放字符，則這棵樹的數(shù)據(jù)結(jié)構(gòu)定義如下：typedef struct node;typedef node *tree;struct node char data; /數(shù)據(jù)域 tree firstchild, next; /指針域，分別指向第一個孩子結(jié)點和下一個兄弟結(jié)點;tree t;【例

9、3-1】找樹根和孩子【問題描述】給定一棵樹，輸出樹的根root，孩子最多的結(jié)點max以及他的孩子【輸入格式】第一行：n（結(jié)點數(shù)=100），m（邊數(shù)=200）。 以下m行；每行兩個結(jié)點x和y， 表示y是x的孩子(x,y=1000)?！据敵龈袷健康谝恍校簶涓簉oot。 第二行：孩子最多的結(jié)點max。 第三行：max的孩子?！据斎霕永? 74 14 21 31 52 62 72 8【輸出樣例】42 6 7 8【參考程序】#includeusing namespace std;int n,m,tree101=0;int main() int i,x,y,root,maxroot,sum=0,j,M

10、ax=0; cinnm; for(i=1;ixy; treey=x; for(i=1;i=n;i+) /找出樹根 if(treei=0) root=i;break; for(i=1;i=n;i+) /找孩子最多的結(jié)點 sum=0; for(j=1;jMax) Max=sum;maxroot=i; coutrootendlmaxrootendl; for(i=1;i=n;i+) if(treei=maxroot) couti ; return 0; 樹的遍歷樹的遍歷 在應(yīng)用樹結(jié)構(gòu)解決問題時，往往要求按照某種次序獲得樹中全部結(jié)點的信息，這種操作叫作樹的遍歷。遍歷的方法有多種，常用的有：A、先序（根

11、）遍歷：先訪問根結(jié)點，再從左到右按照先序思想遍歷 各棵子樹。如上圖先序遍歷的結(jié)果為：125634789；B、后序（根）遍歷：先從左到右遍歷各棵子樹，再訪問根結(jié)點。如上圖后序遍歷的結(jié)果為：562389741；C、層次遍歷：按層次從小到大逐個訪問，同一層次按照從左到右的次序。如上圖層次遍歷的結(jié)果為：123456789；D、葉結(jié)點遍歷：有時把所有的數(shù)據(jù)信息都存放在葉結(jié)點中，而其余結(jié)點都是用來表示數(shù)據(jù)之間的某種分支或?qū)哟侮P(guān)系，這種情況就用這種方法。如上圖按照這個思想訪問的結(jié)果為：56389； 大家可以看出，AB兩種方法的定義是遞歸的，所以在程序?qū)崿F(xiàn)時往往也是采用遞歸的思想。既通常所說的“深度優(yōu)先搜索”

12、。如用先序遍歷編寫的過程如下：void tral(tree t, int m) If (t) cout data endl; for(int i = 0 ; i childi, m); C方法應(yīng)用也較多，實際上是我們講的“廣度優(yōu)先搜索”。思想如下：若某個結(jié)點被訪問，則該結(jié)點的子結(jié)點應(yīng)記錄，等待被訪問。順序訪問各層次上結(jié)點，直至不再有未訪問過的結(jié)點。為此，引入一個隊列來存儲等待訪問的子結(jié)點，設(shè)一個隊首和隊尾指針分別表示出隊、進隊的下標(biāo)。程序框架如下：const int n = 100;int head, tail, i;tree qn;tree p;void work() tail = head

13、 = 1; qtail = t; tail+; /隊尾為空 while(head tail) p = qhead; head+; cout data ; for(i = 0 ; i childi) qtail = p-childi; tail+; 【例3-2】單詞查找樹【問題描述】 在進行文法分析的時候，通常需要檢測一個單詞是否在我們的單詞列表里。為了提高查找和定位的速度，通常都畫出與單詞列表所對應(yīng)的單詞查找樹，其特點如下：1根結(jié)點不包含字母，除根結(jié)點外每一個結(jié)點都僅包含一個大寫英文字母；2從根結(jié)點到某一結(jié)點，路徑上經(jīng)過的字母依次連起來所構(gòu)成的字母序列，稱為該結(jié)點對應(yīng)的單詞。單詞列表中的每個單

14、詞，都是該單詞查找樹某個結(jié)點所對應(yīng)的單詞；3在滿足上述條件下，該單詞查找樹的結(jié)點數(shù)最少。4例如圖左邊的單詞列表就對應(yīng)于右邊的單詞查找樹。注意，對一個確定的單詞列表，請統(tǒng)計對應(yīng)的單詞查找樹的結(jié)點數(shù)（包含根結(jié)點）?！締栴}輸入】輸入文件名為word.in，該文件為一個單詞列表，每一行僅包含一個單詞和一個換行/回車符。每個單詞僅由大寫的英文字母組成，長度不超過63個字母 。文件總長度不超過32K，至少有一行數(shù)據(jù)?！締栴}輸出】輸出文件名為word.out，該文件中僅包含一個整數(shù)，該整數(shù)為單詞列表對應(yīng)的單詞查找樹的結(jié)點數(shù)。 【樣例輸入】AANASPASASCASCIIBASBASIC 【樣例輸出】13 【

15、算法分析】 首先要對建樹的過程有一個了解。對于當(dāng)前被處理的單詞和當(dāng)前樹：在根結(jié)點的子結(jié)點中找單詞的第一位字母，若存在則進而在該結(jié)點的子結(jié)點中尋找第二位如此下去直到單詞結(jié)束，即不需要在該樹中添加結(jié)點；或單詞的第n位不能被找到，即將單詞的第n位及其后的字母依次加入單詞查找樹中去。但，本問題只是問你結(jié)點總數(shù)，而非建樹方案，且有32K文件，所以應(yīng)該考慮能不能不通過建樹就直接算出結(jié)點數(shù)？為了說明問題的本質(zhì)，我們給出一個定義：一個單詞相對于另一個單詞的差：設(shè)單詞1的長度為L，且與單詞2從第N位開始不一致，則說單詞1相對于單詞2的差為L-N+1，這是描述單詞相似程度的量?？梢?，將一個單詞加入單詞樹的時候，須

16、加入的結(jié)點數(shù)等于該單詞樹中已有單詞的差的最小值。 單詞的字典順序排列后的序列則具有類似的特性，即在一個字典順序序列中，第m個單詞相對于第m-1個單詞的差必定是它對于前m-1個單詞的差中最小的。于是，得出建樹的等效算法： 讀入文件； 對單詞列表進行字典順序排序； 依次計算每個單詞對前一單詞的差，并把差累加起來。注意：第一個單詞相對于“空”的差為該單詞的長度； 累加和再加上1（根結(jié)點），輸出結(jié)果。就給定的樣例，按照這個算法求結(jié)點數(shù)的過程如下表：【數(shù)據(jù)結(jié)構(gòu)】 先確定32K（32*1024=32768字節(jié)）的文件最多有多少單詞和字母。當(dāng)然應(yīng)該盡可能地存放較短的單詞。因為單詞不重復(fù)，所以長度為1的單詞（

17、單個字母）最多26個；長度為2的單詞最多為26*26=676個；因為每個單詞后都要一個換行符（換行符在計算機中占2個字節(jié)），所以總共已經(jīng)占用的空間為：（1+2）*26+（2+2）*676=2782字節(jié)；剩余字節(jié)（32768-2782=29986字節(jié)）分配給長度為3的單詞（長度為3的單詞最多有 26*26*26=17576個）有29986/（3+2）5997。所以單詞數(shù)量最多為26+676+5997=6699。 定義一個數(shù)組：string a32768；把所有單詞連續(xù)存放起來，用選擇排序或快排對單詞進行排序?！緟⒖汲绦颉?include #include #include using names

18、pace std;int i, j, n, t, k;string a8001; /數(shù)組可以到32768string s;int main() freopen(word.in, r, stdin); freopen(word.out, w, stdout); while(cin a+n); /讀入文件中的單詞并且存儲到數(shù)組中 n-; for(i = 1 ; i n ; i+) /單詞從小到大排序，選擇排序可改為快排sort(a + 1, a + n + 1) for(j = i + 1 ; j aj) /兩個單詞進行交換 s = ai; ai = aj; aj = s; t = a1.leng

19、th(); /先累加第1個單詞的長度 for(i = 2 ; i = n ; i+) /依次計算每個單詞對前一單詞的差 j = 0; while(aij = ai - 1j & j ai - 1.length() j+; /求兩個單詞相同部分的長度 t += ai.length() - j; /累加兩個單詞的差length(ai)-j cout t + 1 =1）。 證明：很簡單，用歸納法：當(dāng)i=1時，2i-1=1顯然成立；現(xiàn)在假設(shè)第i-1層時命題成立，即第i-1層上最多有2i 2 個結(jié)點。由于二叉樹的每個結(jié)點的度最多為2，故在第i層上的最大結(jié)點數(shù)為第i-1層的2倍，即2*2i-2=2i1?！?/p>

20、性質(zhì)2】深度為k的二叉樹至多有2k 1個結(jié)點（k=1）。 證明：在具有相同深度的二叉樹中，僅當(dāng)每一層都含有最大結(jié)點數(shù)時，其樹中結(jié)點數(shù)最多。因此利用性質(zhì)1可得，深度為k的二叉樹的結(jié)點數(shù)至多為：20+21+2k-1=2k-1故命題正確。【特別】一棵深度為k且有2k1個結(jié)點的二叉樹稱為滿二叉樹。如下圖A為深度為4的滿二叉樹，這種樹的特點是每層上的結(jié)點數(shù)都是最大結(jié)點數(shù)。 可以對滿二叉樹的結(jié)點進行連續(xù)編號，約定編號從根結(jié)點起，自上而下，從左到右，由此引出完全二叉樹的定義，深度為k，有n個結(jié)點的二叉樹當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1到n的結(jié)點一一對應(yīng)時，稱為完全二叉樹。 下圖B就是一個

21、深度為4，結(jié)點數(shù)為12的完全二叉樹。它有如下特征：葉結(jié)點只可能在層次最大的兩層上出現(xiàn)；對任一結(jié)點，若其右分支下的子孫的最大層次為m，則在其左分支下的子孫的最大層次必為m或m+1。下圖C、D不是完全二叉樹，請大家思考為什么？【性質(zhì)3】對任意一棵二叉樹，如果其葉結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則一定滿足：n0=n2+1。證明：因為二叉樹中所有結(jié)點的度數(shù)均不大于2，所以結(jié)點總數(shù)(記為n)應(yīng)等于0度結(jié)點數(shù)n0、1度結(jié)點n1和2度結(jié)點數(shù)n2之和：n=no+n1+n2 (式子1) 另一方面，1度結(jié)點有一個孩子，2度結(jié)點有兩個孩子，故二叉樹中孩子結(jié)點總數(shù)是：nl+2n2 樹中只有根結(jié)點不是任何結(jié)點的孩子

22、，故二叉樹中的結(jié)點總數(shù)又可表示為：n=n1+2n2+1 (式子2) 由式子1和式子2得到：no=n2+1【性質(zhì)4】具有n個結(jié)點的完全二叉樹的深度為floor(log2n)+1證明：假設(shè)深度為k，則根據(jù)完全二叉樹的定義，前面k-1層一定是滿的，所以n2k 1 -1。但n又要滿足n=2k -1。所以，2k11n=2k -1。變換一下為2k1=n2k。 以2為底取對數(shù)得到：k-1=log2n1,則其父結(jié)點編號為i/2。 如果2*in，則結(jié)點i無左孩子（當(dāng)然也無右孩子，為什么？即結(jié)點i為葉結(jié)點）；否則左孩子編號為2*i。如果2*i+1n，則結(jié)點i無右孩子；否則右孩子編號為2*i+1。證明：略，我們只要

23、驗證一下即可?？偨Y(jié)如圖：二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)，即單鏈表結(jié)構(gòu)或雙鏈表結(jié)構(gòu)（同樹）。數(shù)據(jù)結(jié)構(gòu)修改如下：typedef struct node;typedef node *tree;struct node char data; tree lchild, rchild;tree bt;或：typedef struct node;typedef node *tree;struct node char data; tree lchild, rchild,father;tree bt; 如左圖的一棵二叉樹用單鏈表就可以表示成右邊的形式：順序存儲結(jié)構(gòu)，即幾個數(shù)組加一個指針變量。數(shù)據(jù)結(jié)構(gòu)

24、修改如下：const int n = 10;char datan;char lchildn;char rchildn;int bt; /根結(jié)點指針 二叉樹在處理表達式時經(jīng)常用到，一般用葉結(jié)點表示運算元，分支結(jié)點表示運算符。這樣的二叉樹稱為表達式樹。如現(xiàn)在有一個表達式：（a+b/c）*(d-e)?？梢杂靡詧D表示： 數(shù)據(jù)結(jié)構(gòu)定義如下： 按表達式的書寫順序逐個編號，分別為1.9，注意表達式中的所有括號在樹中是不出現(xiàn)的，因為表達式樹本身就是有序的。葉結(jié)點的左右子樹均為空（用0表示）。char data9 = a, +, b, /, c, *, d, -, e;int lchild9 = 0,1,0,3

25、,0,2,0,7,0;int rchild9 = 0,4,0,5,0,8,0,9,0;int bt; /根結(jié)點指針,初值=6，指向* 二叉樹的操作: 最重要的是遍歷二叉樹，但基礎(chǔ)是建一棵二叉樹、插入一個結(jié)點到二叉樹中、刪除結(jié)點或子樹等。【例3-3】醫(yī)院設(shè)置【問題描述】 設(shè)有一棵二叉樹（如圖3-8，其中圈中的數(shù)字表示結(jié)點中居民的人口，圈邊上數(shù)字表示結(jié)點編號?，F(xiàn)在要求在某個結(jié)點上建立一個醫(yī)院，使所有居民所走的路程之和為最小，同時約定，相鄰結(jié)點之間的距離為1。就本圖而言，若醫(yī)院建在1處，則距離和=4+12+2*20+2*40=136；若醫(yī)院建在3處，則距離和=4*2+13+20+40=81【輸入格式

26、】 輸入文件名為hospital.in，其中第一行一個整數(shù)n，表示樹的結(jié)點數(shù)（n=100）。接下來的n行每行描述了一個結(jié)點的狀況，包含三個整數(shù)，整數(shù)之間用空格（一個或多個）分隔，其中：第一個數(shù)為居民人口數(shù)；第二個數(shù)為左鏈接，為0表示無鏈接；第三個數(shù)為右鏈接，為0表示無鏈接。【輸出格式】 輸出文件名為hospital.out，該文件只有一個整數(shù)，表示最小距離和?！緲永斎搿?13 2 34 0 012 4 520 0 040 0 0【樣例輸出】8113412204012345【算法分析】 這是一道簡單的二叉樹應(yīng)用問題，問題中的結(jié)點數(shù)并不多，數(shù)據(jù)規(guī)模也不大，采用鄰接矩陣存儲，用Floyed法求出任

27、意兩結(jié)點之間的最短路徑長，然后窮舉醫(yī)院可能建立的n個結(jié)點位置，找出一個最小距離的位置即可。當(dāng)然也可以用雙鏈表結(jié)構(gòu)或帶父結(jié)點信息的數(shù)組存儲結(jié)構(gòu)來解決，但實際操作稍微麻煩了一點?！緟⒖汲绦颉?include #include include using namespace std;int a101;int g101101;int main() int n, i, j, k, l, r, min, total; freopen(hospital.in, r, stdin); freopen(hospital.out, w, stdout); cin n; for(i = 1 ; i = n ; i+

28、) for(j = 1 ; j = n ; j+) gij = 1000000; for(i = 1 ; i ai l r; if(l 0) gil = gli = 1; if(r 0) gir = gri = 1;for(k = 1 ; k = n ; k+) /用Floyed求任意兩結(jié)點之間的最短路徑 for(i = 1 ; i = n ; i+) if(i != k) for(j = 1 ; j = n ; j+) if(i != j & k != j & gik + gkj gij) gij = gik + gkj;min = 0 x7fffffff;for(i = 1 ; i = n

29、 ; i+) /窮舉醫(yī)院建在N個結(jié)點，找出最短距離total = 0;for(j = 1 ; j = n ; j+) total += gij * aj;if(total min) min = total;cout min endl;return 0;【后記】 在各種競賽中經(jīng)常遇到這樣的問題：N-1條公路連接著N個城市，從每個城市出發(fā)都可以通過公路到達其它任意的城市。每個城市里面都有一定數(shù)量的居民，但是數(shù)量并不一定相等，每條公路的長度也不一定相等。X公司（或者是政府）決定在某一個城市建立一個醫(yī)院/酒廠/游樂場，問：將它建在哪里，可以使得所有的居民移動到那里的總耗費最??？這種題目都是本題的“變型

30、”，一般稱為“樹的中心點問題”。除了簡單的窮舉法外，還有更好的時間復(fù)雜度為O(n)的算法，我們講在后面的章節(jié)中繼續(xù)討論。遍歷二叉樹遍歷二叉樹 在二叉樹的應(yīng)用中，常常要求在樹中查找具有某種特征的結(jié)點，或者對全部結(jié)點逐一進行某種處理。這就是二叉樹的遍歷問題。所謂二叉樹的遍歷是指按一定的規(guī)律和次序訪問樹中的各個結(jié)點，而且每個結(jié)點僅被訪問一次?！霸L問”的含義很廣，可以是對結(jié)點作各種處理，如輸出結(jié)點的信息等。遍歷一般按照從左到右的順序，共有3種遍歷方法，先（根）序遍歷，中（根）序遍歷，后（根）序遍歷。先序遍歷的操作定義如下：若二叉樹為空，則空操作，否則訪問根結(jié)點先序遍歷左子樹先序遍歷右子樹void pr

31、eorder(tree bt) /先序遍歷根結(jié)點為bt的二叉樹的遞歸算法 if(bt) cout data; preorder(bt-lchild); preorder(bt-rchild); 先序遍歷此圖結(jié)果為：124753689中序遍歷的操作定義如下：若二叉樹為空，則空操作，否則 中序遍歷左子樹 訪問根結(jié)點中序遍歷右子樹void inorder(tree bt) /中序遍歷根結(jié)點為bt的二叉樹的遞歸算法 if(bt) inorder(bt-lchild);cout data;inorder(bt-rchild); 中序遍歷此圖結(jié)果為：742513869后序遍歷的操作定義如下：若二叉樹為空，

32、則空操作，否則后序遍歷左子樹后序遍歷右子樹訪問根結(jié)點void postorder(tree bt) /后序遍歷根結(jié)點為bt的二叉樹的遞歸算法 if(bt) postorder(bt-lchild); postorder(bt-rchild); cout data; 后序遍歷此圖結(jié)果為：745289631 當(dāng)然，我們還可以把遞歸過程改成用棧實現(xiàn)的非遞歸過程，以先序遍歷為例，其它的留給讀者完成。void preorder(tree bt) /先序遍歷bt所指的二叉樹 tree stackn; /棧 int top = -1; /棧頂指針 tree P; while(bt | top) while(

33、bt) /非葉結(jié)點 cout data; /訪問根 stack+top = bt-rchild; /右子樹壓棧 bt = bt-lchild; /遍歷左子樹 if(top) /棧中所有元素出棧，遍歷完畢 bt = stacktop-; 關(guān)于前面講的表達式樹，我們可以分別用先序、中序、后序的遍歷方法得出完全不同的遍歷結(jié)果，如對于下圖中遍歷結(jié)果如下，它們正好對應(yīng)著表達式的3種表示方法。-+a*b-cd/ef (前綴表示、波蘭式)a+b*c-d-e/f (中綴表示)abcd-*+ef/- (后綴表示、逆波蘭式)二叉樹的其它重要操作二叉樹的其它重要操作 除了“遍歷”以外，二叉樹的其它重要操作還有：建立

34、一棵二叉樹、插入一個結(jié)點到二叉樹中、刪除結(jié)點或子樹等。1、建立一棵二叉樹void pre_crt(tree &bt) /按先序次序輸入二叉樹中結(jié)點的值，生成char ch;ch = getchar(); /二叉樹的單鏈表存儲結(jié)構(gòu)，bt為指向根結(jié)點的指針,$表示空樹 if(ch != $)bt = new node; /建根結(jié)點bt-data = ch;pre_crt(bt-lchild); /建左子樹pre_crt(bt-rchild); /建右子樹else bt = NULL;2、刪除二叉樹void dis(tree &bt) /刪除二叉樹if(bt)dis(bt-lchild); /刪左子

35、樹dis(bt-rchild); /刪右子樹delete bt; /釋放父結(jié)點3插入一個結(jié)點到排序二叉樹中void insert(tree &bt, int n) /插入一個結(jié)點到排序二叉樹中if(bt)if(n data) insert(bt-lchild, n);else if(n bt-data) insert(bt-rchild, n);elsebt = new node; /新開一個空間bt-data = n;bt-lchild = bt-rchild = NULL;4在排序二叉樹中查找一個數(shù)，找到返回該結(jié)點,否則返回NULLtree findn(tree bt, int n) /在

36、二叉樹中查找一個數(shù)，找到返回該結(jié)點,否則返回NULL。if(bt)if(n data) findn(bt-lchild, n);else if(n bt-data) findn(bt-rchild, n);else return bt;else return NULL;5用嵌套括號表示法輸出二叉樹void print(tree bt) /用嵌套括號表示法輸出二叉樹if(bt)cout data;if(bt-lchild | bt-rchild)cout lchild);if(bt-rchild) cout rchild);cout ); 下面我們換個角度考慮這個問題，從二叉樹的遍歷已經(jīng)知道，任

37、意一棵二叉樹結(jié)點的先序序列和中序序列是唯一的。反過來，給定結(jié)點的先序序列和中序序列，能否確定一棵二叉樹呢？又是否唯一呢？ 由定義，二叉樹的先序遍歷是先訪問根結(jié)點，再遍歷左子樹，最后遍歷右子樹。即在結(jié)點的先序序列中，第一個結(jié)點必是根，假設(shè)為root。再結(jié)合中序遍歷，因為中序遍歷是先遍歷左子樹，再訪問根，最后遍歷右子樹。所以結(jié)點root正好把中序序列分成了兩部分，root之前的應(yīng)該是左子樹上的結(jié)點，root之后的應(yīng)該是右子樹上的結(jié)點。依次類推，便可遞歸得到整棵二叉樹。結(jié)論：已知先序序列和中序序列可以確定出二叉樹；已知中序序列和后序序列也可以確定出二叉樹；但，已知先序序列和后序序列卻不可以確定出二叉

38、樹；為什么？舉個3個結(jié)點的反例。例如：已知結(jié)點的先序序列為ABCDEFG，中序序列為CBEDAFG。構(gòu)造出二叉樹。過程見下圖：【例3-4】求后序遍歷【問題描述】輸入一棵二叉樹的先序和中序遍歷序列，輸出其后序遍歷序列。【輸入格式】輸入文件為tree.in，共兩行，第一行一個字符串，表示樹的先序遍 歷，第二行一個字符串，表示樹的中序遍歷。樹的結(jié)點一律用小寫 字母表示?！据敵龈袷健枯敵鑫募閠ree.out，僅一行，表示樹的后序遍歷序列。【樣例輸入】abdecdbeac【樣例輸出】debca【參考程序】#include #include #include using namespace std;st

39、ring s1, s2;void calc(int l1, int r1, int l2, int r2)int m = s2.find(s1l1);if(m l2) calc(l1 + 1, l1 + m - l2, l2, m - 1);if(m r2) calc(l1 + m - l2 + 1, r1, m + 1, r2);cout s1 s2;calc(0, s1.length() - 1, 0, s2.length() - 1);cout endl;return 0;【例3-5】擴展二叉樹【問題描述】由于先序、中序和后序序列中的任一個都不能唯一確定一棵二叉樹，所以對二叉樹做如下處理

40、，將二叉樹的空結(jié)點用補齊，如圖所示。我們把這樣處理后的二叉樹稱為原二叉樹的擴展二叉樹，擴展二叉樹的先序和后序序列能唯一確定其二叉樹。現(xiàn)給出擴展二叉樹的先序序列，要求輸出其中序和后序序列?！据斎霕永縯ree_b.inABD.EF.G.C.【輸出樣例】tree_b.outDBFEGACDFGEBCA#include #include #include #include #include #include using namespace std;typedef struct node;typedef node *tree;struct nodechar data;tree lchild, rchi

41、ld;tree bt;int i;string s;void build(tree &bt) /建樹if(s+i!=.)bt = new node; bt = new node; bt-data = si;build(bt-lchild); build(bt-rchild); else bt = NULL;void printzx(tree bt) /輸出中序序列 if(bt)printzx(bt-lchild);cout data;printzx(bt-rchild);void printhx(tree bt) /輸出后序序列 if(bt)printhx(bt-lchild);printhx

42、(bt-rchild);cout data;int main()freopen(tree_b.in, r, stdin);freopen(tree_b.out, w, stdout);cin s;i = -1;build(bt);printzx(bt);cout endl;printhx(bt);cout 1)個結(jié)點的二叉樹可以看成是由一個根結(jié)點、一棵具有i個結(jié)點的左子樹和一棵具有n-i-1個結(jié)點的右子樹組成，其中0=i=n-1,由此不難得出下列遞歸公式：我們可以利用生成函數(shù)討論這個遞歸公式，得出：Bn=類推到具有n個結(jié)點、互不相似的多叉樹的數(shù)目Tn由于樹可以轉(zhuǎn)換成二叉樹且轉(zhuǎn)換之后的根節(jié)點沒有

43、右兒子，所以，可以推出：Tn=Bn-1?！菊n堂練習(xí)課堂練習(xí)】1、一棵完全二叉樹的結(jié)點總數(shù)為18，其葉結(jié)點數(shù)為 。A.7個 B.8個 C.9個 D.10個2、 二叉樹第10層的結(jié)點數(shù)的最大數(shù)目為 。A.10 B.100 C.512 D.10243、一棵深度為K的滿二叉樹有（ ）個結(jié)點。A.2K-1 B.2K C.2*K D.2*K-14、對任何一棵二叉樹T，設(shè)n0、n1、n2分別是度數(shù)為0、1、2的頂點數(shù)，則下列判斷中正確的是 。 A.n0=n2+1 B.n1=n0+1 C. n2=n0+1 D.n2=n0+15、一棵n個節(jié)點的完全二叉樹，則該二叉樹的高度h為( )。A.n/2 B.log(n)

44、 C.log(n)/2 D.6、一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是 。A.250 B.500 C.254 D.5017、如果一棵二叉樹有N個度為2的節(jié)點，M個度為1的節(jié)點，則該樹的葉子個數(shù)為 。A. N+1 B. 2 * N-1 C.N-1 D. M+N-18、一棵非空二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定滿足 。A.所有結(jié)點均無左孩子 B.所有的結(jié)點均無右孩子C.只有一個葉子結(jié)點 D.是任意一棵二叉樹9、將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個結(jié)點的完全三叉樹的高度是 。A.4 B.5 C.6 D.710、在一棵具有K層的滿三叉樹中，結(jié)點總數(shù)為

45、 。A.(3k-1)/2 B.3k-1 C.(3k-1)/3 D.3k11、設(shè)樹T的高度為4，其中度為1、2、3和4的結(jié)點個數(shù)分別為4、2、1、1，則T中的葉子數(shù)為 。 A.5 B.6 C.7 D.812、一棵樹T有2個度數(shù)為2的結(jié)點、有1個度數(shù)為3的結(jié)點、有3個度數(shù)為4的結(jié)點，那么樹T有（ ）個樹葉。A.14 B.6 C.18 D.713、某二叉樹中序序列為abcdefg，后序序列為bdcafge，則前序序列是 。A.egfacbd B.eacbdgf C.eagcfbd D.以上答案都不對14、已知某二叉樹的中序遍歷序列是debac，后序遍歷序列是dabec，則它的前序遍歷序列是 。 A.

46、a c b e d B.d e c a b C.d e a b c D.c e d b a15、一顆二叉樹的中序遍歷序列為DGBAECHF，后序遍歷序列為GDBEHFCA，則前序遍歷序列是 。A. ABCDFGHE B. ABDGCEFH C. ACBGDHEF D. ACEFHBGD16、已知一棵二叉樹的前序序列為ABDEGCFH，中序序列為DBGEACHF，則該二叉樹的層次序列為 。 A.GEDHFBCA B.DGEBHFCA C.ABCDEFGH D.ACBFEDHG17、已知一棵二叉樹的前序遍歷結(jié)果為ABDECFHJIG，中序遍歷的結(jié)果為DBEAJHFICG，則這棵二叉樹的深度為 。A

47、.3 B.4 C.5 D.618、二叉樹的先序遍歷和中序遍歷如下：先序遍歷:EFHIGJK，中序遍歷:HFIEJKG。該二叉樹根的右子樹的根是_。 A. E B. F C. G D.H19、中綴表達式A-（B+C/D）*E的后綴形式是 。 A.AB-C+D/E* B.ABC+D/-E* C.ABCD/E*+- D.ABCD/+E*-20、設(shè)森林F對應(yīng)的二叉樹為B，它有M個結(jié)點，B的根為P，P的右子樹結(jié)點個數(shù)為N，森林F中第一棵樹的結(jié)點個數(shù)是 。A.M-N B.M-N-1 C.N+1 D.條件不充分，無法確定【練習(xí)答案練習(xí)答案】1.C 2.C 3.A 4.A 5.D 6.D 7.A 8.A 9.

48、B 10.A 11.D 12.A 13.B 14.D 15.B 16.C 17.C 18.C 19.D 20.A7、此樹的邊數(shù)為2N+M，故而總共有2N+M+1個頂點。除去度為1、2的頂點，度為0的節(jié)點（即葉子節(jié)點）有(2N+M+1)-(N+M)=N+1。答案：A12、設(shè)樹T有n個結(jié)點，m條邊。邊數(shù)為結(jié)點的度數(shù)之和，即m=221334=19，n=m+1=20。n個結(jié)點中有1+2+3=6個分支結(jié)點，有葉結(jié)點20-6=14個。答案：A15、中序遍歷DGBAECHF和后序遍歷GDBEHFCA唯一對應(yīng)一棵二叉樹前序遍歷為ABDGCEFH。答案：B16、由前序序列和中序序列可以唯一地確定一棵二叉樹，根據(jù)

49、題設(shè)中的前序序列和中序序列確定的二叉樹為：由此可見，其層次序列為ABCDEFGH。答案：C17、由題目給出二叉樹先序遍歷結(jié)點的順序：ABDECFHJIG可知結(jié)點A為二叉樹的根結(jié)點。再由中序遍歷的結(jié)點順序：DBEAJHFICG可知結(jié)點A前的DBE為根結(jié)點A的左子樹的結(jié)點，而JHFICG為根結(jié)點A的右子樹的結(jié)點。 先來看A結(jié)點的左子樹的結(jié)點DBE。在先序遍歷順序中，B結(jié)點在A結(jié)點之后，說明B結(jié)點是左子樹的根結(jié)點，D結(jié)點又在B結(jié)點之后，則D是B的左子樹的根結(jié)點。結(jié)點E由中序遍歷的順序可知是B的右子樹的根結(jié)點。同樣求出右子樹JHFICG，如下圖。 由圖可知，二叉樹的深度為5。答案：C。19、該題答案是

50、（D），本題主要考察學(xué)生怎樣將中綴表達式轉(zhuǎn)換為后綴表達式?？梢韵犬嫵鲈摱鏄?，對其進行后根遍歷即為答案。【上機練習(xí)上機練習(xí)】 1、小球(DROP)【問題描述】 許多的小球一個一個的從一棵滿二叉樹上掉下來組成FBT（Full Binary Tree，滿二叉樹），每一時間，一個正在下降的球第一個訪問的是非葉子節(jié)點。然后繼續(xù)下降時，或者走右子樹，或者走左子樹，直到訪問到葉子節(jié)點。決定球運動方向的是每個節(jié)點的布爾值。最初，所有的節(jié)點都是FALSE，當(dāng)訪問到一個節(jié)點時，如果這個節(jié)點是FALSE，則這個球把它變成TRUE，然后從左子樹走，繼續(xù)它的旅程。如果節(jié)點是TRUE，則球也會改變它為FALSE，而接下

51、來從右子樹走。滿二叉樹的標(biāo)記方法如下圖。 因為所有的節(jié)點最初為FALSE，所以第一個球?qū)L問節(jié)點1，節(jié)點2和節(jié)點4，轉(zhuǎn)變節(jié)點的布爾值后在在節(jié)點8停止。第二個球?qū)L問節(jié)點1、3、6,在節(jié)點12停止。明顯地，第三個球在它停止之前，會訪問節(jié)點1、2、5，在節(jié)點10停止。現(xiàn)在你的任務(wù)是，給定FBT的深度D，和I，表示第I個小球下落，你可以假定I不超過給定的FBT的葉子數(shù)，寫一個程序求小球停止時的葉子序號。【輸入格式】 輸入文件僅一行包含兩個用空格隔開的整數(shù)D和I。其中2=D=20，1=I=524288?！据敵龈袷健?對應(yīng)輸出第I個小球下落停止時的葉子序號?！据斎霕永緿ROP.IN4 2【輸出樣例】DROP.OUT122、二叉樹遍歷(flist)【問題描述】樹和二叉樹基本上都有先序、中序、后序、按層遍