第3章--第1-3節(jié)-樹、二叉樹、堆及其應(yīng)用(C++版)

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

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

3、，它沒(méi)有前驅(qū)，其余 每個(gè)結(jié)點(diǎn)都有唯一的一個(gè)前驅(qū)結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)可以有0或多個(gè)后繼結(jié) 點(diǎn)。因此樹雖然是非線性結(jié)構(gòu)，但也是有序結(jié)構(gòu)。至于前驅(qū)后繼結(jié)點(diǎn) 是哪個(gè)，還要看樹的遍歷方法，我們將在后面討論； C. 一個(gè)結(jié)點(diǎn)的子樹個(gè)數(shù)，稱為這個(gè)結(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、2、4、7）； 根以外的分支結(jié)點(diǎn)又稱為內(nèi)部結(jié)點(diǎn)（結(jié)點(diǎn)2、4、7）；樹中各結(jié)點(diǎn)的 度的最大值稱為這棵樹的度（這棵樹的度為3）。 D. 在用圖形表示的樹型結(jié)構(gòu)中，對(duì)兩個(gè)用線段（稱為樹枝）連接的相關(guān) 聯(lián)的結(jié)點(diǎn)，稱上

4、端結(jié)點(diǎn)為下端結(jié)點(diǎn)的父結(jié)點(diǎn)，稱下端結(jié)點(diǎn)為上端結(jié)點(diǎn) 的子結(jié)點(diǎn)。稱同一個(gè)父結(jié)點(diǎn)的多個(gè)子結(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)，同時(shí)結(jié)點(diǎn)2又是結(jié)點(diǎn)5、6的父結(jié)點(diǎn)。稱從根結(jié)點(diǎn)到某個(gè)子結(jié)點(diǎn) 所經(jīng)過(guò)的所有結(jié)點(diǎn)為這個(gè)子結(jié)點(diǎn)的祖先。如結(jié)點(diǎn)1、4、7是結(jié)點(diǎn)8 的祖先。稱以某個(gè)結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都是該結(jié)點(diǎn)的子孫。 如結(jié)點(diǎn)7、8、9都是結(jié)點(diǎn)4的子孫。 E.定義一棵樹的根結(jié)點(diǎn)的層次（level）為0，其它結(jié)點(diǎn)的層次等于它的 父結(jié)點(diǎn)層次加1。如結(jié)點(diǎn)2、3、4的層次為1，結(jié)點(diǎn)5、6、7的層次為2 ，結(jié)點(diǎn)8、9的層次為3。一棵樹中所有的結(jié)點(diǎn)的層次的最大

5、值稱為樹 的深度（depth）。如這棵樹的深度為3。 F.對(duì)于樹中任意兩個(gè)不同的結(jié)點(diǎn)，如果從一個(gè)結(jié)點(diǎn)出發(fā)，自上而下沿著 樹中連著結(jié)點(diǎn)的線段能到達(dá)另一結(jié)點(diǎn)，稱它們之間存在著一條路徑。 可用路徑所經(jīng)過(guò)的結(jié)點(diǎn)序列表示路徑，路徑的長(zhǎng)度等于路徑上的結(jié)點(diǎn) 個(gè)數(shù)減1。如上圖中，結(jié)點(diǎn)1和結(jié)點(diǎn)8之間存在著一條路徑，并可用（1 、4、7、8）表示這條路徑，該條路徑的長(zhǎng)度為3。注意，不同子樹上 的結(jié)點(diǎn)之間不存在路徑，從根結(jié)點(diǎn)出發(fā)，到樹中的其余結(jié)點(diǎn)一定存在 著一條路徑。 G.森林（forest）是m(m=0)棵互不相交的樹的集合。 樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu) 方法1：數(shù)組，稱為“父親表示法”。 const int m

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

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

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

9、struct node char data; /數(shù)據(jù)域 tree firstchild, next; /指針域，分別指向第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn) ; tree t; 【例3-1】找樹根和孩子 【問(wèn)題描述】 給定一棵樹，輸出樹的根root，孩子最多的結(jié)點(diǎn)max以及他的孩子 【輸入格式】 第一行：n（結(jié)點(diǎn)數(shù)=100），m（邊數(shù)=200）。 以下m行；每行兩個(gè)結(jié)點(diǎn)x和y， 表示y是x的孩子(x,y=1000)。 【輸出格式】 第一行：樹根：root。 第二行：孩子最多的結(jié)點(diǎn)max。 第三行：max的孩子。 【輸入樣例】 8 7 4 1 4 2 1 3 1 5 2 6 2 7 2 8 【輸出樣例

10、】 4 2 6 7 8 【參考程序】 #include using namespace std; int n,m,tree101=0; int main() int i,x,y,root,maxroot,sum=0,j,Max=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é)點(diǎn) sum=0; for(j=1;jMax) Max=sum;maxroot=i; coutrootendlmaxrootendl; for(i=1;i=n;i+)

11、 if(treei=maxroot) couti ; return 0; 樹的遍歷樹的遍歷 在應(yīng)用樹結(jié)構(gòu)解決問(wèn)題時(shí)，往往要求按照某種次序獲得樹中全部 結(jié)點(diǎn)的信息，這種操作叫作樹的遍歷。遍歷的方法有多種，常用的有 ： A、先序（根）遍歷：先訪問(wèn)根結(jié)點(diǎn)，再?gòu)淖蟮接野凑障刃蛩枷氡闅v 各棵子樹。 如上圖先序遍歷的結(jié)果為：125634789； B、后序（根）遍歷：先從左到右遍歷各棵子樹，再訪問(wèn)根結(jié)點(diǎn)。如 上圖后序遍歷的結(jié)果為：562389741； C、層次遍歷：按層次從小到大逐個(gè)訪問(wèn)，同一層次按照從左到右的 次序。 如上圖層次遍歷的結(jié)果為：123456789； D、葉結(jié)點(diǎn)遍歷：有時(shí)把所有的數(shù)據(jù)信息都存放

