1、樹及其運(yùn)用樹及其運(yùn)用樹的遞歸定義如下：樹的遞歸定義如下： 樹是樹是n(n0)n(n0)個(gè)結(jié)點(diǎn)的有限集，這個(gè)集合滿足以下條件：個(gè)結(jié)點(diǎn)的有限集，這個(gè)集合滿足以下條件： 有且僅有一個(gè)結(jié)點(diǎn)沒有前驅(qū)父親結(jié)點(diǎn)，該結(jié)點(diǎn)稱為樹有且僅有一個(gè)結(jié)點(diǎn)沒有前驅(qū)父親結(jié)點(diǎn)，該結(jié)點(diǎn)稱為樹的根；的根； 除根外，其他的每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)；除根外，其他的每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)； 除根外，每一個(gè)結(jié)點(diǎn)都經(jīng)過獨(dú)一的途徑連到根上否那么除根外，每一個(gè)結(jié)點(diǎn)都經(jīng)過獨(dú)一的途徑連到根上否那么有環(huán)。這條途徑由根開場(chǎng)，而未端就在該結(jié)點(diǎn)上，且除根有環(huán)。這條途徑由根開場(chǎng)，而未端就在該結(jié)點(diǎn)上，且除根以外，途徑上的每一個(gè)結(jié)點(diǎn)都是前一個(gè)結(jié)點(diǎn)的后繼兒子

2、結(jié)以外，途徑上的每一個(gè)結(jié)點(diǎn)都是前一個(gè)結(jié)點(diǎn)的后繼兒子結(jié)點(diǎn)；點(diǎn)；由上述定義可知，樹構(gòu)造沒有封鎖的回路。由上述定義可知，樹構(gòu)造沒有封鎖的回路。 e e，f f，s s，m m，o o，n n，j j，u u為葉結(jié)點(diǎn)。為葉結(jié)點(diǎn)。根結(jié)點(diǎn)到每一個(gè)分支結(jié)根結(jié)點(diǎn)到每一個(gè)分支結(jié)點(diǎn)或葉結(jié)點(diǎn)的途徑是獨(dú)點(diǎn)或葉結(jié)點(diǎn)的途徑是獨(dú)一的。從根一的。從根r r到結(jié)點(diǎn)到結(jié)點(diǎn)i i的的獨(dú)一途徑為獨(dú)一途徑為rctircti。二、樹的表示方法和存儲(chǔ)構(gòu)造二、樹的表示方法和存儲(chǔ)構(gòu)造1 1、樹的表示方法、樹的表示方法樹的表示方法普通有兩種：樹的表示方法普通有兩種：自然界的樹形表示法：用結(jié)點(diǎn)和邊表示樹，例自然界的樹形表示法：用結(jié)點(diǎn)和邊表示樹，例