12、在葉結(jié)點(diǎn)中，而其余 結(jié)點(diǎn)都是用來(lái)表示數(shù)據(jù)之間的某種分支或?qū)哟侮P(guān)系，這種情況就 用這種方法。如上圖按照這個(gè)思想訪問(wèn)的結(jié)果為：56389； 大家可以看出，AB兩種方法的定義是遞歸的，所以在程序?qū)崿F(xiàn)時(shí) 往往也是采用遞歸的思想。既通常所說(shuō)的“深度優(yōu)先搜索”。如用先 序遍歷編寫的過(guò)程如下： void tral(tree t, int m) If (t) cout data endl; for(int i = 0 ; i childi, m); C方法應(yīng)用也較多，實(shí)際上是我們講的“廣度優(yōu)先搜索”。思想 如下：若某個(gè)結(jié)點(diǎn)被訪問(wèn)，則該結(jié)點(diǎn)的子結(jié)點(diǎn)應(yīng)記錄，等待被訪問(wèn)。 順序訪問(wèn)各層次上結(jié)點(diǎn)，直至不再有未訪問(wèn)過(guò)的

13、結(jié)點(diǎn)。為此，引入一 個(gè)隊(duì)列來(lái)存儲(chǔ)等待訪問(wèn)的子結(jié)點(diǎn)，設(shè)一個(gè)隊(duì)首和隊(duì)尾指針?lè)謩e表示出 隊(duì)、進(jìn)隊(duì)的下標(biāo)。程序框架如下： const int n = 100; int head, tail, i; tree qn; tree p; void work() tail = head = 1; qtail = t; tail+; /隊(duì)尾為空 while(head tail) p = qhead; head+; cout data ; for(i = 0 ; i childi) qtail = p-childi; tail+; 【例3-2】單詞查找樹 【問(wèn)題描述】 在進(jìn)行文法分析的時(shí)候，通常需要檢測(cè)一個(gè)單詞是

14、否在我們的單 詞列表里。為了提高查找和定位的速度，通常都畫出與單詞列表所對(duì) 應(yīng)的單詞查找樹，其特點(diǎn)如下： 1根結(jié)點(diǎn)不包含字母，除根結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都僅包含一個(gè)大寫英 文字母； 2從根結(jié)點(diǎn)到某一結(jié)點(diǎn)，路徑上經(jīng)過(guò)的字母依次連起來(lái)所構(gòu)成的字 母序列，稱為該結(jié)點(diǎn)對(duì)應(yīng)的單詞。單詞列表中的每個(gè)單詞，都是該單 詞查找樹某個(gè)結(jié)點(diǎn)所對(duì)應(yīng)的單詞； 3在滿足上述條件下，該單詞查找樹的結(jié)點(diǎn)數(shù)最少。 4例如圖左邊的單詞列表就對(duì)應(yīng)于右邊的單詞查找樹。注意，對(duì)一 個(gè)確定的單詞列表，請(qǐng)統(tǒng)計(jì)對(duì)應(yīng)的單詞查找樹的結(jié)點(diǎn)數(shù)（包含根結(jié)點(diǎn) ）。 【問(wèn)題輸入】 輸入文件名為word.in，該文件為一個(gè)單詞列表，每一行僅包含一個(gè) 單詞和一個(gè)換

15、行/回車符。每個(gè)單詞僅由大寫的英文字母組成，長(zhǎng)度 不超過(guò)63個(gè)字母 。文件總長(zhǎng)度不超過(guò)32K，至少有一行數(shù)據(jù)。 【問(wèn)題輸出】 輸出文件名為word.out，該文件中僅包含一個(gè)整數(shù)，該整數(shù)為單詞 列表對(duì)應(yīng)的單詞查找樹的結(jié)點(diǎn)數(shù)。 【樣例輸入】 A AN ASP AS ASC ASCII BAS BASIC 【樣例輸出】 13 【算法分析】 首先要對(duì)建樹的過(guò)程有一個(gè)了解。對(duì)于當(dāng)前被處理的單詞和當(dāng)前 樹：在根結(jié)點(diǎn)的子結(jié)點(diǎn)中找單詞的第一位字母，若存在則進(jìn)而在該結(jié) 點(diǎn)的子結(jié)點(diǎn)中尋找第二位如此下去直到單詞結(jié)束，即不需要在該 樹中添加結(jié)點(diǎn)；或單詞的第n位不能被找到，即將單詞的第n位及其后 的字母依次加入單詞查

16、找樹中去。但，本問(wèn)題只是問(wèn)你結(jié)點(diǎn)總數(shù)，而 非建樹方案，且有32K文件，所以應(yīng)該考慮能不能不通過(guò)建樹就直接 算出結(jié)點(diǎn)數(shù)？為了說(shuō)明問(wèn)題的本質(zhì)，我們給出一個(gè)定義：一個(gè)單詞相 對(duì)于另一個(gè)單詞的差：設(shè)單詞1的長(zhǎng)度為L(zhǎng)，且與單詞2從第N位開(kāi)始不 一致，則說(shuō)單詞1相對(duì)于單詞2的差為L(zhǎng)-N+1，這是描述單詞相似程度 的量?？梢?jiàn)，將一個(gè)單詞加入單詞樹的時(shí)候，須加入的結(jié)點(diǎn)數(shù)等于該 單詞樹中已有單詞的差的最小值。 單詞的字典順序排列后的序列則具有類似的特性，即在一個(gè)字典 順序序列中，第m個(gè)單詞相對(duì)于第m-1個(gè)單詞的差必定是它對(duì)于前m-1 個(gè)單詞的差中最小的。于是，得出建樹的等效算法： 讀入文件； 對(duì)單詞列表進(jìn)行字典

17、順序排序； 依次計(jì)算每個(gè)單詞對(duì)前一單詞的差，并把差累加起來(lái)。注意：第 一個(gè)單詞相對(duì)于“空”的差為該單詞的長(zhǎng)度； 累加和再加上1（根結(jié)點(diǎn)），輸出結(jié)果。 就給定的樣例，按照這個(gè)算法求結(jié)點(diǎn)數(shù)的過(guò)程如下表： 【數(shù)據(jù)結(jié)構(gòu)】 先確定32K（32*1024=32768字節(jié)）的文件最多有多少單詞和字母 。當(dāng)然應(yīng)該盡可能地存放較短的單詞。因?yàn)閱卧~不重復(fù)，所以長(zhǎng)度為 1的單詞（單個(gè)字母）最多26個(gè)；長(zhǎng)度為2的單詞最多為26*26=676個(gè) ；因?yàn)槊總€(gè)單詞后都要一個(gè)換行符（換行符在計(jì)算機(jī)中占2個(gè)字節(jié)） ，所以總共已經(jīng)占用的空間為：（1+2）*26+（2+2）*676=2782字節(jié) ；剩余字節(jié)（32768-2782=

18、29986字節(jié)）分配給長(zhǎng)度為3的單詞（長(zhǎng)度 為3的單詞最多有 26*26*26=17576個(gè)）有29986/（3+2）5997。所 以單詞數(shù)量最多為26+676+5997=6699。 定義一個(gè)數(shù)組：string a32768；把所有單詞連續(xù)存放起來(lái)， 用選擇排序或快排對(duì)單詞進(jìn)行排序。 【參考程序】 #include #include #include using namespace std; int i, j, n, t, k; string a8001; /數(shù)組可以到32768 string s; int main() freopen(word.in, r, stdin); freopen(

19、word.out, w, stdout); while(cin a+n); /讀入文件中的單詞并且存儲(chǔ)到數(shù)組中 n-; for(i = 1 ; i n ; i+) /單詞從小到大排序，選擇排序可改為快排sort(a + 1, a + n + 1) for(j = i + 1 ; j aj) /兩個(gè)單詞進(jìn)行交換 s = ai; ai = aj; aj = s; t = a1.length(); /先累加第1個(gè)單詞的長(zhǎng)度 for(i = 2 ; i = n ; i+) /依次計(jì)算每個(gè)單詞對(duì)前一單詞的差 j = 0; while(aij = ai - 1j /求兩個(gè)單詞相同部分的長(zhǎng)度 t += ai

20、.length() - j; /累加兩個(gè)單詞的差length(ai)-j cout t + 1 =1）。 證明：很簡(jiǎn)單，用歸納法：當(dāng)i=1時(shí)，2i-1=1顯然成立；現(xiàn)在假 設(shè)第i-1層時(shí)命題成立，即第i-1層上最多有2i 2 個(gè)結(jié)點(diǎn)。由于二 叉樹的每個(gè)結(jié)點(diǎn)的度最多為2，故在第i層上的最大結(jié)點(diǎn)數(shù)為第i-1層 的2倍， 即 2*2i-2=2i1。 【性質(zhì)2】深度為k的二叉樹至多有2k 1個(gè)結(jié)點(diǎn)（k=1）。 證明：在具有相同深度的二叉樹中，僅當(dāng)每一層都含有最大結(jié)點(diǎn) 數(shù)時(shí)，其樹中結(jié)點(diǎn)數(shù)最多。因此利用性質(zhì)1可得，深度為k的二叉樹的 結(jié)點(diǎn)數(shù)至多為： 20+21+2k-1=2k-1 故命題正確。 【特別】一

21、棵深度為k且有2k1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。如下 圖A為深度為4的滿二叉樹，這種樹的特點(diǎn)是每層上的結(jié)點(diǎn)數(shù)都是最大 結(jié)點(diǎn)數(shù)。 可以對(duì)滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，約定編號(hào)從根結(jié)點(diǎn)起，自 上而下，從左到右，由此引出完全二叉樹的定義，深度為k，有n個(gè)結(jié) 點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1 到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹。 下圖B就是一個(gè)深度為4，結(jié)點(diǎn)數(shù)為12的完全二叉樹。它有如下特 征：葉結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)；對(duì)任一結(jié)點(diǎn)，若其右分 支下的子孫的最大層次為m，則在其左分支下的子孫的最大層次必為m 或m+1。下圖C、D不是完全二叉樹，請(qǐng)大家思考為什么？ 【

22、性質(zhì)3】對(duì)任意一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù) 為n2，則一定滿足：n0=n2+1。 證明：因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)的度數(shù)均不大于2，所以結(jié)點(diǎn)總數(shù)(記為 n)應(yīng)等于0度結(jié)點(diǎn)數(shù)n0、1度結(jié)點(diǎn)n1和2度結(jié)點(diǎn)數(shù)n2之和： n=no+n1+n2 (式子1) 另一方面，1度結(jié)點(diǎn)有一個(gè)孩子，2度結(jié)點(diǎn)有兩個(gè)孩子，故二叉樹 中孩子結(jié)點(diǎn)總數(shù)是： nl+2n2 樹中只有根結(jié)點(diǎn)不是任何結(jié)點(diǎn)的孩子，故二叉樹中的結(jié)點(diǎn)總數(shù)又 可表示為： n=n1+2n2+1 (式子2) 由式子1和式子2得到： no=n2+1 【性質(zhì)4】具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為floor(log2n)+1 證明：假設(shè)深度為k，則根據(jù)完