3、如上圖采用的就是自然界的樹形表示法。樹形表示法如上圖采用的就是自然界的樹形表示法。樹形表示法普通用于分析問題。普通用于分析問題。. .括號(hào)表示法：括號(hào)表示法： 先將根結(jié)點(diǎn)放入一對(duì)圓括號(hào)中，然后把先將根結(jié)點(diǎn)放入一對(duì)圓括號(hào)中，然后把它的子樹按由左而右的順序放入括號(hào)中，而它的子樹按由左而右的順序放入括號(hào)中，而對(duì)子樹也采用同樣方法處置：同層子樹與它對(duì)子樹也采用同樣方法處置：同層子樹與它的根結(jié)點(diǎn)用圓括號(hào)括起來，同層子樹之間用的根結(jié)點(diǎn)用圓括號(hào)括起來，同層子樹之間用逗號(hào)隔開，最后用閉括號(hào)括起來。例如圖可逗號(hào)隔開，最后用閉括號(hào)括起來。例如圖可寫成如下方式寫成如下方式(A(B(E(K,L),F),C(G),D(

4、H(M),I,J) (A(B(E(K,L),F),C(G),D(H(M),I,J) 優(yōu)點(diǎn)優(yōu)點(diǎn): :易于保管易于保管; ;缺陷缺陷: :不直觀不直觀. .2 2、樹的存儲(chǔ)構(gòu)造、樹的存儲(chǔ)構(gòu)造樹的存儲(chǔ)構(gòu)造普通有兩種樹的存儲(chǔ)構(gòu)造普通有兩種. .靜態(tài)的記錄數(shù)組。一切結(jié)點(diǎn)存儲(chǔ)在一個(gè)數(shù)靜態(tài)的記錄數(shù)組。一切結(jié)點(diǎn)存儲(chǔ)在一個(gè)數(shù)組中組中, ,數(shù)組元素為記錄類型數(shù)組元素為記錄類型, ,包括數(shù)據(jù)域和長(zhǎng)度包括數(shù)據(jù)域和長(zhǎng)度為為n(nn(n為樹的度為樹的度) )的數(shù)組的數(shù)組, ,分別存儲(chǔ)該結(jié)點(diǎn)的每分別存儲(chǔ)該結(jié)點(diǎn)的每一個(gè)兒子的下標(biāo)一個(gè)兒子的下標(biāo)#define n #define n 樹的度；樹的度；#define max #d

5、efine max 結(jié)點(diǎn)數(shù)的上限；結(jié)點(diǎn)數(shù)的上限；struct treetypestruct treetype int data; / int data; /數(shù)據(jù)域數(shù)據(jù)域 int chn int chn； / /指向各兒子的下標(biāo)指向各兒子的下標(biāo) treetype treemaxtreetype treemax； / /樹數(shù)組樹數(shù)組12345678910111213DataParent (1).前序根遍歷：先訪問根結(jié)點(diǎn)，再?gòu)淖蟮接野凑涨靶蛩枷氡闅v各棵子樹。如上圖前序遍歷的結(jié)果為：125634789； 詳細(xì)步驟深度優(yōu)先遍歷.讀入數(shù)據(jù) cinn; for(i=1;itreei1treei2;.尋覓根節(jié)

6、點(diǎn) root=1; while(treeroot2!=0)root=treeroot2; /尋覓根節(jié)點(diǎn) 3.先序遍歷樹 void dfs(int k)/深度優(yōu)先遍歷 couttreek1“ ; /輸出當(dāng)前節(jié)點(diǎn) for(i=1;i=n;i+) if(treei2=k)dfs(i); /遍歷當(dāng)前節(jié)點(diǎn)孩子 1、樹的統(tǒng)計(jì)、樹的統(tǒng)計(jì)輸入森林中的結(jié)點(diǎn)關(guān)系，統(tǒng)計(jì)森林中樹的數(shù)量，輸出樹的根。輸入森林中的結(jié)點(diǎn)關(guān)系，統(tǒng)計(jì)森林中樹的數(shù)量，輸出樹的根。輸入：輸入：第一行：第一行：n：結(jié)點(diǎn)數(shù)量；：結(jié)點(diǎn)數(shù)量；k：邊數(shù)；：邊數(shù)；n,k=100以下以下k行：每行兩個(gè)結(jié)點(diǎn)編號(hào)：行：每行兩個(gè)結(jié)點(diǎn)編號(hào)：i，j：i是是j的父結(jié)點(diǎn)的父

7、結(jié)點(diǎn)(I,j=100)。輸出：輸出：第一行：樹的數(shù)量。第一行：樹的數(shù)量。第二行：依次輸出森林中樹的根結(jié)點(diǎn)編號(hào)從小到大。第二行：依次輸出森林中樹的根結(jié)點(diǎn)編號(hào)從小到大。樣例輸入：樣例輸入：9 71 22 34 64 57 89 1 9 4輸出：輸出：27 9運(yùn)用運(yùn)用:#includeusing namespace std;int n,m,tree101,ans10;int main() int i,x,y,root,maxroot,sum=0,j=0,max=0; cinnm; memset(tree,0,sizeof(tree);/默許根標(biāo)志是本身默許根標(biāo)志是本身,各自是獨(dú)各自是獨(dú)立的一棵樹立的

8、一棵樹 for(i=1;ixy;treey=x; for(i=1;i=n;i+) if(treei=0)ans+j=i;sum+; coutsumendl; for(i=1;i=j;i+) coutansi ; return 0;2、找樹根和孩子、找樹根和孩子treea.pas給定一棵樹，輸出樹的根給定一棵樹，輸出樹的根root，孩子最多的結(jié)點(diǎn)，孩子最多的結(jié)點(diǎn)max以及他以及他的孩子。的孩子。輸入：輸入：第一行：第一行：n結(jié)點(diǎn)個(gè)數(shù)，結(jié)點(diǎn)個(gè)數(shù)，m邊數(shù)。邊數(shù)。以下以下m行；每行兩個(gè)結(jié)點(diǎn)行；每行兩個(gè)結(jié)點(diǎn)x和和y，表示，表示y是是x的孩子。的孩子。輸出：輸出：第一行：樹根：第一行：樹根：root。第二

9、行：孩子最多的結(jié)點(diǎn)第二行：孩子最多的結(jié)點(diǎn)max。第三行：第三行：max的孩子。的孩子。樣例輸入：樣例輸入：8 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,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)找孩子最多的結(jié)點(diǎn)

10、 sum=0; for(j=1;jMax)Max=sum;maxroot=i; coutrootendlmaxrootendl; if(treei=maxroot)couti ; return 0; 一、二叉樹的概念一、二叉樹的概念 二叉樹的特點(diǎn)二叉樹的特點(diǎn): :是每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，且其子樹有是每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，且其子樹有左右之分有序樹，次序不能恣意顛倒。左右之分有序樹，次序不能恣意顛倒。1 1、二叉樹的遞歸定義和根本形狀、二叉樹的遞歸定義和根本形狀 二叉樹是以結(jié)點(diǎn)為元素的有限集，它或者為空，或者滿足二叉樹是以結(jié)點(diǎn)為元素的有限集，它或者為空，或者滿足以下條件：以下條件： 有一個(gè)特定

11、的結(jié)點(diǎn)稱為根；有一個(gè)特定的結(jié)點(diǎn)稱為根； 余下的結(jié)點(diǎn)分為互不相交的子集余下的結(jié)點(diǎn)分為互不相交的子集L L和和R R，其中，其中L L是根的左是根的左子樹；子樹；R R是根的右子樹；是根的右子樹；L L和和R R又是二叉樹；又是二叉樹； 由此定義可以看出，一個(gè)二叉樹中的由此定義可以看出，一個(gè)二叉樹中的每個(gè)結(jié)點(diǎn)只能含有每個(gè)結(jié)點(diǎn)只能含有0 0、 1 1或或2 2個(gè)孩子個(gè)孩子二叉樹和樹區(qū)別：二叉樹和樹區(qū)別： 樹的每一個(gè)結(jié)點(diǎn)可以有恣意多個(gè)孩子，而二叉樹中每個(gè)樹的每一個(gè)結(jié)點(diǎn)可以有恣意多個(gè)孩子，而二叉樹中每個(gè)結(jié)點(diǎn)的孩子數(shù)不能超越結(jié)點(diǎn)的孩子數(shù)不能超越2 2； 樹的子樹可以不分次序除有序樹外；而二叉樹的子樹的子樹

12、可以不分次序除有序樹外；而二叉樹的子樹有左右之分。左兒子和右兒子。樹有左右之分。左兒子和右兒子。以下圖列出二叉樹的五種根本形狀：以下圖列出二叉樹的五種根本形狀：(a)(b)3 3、二叉樹的三個(gè)主要性質(zhì)、二叉樹的三個(gè)主要性質(zhì)性質(zhì)性質(zhì)1 1：在二叉樹的第：在二叉樹的第i ii1i1層上，最多有層上，最多有2i-12i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)性質(zhì)性質(zhì)2 2：在深度為：在深度為k(k1)k(k1)的二叉樹中最多有的二叉樹中最多有2k-12k-1個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。性質(zhì)性質(zhì)3 3：在任何二叉樹中，葉子結(jié)點(diǎn)數(shù)總比度為：在任何二叉樹中，葉子結(jié)點(diǎn)數(shù)總比度為2 2的結(jié)點(diǎn)多的結(jié)點(diǎn)多1 1。 n0=n2+1 n0=n2+1(

13、(設(shè)設(shè)n0n0為二叉樹的葉結(jié)點(diǎn)數(shù)；為二叉樹的葉結(jié)點(diǎn)數(shù)；n2n2為二叉樹中度為為二叉樹中度為2 2的結(jié)點(diǎn)數(shù)的結(jié)點(diǎn)數(shù)) )設(shè)設(shè)n0n0為二叉樹的葉結(jié)點(diǎn)數(shù)；為二叉樹的葉結(jié)點(diǎn)數(shù)；n1n1為二叉樹中度為為二叉樹中度為1 1的結(jié)點(diǎn)數(shù)；的結(jié)點(diǎn)數(shù)；n2n2為二叉樹中度為為二叉樹中度為2 2的結(jié)點(diǎn)數(shù)，顯然的結(jié)點(diǎn)數(shù)，顯然 n=n0+n1+n2 n=n0+n1+n2 1 1由于二叉樹中除了根結(jié)點(diǎn)外，其他每個(gè)結(jié)點(diǎn)都有且僅有一由于二叉樹中除了根結(jié)點(diǎn)外，其他每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)邊指向父親。設(shè)個(gè)邊指向父親。設(shè) b b為二叉樹的邊的個(gè)數(shù)，為二叉樹的邊的個(gè)數(shù)， n=b+1 n=b+1 2 2 一切這些分支同時(shí)又為度為一切這些

14、分支同時(shí)又為度為1 1和度為和度為2 2的結(jié)點(diǎn)發(fā)出的。因此的結(jié)點(diǎn)發(fā)出的。因此又有又有 b=n1+2n2 (3)b=n1+2n2 (3)由由1 1，2 2，3 3得到：得到：n0=n2+1n0=n2+1【試題分析】：假設(shè)一棵【試題分析】：假設(shè)一棵m度的樹中有度的樹中有N1個(gè)度為個(gè)度為1的頂點(diǎn)，的頂點(diǎn)，N2個(gè)度為個(gè)度為2的的頂點(diǎn)，頂點(diǎn)，N3個(gè)度為個(gè)度為3的頂點(diǎn)，的頂點(diǎn)，Nm個(gè)度為個(gè)度為m的頂點(diǎn)，求該樹中葉子頂點(diǎn)的頂點(diǎn)，求該樹中葉子頂點(diǎn)個(gè)數(shù)。個(gè)數(shù)。分析：設(shè)葉子結(jié)點(diǎn)數(shù)為分析：設(shè)葉子結(jié)點(diǎn)數(shù)為N0N0 一切結(jié)點(diǎn)數(shù)為一切結(jié)點(diǎn)數(shù)為n n，邊數(shù)，邊數(shù)( (分支為分支為b b，那么有：，那么有： n=b+1 (1

15、) n=b+1 (1) 又：又：n= N0+N1+N2+.+NM (2)n= N0+N1+N2+.+NM (2) b= N1+2N2+3N3+.+M b= N1+2N2+3N3+.+M* *NM (3)NM (3) (2),(3) (2),(3)代入代入1 1得出：得出： N0 =N2+2N3+3N4+.+(M-1)NM+1 N0 =N2+2N3+3N4+.+(M-1)NM+1(NOIP9)(NOIP9)一個(gè)高度為一個(gè)高度為h h 的二叉樹最小元素?cái)?shù)目的二叉樹最小元素?cái)?shù)目 。AA 2h+1B 2h+1B h C h C 2h-1D 2h-1D 2hE 2hE 2h-1 2h-1(NOIP8)(

16、NOIP8)按照二叉數(shù)的定義，具有按照二叉數(shù)的定義，具有3 3個(gè)結(jié)點(diǎn)的二叉樹有個(gè)結(jié)點(diǎn)的二叉樹有 種。種。 A A3 B3 B4 C4 C5 D5 D6 6(NOIP8)(NOIP8)設(shè)有一棵設(shè)有一棵k k叉樹，其中只需度為叉樹，其中只需度為0 0和和k k兩種結(jié)點(diǎn)，設(shè)兩種結(jié)點(diǎn)，設(shè)n 0 n 0 ，n k n k ，分別表示度為，分別表示度為0 0和度為和度為k k的結(jié)點(diǎn)個(gè)數(shù)，試求出的結(jié)點(diǎn)個(gè)數(shù)，試求出n 0 n 0 和和n kn k之間之間的關(guān)系的關(guān)系n 0 = n 0 = 數(shù)學(xué)表達(dá)式，數(shù)學(xué)表達(dá)式僅含數(shù)學(xué)表達(dá)式，數(shù)學(xué)表達(dá)式僅含n k n k 、k k和數(shù)字。和數(shù)字。(NOIP7).(NOIP7)