23、全二叉樹的定義，前面k-1層一定是滿 的，所以n2k 1 -1。但n又要滿足n=2k -1。所以， 2k11n=2k -1。變換一下為2k1=n2k。 以2為底取對(duì)數(shù)得到：k-1=log2n1,則其父結(jié)點(diǎn)編號(hào)為i/2 。 如果2*in，則結(jié)點(diǎn)i無(wú)左孩子（當(dāng)然也無(wú)右孩子，為什么？即結(jié) 點(diǎn)i為葉結(jié)點(diǎn)）；否則左孩子編號(hào)為2*i。 如果2*i+1n，則結(jié)點(diǎn)i無(wú)右孩子；否則右孩子編號(hào)為2*i+1。 證明：略，我們只要驗(yàn)證一下即可?？偨Y(jié)如圖： 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，即單鏈表結(jié)構(gòu)或雙鏈表結(jié)構(gòu)（同樹）。數(shù)據(jù)結(jié)構(gòu)修 改如下： typedef struct node; typedef n

24、ode *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; 如左圖的一棵二叉樹用單鏈表就可 以表示成右邊的形式： 順序存儲(chǔ)結(jié)構(gòu)，即幾個(gè)數(shù)組加一個(gè)指針變量。數(shù)據(jù)結(jié)構(gòu)修改如下： const int n = 10; char datan; char lchildn; char rchildn; int bt; /根結(jié)點(diǎn)指

25、針 二叉樹在處理表達(dá)式時(shí)經(jīng)常用到，一般用葉結(jié)點(diǎn)表示運(yùn)算元，分 支結(jié)點(diǎn)表示運(yùn)算符。這樣的二叉樹稱為表達(dá)式樹。如現(xiàn)在有一個(gè)表達(dá) 式：（a+b/c）*(d-e)?？梢杂靡詧D表示： 數(shù)據(jù)結(jié)構(gòu)定義如下： 按表達(dá)式的書寫順序逐個(gè)編號(hào)，分別為1.9，注意表達(dá)式中的所 有括號(hào)在樹中是不出現(xiàn)的，因?yàn)楸磉_(dá)式樹本身就是有序的。葉結(jié)點(diǎn)的 左右子樹均為空（用0表示）。 char data9 = a, +, b, /, c, *, d, -, e; int lchild9 = 0,1,0,3,0,2,0,7,0; int rchild9 = 0,4,0,5,0,8,0,9,0; int bt; /根結(jié)點(diǎn)指針,初值=6，指

26、向* 二叉樹的操作: 最重要的是遍歷二叉樹，但基礎(chǔ)是建一棵二叉樹 、插入一個(gè)結(jié)點(diǎn)到二叉樹中、刪除結(jié)點(diǎn)或子樹等。 【例3-3】醫(yī)院設(shè)置 【問(wèn)題描述】 設(shè)有一棵二叉樹（如圖3-8，其中圈中的數(shù)字表示結(jié)點(diǎn)中居民的人口，圈 邊上數(shù)字表示結(jié)點(diǎn)編號(hào)?，F(xiàn)在要求在某個(gè)結(jié)點(diǎn)上建立一個(gè)醫(yī)院，使所有居民 所走的路程之和為最小，同時(shí)約定，相鄰結(jié)點(diǎn)之間的距離為1。就本圖而言， 若醫(yī)院建在1處，則距離和=4+12+2*20+2*40=136；若醫(yī)院建在3處，則距離和 =4*2+13+20+40=81 【輸入格式】 輸入文件名為hospital.in，其中第一行一個(gè)整數(shù)n，表示樹的結(jié)點(diǎn)數(shù)（ n=100）。接下來(lái)的n行每行描

27、述了一個(gè)結(jié)點(diǎn)的狀況，包含三個(gè)整數(shù)，整數(shù)之 間用空格（一個(gè)或多個(gè)）分隔，其中：第一個(gè)數(shù)為居民人口數(shù)；第二個(gè)數(shù)為 左鏈接，為0表示無(wú)鏈接；第三個(gè)數(shù)為右鏈接，為0表示無(wú)鏈接。 【輸出格式】 輸出文件名為hospital.out，該文件只有一個(gè)整數(shù)，表示最小距離和。 【樣例輸入】 5 13 2 3 4 0 0 12 4 5 20 0 0 40 0 0 【樣例輸出】 81 13 412 2040 1 2 3 4 5 【算法分析】 這是一道簡(jiǎn)單的二叉樹應(yīng)用問(wèn)題，問(wèn)題中的結(jié)點(diǎn)數(shù)并不多，數(shù)據(jù) 規(guī)模也不大，采用鄰接矩陣存儲(chǔ)，用Floyed法求出任意兩結(jié)點(diǎn)之間的 最短路徑長(zhǎng)，然后窮舉醫(yī)院可能建立的n個(gè)結(jié)點(diǎn)位置，找

28、出一個(gè)最小 距離的位置即可。當(dāng)然也可以用雙鏈表結(jié)構(gòu)或帶父結(jié)點(diǎn)信息的數(shù)組存 儲(chǔ)結(jié)構(gòu)來(lái)解決，但實(shí)際操作稍微麻煩了一點(diǎn)。 【參考程序】 #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+) for(j = 1 ; j = n ; j+)