17、.一棵二叉樹的高度為一棵二叉樹的高度為h h，一切結(jié)點(diǎn)的度為，一切結(jié)點(diǎn)的度為0 0，或?yàn)?，或?yàn)? 2，那么此樹最少有那么此樹最少有( )( )個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) A)2h-1 A)2h-1 B)2h-1 B)2h-1 C)2h+1 C)2h+1 D)h+1D)h+1二、二叉樹的存儲(chǔ)構(gòu)造二、二叉樹的存儲(chǔ)構(gòu)造二叉樹的存儲(chǔ)構(gòu)造有兩種方式二叉樹的存儲(chǔ)構(gòu)造有兩種方式 順序存儲(chǔ)構(gòu)造順序存儲(chǔ)構(gòu)造(重點(diǎn)重點(diǎn)) 鏈?zhǔn)酱鎯?chǔ)構(gòu)造鏈?zhǔn)酱鎯?chǔ)構(gòu)造例如，采用數(shù)組例如，采用數(shù)組treetree存儲(chǔ)二叉樹如以下圖存儲(chǔ)二叉樹如以下圖 三、二叉樹的遍歷三、二叉樹的遍歷( (訪問訪問) ) 所謂二叉樹的遍歷是指按照一定的規(guī)律不反復(fù)地訪問二