29、 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é)點(diǎn)之間的最短路徑 for(i = 1 ; i = n ; i+) if(i != k) for(j = 1 ; j = n ; j+) if(i != j min = 0 x7fffffff; for(i = 1 ; i = n ; i+) /窮舉醫(yī)院建在N個(gè)結(jié)點(diǎn)，找出最短距離 total = 0; for(j = 1 ; j = n ; j+) tota

30、l += gij * aj; if(total min) min = total; cout min endl; return 0; 【后記】 在各種競(jìng)賽中經(jīng)常遇到這樣的問(wèn)題：N-1條公路連接著N個(gè)城市， 從每個(gè)城市出發(fā)都可以通過(guò)公路到達(dá)其它任意的城市。每個(gè)城市里面 都有一定數(shù)量的居民，但是數(shù)量并不一定相等，每條公路的長(zhǎng)度也不 一定相等。X公司（或者是政府）決定在某一個(gè)城市建立一個(gè)醫(yī)院/酒 廠/游樂(lè)場(chǎng)，問(wèn)：將它建在哪里，可以使得所有的居民移動(dòng)到那 里的總耗費(fèi)最小？這種題目都是本題的“變型”，一般稱為“樹的中 心點(diǎn)問(wèn)題”。除了簡(jiǎn)單的窮舉法外，還有更好的時(shí)間復(fù)雜度為O(n)的 算法，我們講在后面的

31、章節(jié)中繼續(xù)討論。 遍歷二叉樹遍歷二叉樹 在二叉樹的應(yīng)用中，常常要求在樹中查找具有某種特征的結(jié)點(diǎn)， 或者對(duì)全部結(jié)點(diǎn)逐一進(jìn)行某種處理。這就是二叉樹的遍歷問(wèn)題。所謂 二叉樹的遍歷是指按一定的規(guī)律和次序訪問(wèn)樹中的各個(gè)結(jié)點(diǎn)，而且每 個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次?！霸L問(wèn)”的含義很廣，可以是對(duì)結(jié)點(diǎn)作各種處 理，如輸出結(jié)點(diǎn)的信息等。遍歷一般按照從左到右的順序，共有3種 遍歷方法，先（根）序遍歷，中（根）序遍歷，后（根）序遍歷。 先序遍歷的操作定義如下： 若二叉樹為空，則空操作，否則 訪問(wèn)根結(jié)點(diǎn) 先序遍歷左子樹 先序遍歷右子樹 void preorder(tree bt) /先序遍歷根結(jié)點(diǎn)為bt的二叉樹的遞歸算法 if(

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

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

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

35、除結(jié)點(diǎn)或子樹等。 1、建立一棵二叉樹 void pre_crt(tree ch = getchar(); /二叉樹的單鏈表存儲(chǔ)結(jié)構(gòu)，bt為指向根結(jié)點(diǎn)的指針,$表示空樹 if(ch != $) bt = new node; /建根結(jié)點(diǎn) bt-data = ch; pre_crt(bt-lchild); /建左子樹 pre_crt(bt-rchild); /建右子樹 else bt = NULL; 2、刪除二叉樹 void dis(tree /刪左子樹 dis(bt-rchild); /刪右子樹 delete bt; /釋放父結(jié)點(diǎn) 3插入一個(gè)結(jié)點(diǎn)到排序二叉樹中 void insert(tree e

36、lse if(n bt-data) insert(bt-rchild, n); else bt = new node; /新開(kāi)一個(gè)空間 bt-data = n; bt-lchild = bt-rchild = NULL; 4在排序二叉樹中查找一個(gè)數(shù)，找到返回該結(jié)點(diǎn),否則返回NULL tree findn(tree bt, int n) /在二叉樹中查找一個(gè)數(shù)，找到返回該結(jié)點(diǎn),否則返回NULL。 if(bt) if(n data) findn(bt-lchild, n); else if(n bt-data) findn(bt-rchild, n); else return bt; else r

37、eturn NULL; 5用嵌套括號(hào)表示法輸出二叉樹 void print(tree bt) /用嵌套括號(hào)表示法輸出二叉樹 if(bt) cout data; if(bt-lchild | bt-rchild) cout lchild); if(bt-rchild) cout rchild); cout ); 下面我們換個(gè)角度考慮這個(gè)問(wèn)題，從二叉樹的遍歷已經(jīng)知道，任 意一棵二叉樹結(jié)點(diǎn)的先序序列和中序序列是唯一的。反過(guò)來(lái)，給定結(jié) 點(diǎn)的先序序列和中序序列，能否確定一棵二叉樹呢？又是否唯一呢？ 由定義，二叉樹的先序遍歷是先訪問(wèn)根結(jié)點(diǎn)，再遍歷左子樹，最 后遍歷右子樹。即在結(jié)點(diǎn)的先序序列中，第一個(gè)結(jié)點(diǎn)必

38、是根，假設(shè)為 root。再結(jié)合中序遍歷，因?yàn)橹行虮闅v是先遍歷左子樹，再訪問(wèn)根， 最后遍歷右子樹。所以結(jié)點(diǎn)root正好把中序序列分成了兩部分，root 之前的應(yīng)該是左子樹上的結(jié)點(diǎn)，root之后的應(yīng)該是右子樹上的結(jié)點(diǎn)。 依次類推，便可遞歸得到整棵二叉樹。 結(jié)論：已知先序序列和中序序列可以確定出二叉樹； 已知中序序列和后序序列也可以確定出二叉樹； 但，已知先序序列和后序序列卻不可以確定出二叉樹；為什么？舉個(gè) 3個(gè)結(jié)點(diǎn)的反例。 例如：已知結(jié)點(diǎn)的先序序列為ABCDEFG，中序序列為CBEDAFG。構(gòu)造出 二叉樹。過(guò)程見(jiàn)下圖： 【例3-4】求后序遍歷 【問(wèn)題描述】 輸入一棵二叉樹的先序和中序遍歷序列，輸出

39、其后序遍歷序列。 【輸入格式】 輸入文件為tree.in，共兩行，第一行一個(gè)字符串，表示樹的先序遍 歷，第二行一個(gè)字符串，表示樹的中序遍歷。樹的結(jié)點(diǎn)一律用小寫 字母表示。 【輸出格式】 輸出文件為tree.out，僅一行，表示樹的后序遍歷序列。 【樣例輸入】 abdec dbeac 【樣例輸出】 debca 【參考程序】 #include #include #include using namespace std; string s1, s2; void calc(int l1, int r1, int l2, int r2) int m = s2.find(s1l1); if(m l2) c

40、alc(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】擴(kuò)展二叉樹 【問(wèn)題描述】 由于先序、中序和后序序列中的任一個(gè)都不能唯一確定一棵二叉樹， 所以對(duì)二叉樹做如下處理，將二叉樹的空結(jié)點(diǎn)用補(bǔ)齊，如圖所示。 我們把這樣處理后的二叉樹稱為原二叉樹的擴(kuò)展二叉樹，擴(kuò)展二叉樹 的先序和后序序列能唯一確定其二叉樹。 現(xiàn)給出擴(kuò)展二叉

41、樹的先序序列，要求輸出其中序和后序序列。 【輸入樣例】tree_b.in ABD.EF.G.C. 【輸出樣例】tree_b.out DBFEGAC DFGEBCA #include #include #include #include #include #include using namespace std; typedef struct node; typedef node *tree; struct node char data; tree lchild, rchild; ; tree bt; int i; string s; void build(tree bt = new node;

42、 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(bt-rchild); cout data; int main() freopen(tree_b.in, r, stdin); freopen(tree_b.o

43、ut, w, stdout); cin s; i = -1; build(bt); printzx(bt); cout endl; printhx(bt); cout 1)個(gè)結(jié)點(diǎn)的二叉樹可以看成是由一個(gè)根 結(jié)點(diǎn)、一棵具有i個(gè)結(jié)點(diǎn)的左子樹和一棵具有n-i-1個(gè)結(jié)點(diǎn)的右子樹組 成，其中0=i=n-1, 由此不難得出下列遞歸公式： 我們可以利用生成函數(shù)討論這個(gè)遞歸公式，得出：Bn= 類推到具有n個(gè)結(jié)點(diǎn)、互不相似的多叉樹的數(shù)目Tn 由于樹可以轉(zhuǎn)換成二叉樹且轉(zhuǎn)換之后的根節(jié)點(diǎn)沒(méi)有右兒子，所以，可 以推出：Tn=Bn-1。 【課堂練習(xí)課堂練習(xí)】 1、一棵完全二叉樹的結(jié)點(diǎn)總數(shù)為18，其葉結(jié)點(diǎn)數(shù)為 。 A.7個(gè)

44、 B.8個(gè) C.9個(gè) D.10個(gè) 2、 二叉樹第10層的結(jié)點(diǎn)數(shù)的最大數(shù)目為 。 A.10 B.100 C.512 D.1024 3、一棵深度為K的滿二叉樹有（ ）個(gè)結(jié)點(diǎn)。 A.2K-1 B.2K C.2*K D.2*K-1 4、對(duì)任何一棵二叉樹T，設(shè)n0、n1、n2分別是度數(shù)為0、1、2的頂點(diǎn)數(shù)， 則下列判斷中正確的是 。 A.n0=n2+1 B.n1=n0+1 C. n2=n0+1 D.n2=n0+1 5、一棵n個(gè)節(jié)點(diǎn)的完全二叉樹，則該二叉樹的高度h為( )。 A.n/2 B.log(n) C.log(n)/2 D. 6、一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是 。 A.250

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

46、、設(shè)樹T的高度為4，其中度為1、2、3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4、2、1、 1，則T中的葉子數(shù)為 。 A.5 B.6 C.7 D.8 12、一棵樹T有2個(gè)度數(shù)為2的結(jié)點(diǎn)、有1個(gè)度數(shù)為3的結(jié)點(diǎn)、有3個(gè)度數(shù)為4 的結(jié)點(diǎn)，那么樹T有（ ）個(gè)樹葉。 A.14 B.6 C.18 D.7 13、某二叉樹中序序列為abcdefg，后序序列為bdcafge，則前序序列是 。 A.egfacbd B.eacbdgf C.eagcfbd D.以上 答案都不對(duì) 14、已知某二叉樹的中序遍歷序列是debac，后序遍歷序列是dabec，則 它的前序遍歷序列是 。 A.a c b e d B.d e c a b C.d e

47、a b c D.c e d b a 15、一顆二叉樹的中序遍歷序列為DGBAECHF，后序遍歷序列為GDBEHFCA ，則前序遍歷序列是 。 A. ABCDFGHE B. ABDGCEFH C. ACBGDHEF D. ACEFHBGD 16、已知一棵二叉樹的前序序列為ABDEGCFH，中序序列為DBGEACHF，則 該二叉樹的層次序列為 。 A.GEDHFBCA B.DGEBHFCA C.ABCDEFGH D.ACBFEDHG 17、已知一棵二叉樹的前序遍歷結(jié)果為ABDECFHJIG，中序遍歷的結(jié)果為 DBEAJHFICG，則這棵二叉樹的深度為 。 A.3 B.4 C.5 D.6 18、二叉

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

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

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

51、19、該題答案是（D），本題主要考察學(xué)生怎樣將中綴表達(dá)式 轉(zhuǎn)換為后綴表達(dá)式。可以先畫出該二叉樹，對(duì)其進(jìn)行后根遍歷 即為答案。 【上機(jī)練習(xí)上機(jī)練習(xí)】 1、小球(DROP) 【問(wèn)題描述】 許多的小球一個(gè)一個(gè)的從一棵滿二叉樹上掉下來(lái)組成FBT（Full Binary Tree，滿二叉樹），每一時(shí)間，一個(gè)正在下降的球第一個(gè)訪 問(wèn)的是非葉子節(jié)點(diǎn)。然后繼續(xù)下降時(shí)，或者走右子樹，或者走左子樹 ，直到訪問(wèn)到葉子節(jié)點(diǎn)。決定球運(yùn)動(dòng)方向的是每個(gè)節(jié)點(diǎn)的布爾值。最 初，所有的節(jié)點(diǎn)都是FALSE，當(dāng)訪問(wèn)到一個(gè)節(jié)點(diǎn)時(shí)，如果這個(gè)節(jié)點(diǎn)是 FALSE，則這個(gè)球把它變成TRUE，然后從左子樹走，繼續(xù)它的旅程。 如果節(jié)點(diǎn)是TRUE，

52、則球也會(huì)改變它為FALSE，而接下來(lái)從右子樹走。 滿二叉樹的標(biāo)記方法如下圖。 因?yàn)樗械墓?jié)點(diǎn)最初為FALSE，所以第一個(gè)球?qū)?huì)訪問(wèn)節(jié)點(diǎn)1，節(jié) 點(diǎn)2和節(jié)點(diǎn)4，轉(zhuǎn)變節(jié)點(diǎn)的布爾值后在在節(jié)點(diǎn)8停止。第二個(gè)球?qū)?huì)訪 問(wèn)節(jié)點(diǎn)1、3、6,在節(jié)點(diǎn)12停止。明顯地，第三個(gè)球在它停止之前，會(huì) 訪問(wèn)節(jié)點(diǎn)1、2、5，在節(jié)點(diǎn)10停止。 現(xiàn)在你的任務(wù)是，給定FBT的深度D，和I，表示第I個(gè)小球下落，你 可以假定I不超過(guò)給定的FBT的葉子數(shù)，寫一個(gè)程序求小球停止時(shí)的葉 子序號(hào)。 【輸入格式】 輸入文件僅一行包含兩個(gè)用空格隔開(kāi)的整數(shù)D和I。其中2=D=20 ，1=I=524288。 【輸出格式】 對(duì)應(yīng)輸出第I個(gè)小球下落停止時(shí)