18、叉所謂二叉樹的遍歷是指按照一定的規(guī)律不反復(fù)地訪問二叉樹中的每一個(gè)結(jié)點(diǎn)。樹中的每一個(gè)結(jié)點(diǎn)。 假設(shè)用假設(shè)用L L、D D、R R分別表示遍歷左子樹、訪問根結(jié)點(diǎn)、遍歷分別表示遍歷左子樹、訪問根結(jié)點(diǎn)、遍歷右子樹，那么對(duì)二叉樹的遍歷可以有以下六種右子樹，那么對(duì)二叉樹的遍歷可以有以下六種3!=63!=6組合：組合： LDRLDR、 LRDLRD、 DLRDLR、 DRLDRL、RDLRDL、 RLDRLD 假設(shè)再限定先左后右的次序，那么只剩下三種組合假設(shè)再限定先左后右的次序，那么只剩下三種組合 DLRDLR、LDRLDR、LRDLRD 這三種遍歷規(guī)那么分別稱為先前序遍歷、中序遍歷和這三種遍歷規(guī)那么分別稱為

19、先前序遍歷、中序遍歷和后序遍歷以根為規(guī)范。后序遍歷以根為規(guī)范。、前根序遍歷、前根序遍歷前序遍歷的規(guī)那么為：假設(shè)二叉樹為空，那么退出。否那么前序遍歷的規(guī)那么為：假設(shè)二叉樹為空，那么退出。否那么 訪問處置根結(jié)點(diǎn)；訪問處置根結(jié)點(diǎn)； 前序遍歷左子樹；前序遍歷左子樹； 前序遍歷右子樹；前序遍歷右子樹； a b d e h i c f g a b d e h i c f g中序遍歷中序遍歷中序遍歷的規(guī)那么如下：中序遍歷的規(guī)那么如下：假設(shè)二叉樹為空，那么退出；否那么假設(shè)二叉樹為空，那么退出；否那么 中序遍歷左子樹；中序遍歷左子樹； 訪問處置根結(jié)點(diǎn)；訪問處置根結(jié)點(diǎn)； 中序遍歷右子樹；中序遍歷右子樹；假設(shè)中序遍