53、的葉子序號(hào)。 【輸入樣例】DROP.IN 4 2 【輸出樣例】DROP.OUT 12 2、二叉樹遍歷(flist) 【問(wèn)題描述】 樹和二叉樹基本上都有先序、中序、后序、按層遍歷等遍歷順序， 給定中序和其它一種遍歷的序列就可以確定一棵二叉樹的結(jié)構(gòu)。 假定一棵二叉樹一個(gè)結(jié)點(diǎn)用一個(gè)字符描述，現(xiàn)在給出中序和按層遍 歷的字符串，求該樹的先序遍歷字符串。 【輸入格式】 輸入文件flist.in共兩行，每行是由字母組成的字符串（一行的每 個(gè)字符都是唯一的），分別表示二叉樹的中序遍歷和按層遍歷的序列 。 【輸出格式】 輸出文件flist.out就一行，表示二叉樹的先序序列。 【輸入樣例】flist.in DB

54、EAC ABCDE 【輸出樣例】flist.out ABDEC 3、FBI樹(fbi) 【問(wèn)題描述】 我們可以把由“0”和“1”組成的字符串分為三類：全“0”串 稱為B串，全“1”串稱為I串，既含“0”又含“1”的串則稱為F串。 FBI樹是一種二叉樹 二叉樹：二叉樹是結(jié)點(diǎn)的有限集合，這個(gè) 集合或?yàn)榭占蛴梢粋€(gè)根結(jié)點(diǎn)和兩棵不相交的二叉樹組成。這兩棵 不相交的二叉樹分別稱為這個(gè)根結(jié)點(diǎn)的左子樹和右子樹。，它的結(jié) 點(diǎn)類型也包括F結(jié)點(diǎn)，B結(jié)點(diǎn)和I結(jié)點(diǎn)三種。由一個(gè)長(zhǎng)度為2N的“01” 串S可以構(gòu)造出一棵FBI樹T，遞歸的構(gòu)造方法如下： T的根結(jié)點(diǎn)為R，其類型與串S的類型相同； 若串S的長(zhǎng)度大于1，將串S

55、從中間分開(kāi)，分為等長(zhǎng)的左右子串S1 和S2；由左子串S1構(gòu)造R的左子樹T1，由右子串S2構(gòu)造R的右子樹T2。 現(xiàn)在給定一個(gè)長(zhǎng)度為2N的“01”串，請(qǐng)用上述構(gòu)造方法構(gòu)造出一 棵FBI樹，并輸出它的后序遍歷 后序遍歷：后序遍歷是深度優(yōu)先遍 歷二叉樹的一種方法，它的遞歸定義是：先后序遍歷左子樹，再后序 遍歷右子樹，最后訪問(wèn)根。序列。 【輸入文件】 輸入文件fbi.in的第一行是一個(gè)整數(shù)N（0 = N = 10），第二 行是一個(gè)長(zhǎng)度為2N的“01”串。 【輸出文件】 輸出文件fbi.out包括一行，這一行只包含一個(gè)字符串，即FBI樹 的后序遍歷序列。 【樣例輸入】fbi.in 3 10001011 【

56、樣例輸出】fbi.out IBFBBBFIBFIIIFF 【數(shù)據(jù)規(guī)模】 對(duì)于40%的數(shù)據(jù)，N = 2； 對(duì)于全部的數(shù)據(jù)，N = 10。 4、二叉樹輸出(btout) 【問(wèn)題描述】 樹的凹入表示法主要用于樹的屏幕或打印輸出，其表示的基本思 想是兄弟間等長(zhǎng)，一個(gè)結(jié)點(diǎn)要不小于其子結(jié)點(diǎn)的長(zhǎng)度。二叉樹也可以 這樣表示，假設(shè)葉結(jié)點(diǎn)的長(zhǎng)度為1，一個(gè)非葉結(jié)點(diǎn)的長(zhǎng)并等于它的左 右子樹的長(zhǎng)度之和。 一棵二叉樹的一個(gè)結(jié)點(diǎn)用一個(gè)字母表示（無(wú)重復(fù)），輸出時(shí)從根 結(jié)點(diǎn)開(kāi)始： 每行輸出若干個(gè)結(jié)點(diǎn)字符（相同字符的個(gè)數(shù)等于該結(jié)點(diǎn)長(zhǎng)度）， 如果該結(jié)點(diǎn)有左子樹就遞歸輸出左子樹； 如果該結(jié)點(diǎn)有右子樹就遞歸輸出右子樹。 假定一棵二叉樹