20、歷上圖中的二叉樹，可以得到如下的中序序假設(shè)中序遍歷上圖中的二叉樹，可以得到如下的中序序列：列： d b h e i a f c g 后序遍歷后序遍歷后序遍歷的規(guī)那么如下：后序遍歷的規(guī)那么如下： 假設(shè)二叉樹為空，那么退出；否那么假設(shè)二叉樹為空，那么退出；否那么 后序遍歷左子樹；后序遍歷左子樹； 后序遍歷右子樹；后序遍歷右子樹； 訪問處置根結(jié)點(diǎn)；訪問處置根結(jié)點(diǎn)； 假設(shè)后序遍歷上圖中的二叉樹，可以得到如下的后序序假設(shè)后序遍歷上圖中的二叉樹，可以得到如下的后序序列列 d h i e b f g c a 關(guān)于前面講的表達(dá)式樹，我們可以分別用先序、中序、后序的遍歷方法得出完全不同的遍歷結(jié)果，如對(duì)于右圖3種

21、遍歷結(jié)果如下，它們正好對(duì)應(yīng)著表達(dá)式的3種表示方法。 -+a*b-cd/ef (前綴表示、波蘭式) a+b*c-d-e/f (中綴表示) abcd-*+ef/- (后綴表示、逆波蘭式)1、編程實(shí)現(xiàn)：二叉樹的遍歷、編程實(shí)現(xiàn)：二叉樹的遍歷tree1.pas建立二叉樹，然后實(shí)現(xiàn)：輸出先序遍歷、中序遍歷、建立二叉樹，然后實(shí)現(xiàn)：輸出先序遍歷、中序遍歷、后序遍歷的結(jié)果。后序遍歷的結(jié)果。輸入：第一行：結(jié)點(diǎn)個(gè)數(shù)輸入：第一行：結(jié)點(diǎn)個(gè)數(shù)n。以下行：每行。以下行：每行3個(gè)數(shù)，第個(gè)數(shù)，第一個(gè)是父親，后兩個(gè)依次為左右孩子，一個(gè)是父親，后兩個(gè)依次為左右孩子，0表示空。表示空。輸出：根、先中后序遍歷結(jié)果。輸出：根、先中后序遍