57、一個(gè)結(jié)點(diǎn)用一個(gè)字符描述，現(xiàn)在給出先序和中序 遍歷的字符串，用樹的凹入表示法輸出該二叉樹。 【輸入格式】 輸入文件btout.in共兩行，每行是由字母組成的字符串（一行的 每個(gè)字符都是唯一的），分別表示二叉樹的先序遍歷和中序遍歷的序 列。 【輸出格式】 輸出文件btout.out的行數(shù)等于該樹的結(jié)點(diǎn)數(shù)，每行的字母相同。 【輸入樣例】btout.in ABCDEFG CBDAFEG 【輸出樣例】btout.out AAAA BB C D EE F G 5、查找二叉樹(tree_c.cpp) 【問(wèn)題描述】 已知一棵二叉樹用鄰接表結(jié)構(gòu)存儲(chǔ)，中序查找二叉樹中值為x的結(jié)點(diǎn) ，并指出是第幾個(gè)結(jié)點(diǎn)。例：如圖二

58、叉樹的數(shù)據(jù)文件的數(shù)據(jù)格式如下 7 15 5 2 3 12 4 5 10 0 0 29 0 0 15 6 7 8 0 0 23 0 0 第一行n為二叉樹的結(jié) 點(diǎn)個(gè)樹，n=100；第二行x 表示要查找的結(jié)點(diǎn)的值；以 下第一列數(shù)據(jù)是各結(jié)點(diǎn)的值 ，第二列數(shù)據(jù)是左兒子結(jié)點(diǎn) 編號(hào)，第三列數(shù)據(jù)是右兒子 結(jié)點(diǎn)編號(hào)。 輸出一個(gè)數(shù)即查找的結(jié) 點(diǎn)編號(hào)。 本例的輸出樣例: 4 6、對(duì)稱二叉樹 【問(wèn)題描述】 如果二叉樹的左右子樹的結(jié)構(gòu)是對(duì)稱的，即兩棵子樹皆為空，或 者皆不空，則稱該二叉樹是對(duì)稱的。編程判斷給定的二叉樹是否對(duì)稱 . 例：如下圖中的二叉樹T1是對(duì)稱的，T2是不對(duì)稱的。 二叉樹用順序結(jié)構(gòu)給出，若讀到#則為空，

59、二叉樹T1=ABCDE， T2=ABCD#E，如果二叉樹是對(duì)稱的，輸出“Yes”,反之輸出“No”。 【輸入樣例】tree_c.in ABCDE 【輸出樣例】tree_c.out Yes 第三節(jié)第三節(jié) 堆及其應(yīng)用堆及其應(yīng)用 一、預(yù)備知識(shí)一、預(yù)備知識(shí) 完全二叉樹完全二叉樹： 如果一棵深度為K二叉樹，1至k-1層的 結(jié)點(diǎn)都是滿的，即滿足2i-1，只有最下面的 一層的結(jié)點(diǎn)數(shù)小于2i-1，并且最下面一層的 結(jié)點(diǎn)都集中在該層最左邊的若干位置，則 此二叉樹稱為完全二叉樹。 二、堆的定義二、堆的定義 堆結(jié)構(gòu)是一種數(shù)組對(duì)象，它可以被視 為一棵完全二叉樹。樹中每個(gè)結(jié)點(diǎn)與數(shù)組 中存放該結(jié)點(diǎn)中值的那個(gè)元素相對(duì)應(yīng)，如

60、 下圖： 三、堆的性質(zhì)三、堆的性質(zhì) 設(shè)數(shù)組A的長(zhǎng)度為len，二叉樹的結(jié)點(diǎn) 個(gè)數(shù)為size，sizelen，則Ai存儲(chǔ)二叉 樹中編號(hào)為i的結(jié)點(diǎn)值（1isize），而 Asize以后的元素并不屬于相應(yīng)的堆，樹 的根為A1，并且利用完全二叉樹的性質(zhì)， 我們很容易求第i個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn) （parent(i)）、左孩子結(jié)點(diǎn)(left(i)、 右孩子結(jié)點(diǎn)(right(i)的下標(biāo)了,分別為： i/2、2i、2i+1； 更重要的是，堆具有這樣一個(gè)性質(zhì)， 對(duì)除根以外的每個(gè)結(jié)點(diǎn)i， Aparent(i)Ai。即除根結(jié)點(diǎn)以外， 所有結(jié)點(diǎn)的值都不得超過(guò)其父結(jié)點(diǎn)的值， 這樣就推出，堆中的最大元素存放在根結(jié) 點(diǎn)中，且每一結(jié)