22、歷結(jié)果。樣例輸入：樣例輸入：81 2 42 0 04 8 03 1 55 6 06 0 78 0 07 0 0樣例輸出：樣例輸出：33 1 2 4 8 5 6 72 1 8 4 3 6 7 52 8 4 1 7 6 5 3#includeusing namespace std;int a1002,b100;int dfs(int k,int w) if(w=1)coutk ; if(ak0!=0)dfs(ak0,w); if(w=2)coutk ; if(ak1!=0)dfs(ak1,w); if(w=3)coutkn; for(i=1;it;cinat0at1; bat0=1;bat1=1;

23、 for(i=1;i=n;i+) if(bi=0)root=i;break; dfs(root,1);coutendl; dfs(root,2);coutendl; dfs(root,3);coutendl;1 1、樹轉(zhuǎn)化為二叉樹、樹轉(zhuǎn)化為二叉樹 一棵有序樹轉(zhuǎn)化成二叉樹的根結(jié)點(diǎn)是沒有右子樹的一棵有序樹轉(zhuǎn)化成二叉樹的根結(jié)點(diǎn)是沒有右子樹的, ,并且除保并且除保管每個(gè)結(jié)點(diǎn)的最左分支外，其他分支應(yīng)去掉管每個(gè)結(jié)點(diǎn)的最左分支外，其他分支應(yīng)去掉, ,然后從最左的兒子然后從最左的兒子開場(chǎng)沿右兒子方向依次鏈接該結(jié)點(diǎn)的全部?jī)鹤?。例如將以下圖開場(chǎng)沿右兒子方向依次鏈接該結(jié)點(diǎn)的全部?jī)鹤?。例如將以下圖(a)(a)所示的普

24、通有序樹轉(zhuǎn)換成二叉樹所示的普通有序樹轉(zhuǎn)換成二叉樹( (以下圖以下圖b)b)。 五、由二叉樹的兩種遍歷順序確定樹構(gòu)造五、由二叉樹的兩種遍歷順序確定樹構(gòu)造 遍歷二叉樹如以下圖有三種規(guī)那么：遍歷二叉樹如以下圖有三種規(guī)那么： 前序遍歷：根前序遍歷：根左子樹左子樹右子樹；右子樹； 中序遍歷：左子樹中序遍歷：左子樹根根右子樹；右子樹； 后序遍歷：左子樹后序遍歷：左子樹右子樹右子樹根；根； 問問: :知前序序列和中序序列能否確定出二叉樹知前序序列和中序序列能否確定出二叉樹? ? 知中序序列和后序序列能否確定出二叉樹知中序序列和后序序列能否確定出二叉樹? ? 知前序序列和后序序列能否確定出二叉樹知前序序列和后

25、序序列能否確定出二叉樹? ? 例題例題:由二叉樹的先序序列和中序序列可獨(dú)一地確定一棵二由二叉樹的先序序列和中序序列可獨(dú)一地確定一棵二叉樹。例叉樹。例, 先序序列先序序列 ABHFDECKG 和中序序列和中序序列 HBDFAEKCG , 構(gòu)造二叉樹過程如下：構(gòu)造二叉樹過程如下：2 2、(NOIP7)(NOIP7)知一棵二叉樹的結(jié)點(diǎn)名為大寫英文字母，知一棵二叉樹的結(jié)點(diǎn)名為大寫英文字母， 中序：中序：CBGEAFHDIJCBGEAFHDIJ 后序：后序：CGEBHFJIDACGEBHFJIDA 求該二叉樹的先序遍歷的順序?yàn)槎嗌偾笤摱鏄涞南刃虮闅v的順序?yàn)槎嗌? ?1 1、知：先序遍歷結(jié)果：、知：先序遍歷結(jié)果：ABCDEFGHABCDEFGH 中序遍歷結(jié)果：中