計(jì)算機(jī)軟件基礎(chǔ)5.樹和二叉樹

1、第五章 樹和二叉樹Chapter 5 Tree and Binary Tree本章內(nèi)容本章內(nèi)容n樹樹n二叉樹二叉樹n二叉樹的設(shè)計(jì)與實(shí)現(xiàn)二叉樹的設(shè)計(jì)與實(shí)現(xiàn)n二叉樹的遍歷二叉樹的遍歷n樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換n樹的遍歷樹的遍歷n二叉樹的應(yīng)用二叉樹的應(yīng)用bacghdefijbacghdefij5.1 5.1 樹樹bacghdefij特點(diǎn)：特點(diǎn)：除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)，根結(jié)點(diǎn)除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)，根結(jié)點(diǎn) 沒有前驅(qū)結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)樹中所有結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)樹中所有結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)bacghdefbacghdef非樹結(jié)構(gòu)非

2、樹結(jié)構(gòu)樹結(jié)構(gòu)描述的是樹結(jié)構(gòu)描述的是層次關(guān)系層次關(guān)系A(chǔ)DCBEFGHI 主要用于直觀描述樹的邏輯結(jié)構(gòu)。 主要用于樹的理論描述。T=(D,R)D:D=; 空樹空樹 R=,i=1,2,m D ;D=Root DF ri:是是Root子樹的根結(jié)點(diǎn)子樹的根結(jié)點(diǎn)Root:樹的根結(jié)點(diǎn)樹的根結(jié)點(diǎn)DF :樹的根結(jié)點(diǎn)樹的根結(jié)點(diǎn)Root的子樹集合的子樹集合DF= D1 D2 D3 . Dm 并且并且Di Dj= (i j; i=1,2,m ; j=1,2,m )D D：樹：樹T T中結(jié)點(diǎn)的中結(jié)點(diǎn)的集合集合R R：樹中結(jié)點(diǎn)之：樹中結(jié)點(diǎn)之間關(guān)系的集合間關(guān)系的集合abdeijfcgh 主要用于樹的屏幕和打印機(jī)顯示。ijd

3、fghabcea ( b ( d, e ( i, j ), f ),c ( g, h ) )ADCBEFGHI（1 1）結(jié)點(diǎn)：結(jié)點(diǎn)：由數(shù)據(jù)元素由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關(guān)和構(gòu)造數(shù)據(jù)元素之間關(guān)系的指針組成系的指針組成. .（2 2）結(jié)點(diǎn)的度結(jié)點(diǎn)的度：結(jié)點(diǎn)所：結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)。擁有的子樹的個(gè)數(shù)。（3 3）葉子結(jié)點(diǎn)：葉子結(jié)點(diǎn)：度為度為0 0的結(jié)點(diǎn)。的結(jié)點(diǎn)。（4 4）分枝結(jié)點(diǎn)：分枝結(jié)點(diǎn)：度不為度不為0 0的結(jié)點(diǎn)。的結(jié)點(diǎn)。（5 5）樹的度：樹的度：樹中各結(jié)點(diǎn)度的最大值稱為該樹的度。樹中各結(jié)點(diǎn)度的最大值稱為該樹的度。（6 6）孩子、兄弟、雙親：孩子、兄弟、雙親：樹中一個(gè)結(jié)點(diǎn)的子樹的根結(jié)樹中一個(gè)結(jié)點(diǎn)

4、的子樹的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子。這個(gè)結(jié)點(diǎn)稱為它的孩子結(jié)點(diǎn)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子。這個(gè)結(jié)點(diǎn)稱為它的孩子結(jié)點(diǎn)的雙親。具有同一個(gè)雙親的孩子結(jié)點(diǎn)互為兄弟。的雙親。具有同一個(gè)雙親的孩子結(jié)點(diǎn)互為兄弟。（7 7）結(jié)點(diǎn)的層次：結(jié)點(diǎn)的層次：規(guī)定樹的根結(jié)點(diǎn)的層次為規(guī)定樹的根結(jié)點(diǎn)的層次為0 0，其余，其余結(jié)點(diǎn)的層次等于它的雙親結(jié)點(diǎn)的層次加結(jié)點(diǎn)的層次等于它的雙親結(jié)點(diǎn)的層次加1 1。（8 8）樹的深度：樹的深度：樹中所有結(jié)點(diǎn)的最大層次稱為樹的深樹中所有結(jié)點(diǎn)的最大層次稱為樹的深度。度。（9 9）有序樹和無(wú)序樹：有序樹和無(wú)序樹：如果一棵樹中結(jié)點(diǎn)的各子樹從如果一棵樹中結(jié)點(diǎn)的各子樹從左到右是有次序的，即若交換某結(jié)點(diǎn)各子樹的相對(duì)

5、位左到右是有次序的，即若交換某結(jié)點(diǎn)各子樹的相對(duì)位置則構(gòu)成不同的樹，稱這棵樹為有序樹；否則為無(wú)序置則構(gòu)成不同的樹，稱這棵樹為有序樹；否則為無(wú)序樹。樹。（1010）森林：森林：零棵或有限棵不相交的樹的集合稱為森零棵或有限棵不相交的樹的集合稱為森林。林。練習(xí)：雙親表示法雙親表示法孩子表示法孩子表示法孩子兄弟表示法孩子兄弟表示法雙親孩子表示法雙親孩子表示法ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5序號(hào)序號(hào) data parent 1.雙親表示法雙親表示法雙親表示法雙親表示法c c語(yǔ)言描述語(yǔ)言描述特點(diǎn)：難于實(shí)現(xiàn)尋找一個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)的操作特點(diǎn)：難于實(shí)現(xiàn)尋找一

6、個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)的操作 便于實(shí)現(xiàn)尋找一個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的操作便于實(shí)現(xiàn)尋找一個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的操作 data parent結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):2.2.孩子表示法孩子表示法ABCDEFGHIJABC DE F GH I J兩種方法：兩種方法：結(jié)點(diǎn)的指針域的個(gè)數(shù)結(jié)點(diǎn)的指針域的個(gè)數(shù)= =樹的度樹的度 同構(gòu)型同構(gòu)型結(jié)點(diǎn)的指針域的個(gè)數(shù)結(jié)點(diǎn)的指針域的個(gè)數(shù)= =結(jié)點(diǎn)的度結(jié)點(diǎn)的度 異構(gòu)型異構(gòu)型同構(gòu)型同構(gòu)型（多重鏈表法）（多重鏈表法）ABCDEFGHIJ異構(gòu)型異構(gòu)型特點(diǎn)：便于實(shí)現(xiàn)尋找一個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)的操作 難于實(shí)現(xiàn)尋找一個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的操作ABCDEFGHIJ序號(hào)序號(hào) datadata parent paren

7、t 3、雙親孩子表示法、雙親孩子表示法J 3A -1B 0C 0D 0E 1F 1G 2H 3I 31237894560123456789孩子結(jié)點(diǎn)指針域孩子結(jié)點(diǎn)指針域 AB C E D F G4、孩子兄弟表示法、孩子兄弟表示法（二重鏈表法）（二重鏈表法）BDACEFG兄弟結(jié)點(diǎn)指針域兄弟結(jié)點(diǎn)指針域孩子結(jié)點(diǎn)指針域孩子結(jié)點(diǎn)指針域孩子兄弟表示孩子兄弟表示C C語(yǔ)言描述語(yǔ)言描述ABGDCHEF二叉樹(1) (1) 二叉樹的特點(diǎn)：二叉樹的特點(diǎn)： 度小于等于度小于等于2 2 有序樹有序樹(2) (2) 二叉樹的五種基本形態(tài)二叉樹的五種基本形態(tài) 左子樹右子樹右子樹左子樹(a)(b)(c)(d)(e)(2) (

8、2) 特殊二叉樹特殊二叉樹ACGFBDE滿二叉樹滿二叉樹一棵深度為一棵深度為h h且有且有2 2h+1h+1-1-1個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的二叉樹。二叉樹。ACFBDE完全二叉樹完全二叉樹45628849181230302582二叉排序樹：二叉排序樹：若為非空二叉樹，若為非空二叉樹，根結(jié)點(diǎn)的左子樹所有結(jié)點(diǎn)的關(guān)鍵字根結(jié)點(diǎn)的左子樹所有結(jié)點(diǎn)的關(guān)鍵字值都小于根結(jié)點(diǎn)關(guān)鍵字值，右子樹值都小于根結(jié)點(diǎn)關(guān)鍵字值，右子樹所有結(jié)點(diǎn)的關(guān)鍵字值都大于或等于所有結(jié)點(diǎn)的關(guān)鍵字值都大于或等于根結(jié)點(diǎn)關(guān)鍵字值。左子樹和右子樹根結(jié)點(diǎn)關(guān)鍵字值。左子樹和右子樹又分別是一棵二叉排序樹。又分別是一棵二叉排序樹。ACEFBD平衡二叉樹：平衡二叉樹：

9、二叉樹中每個(gè)結(jié)點(diǎn)的平二叉樹中每個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值都不大于衡因子的絕對(duì)值都不大于1 1，則稱這棵二叉樹，則稱這棵二叉樹為平衡二叉樹。為平衡二叉樹。平衡因子：平衡因子：二叉樹任意結(jié)點(diǎn)的左子樹二叉樹任意結(jié)點(diǎn)的左子樹深度減去右子樹深度的差值，為此結(jié)點(diǎn)的深度減去右子樹深度的差值，為此結(jié)點(diǎn)的平衡因子。平衡因子。1、創(chuàng)建二叉樹、創(chuàng)建二叉樹2、撤消二叉樹、撤消二叉樹3、左插入結(jié)點(diǎn)、左插入結(jié)點(diǎn)4、右插入結(jié)點(diǎn)、右插入結(jié)點(diǎn)5、左刪除子樹、左刪除子樹6、右刪除子樹、右刪除子樹7、遍歷二叉樹、遍歷二叉樹8 8、其他、其他: :左插入子樹左插入子樹, ,右插入子樹右插入子樹, ,左刪除結(jié)點(diǎn)左刪除結(jié)點(diǎn), , 右刪除結(jié)

10、點(diǎn)等右刪除結(jié)點(diǎn)等 ”表示上取整證明：設(shè)完全二叉樹的高度為證明：設(shè)完全二叉樹的高度為h h，則有，則有 2 2h h - 1 - 1 n n 2 2h+1h+1 - 1 - 1 2 2h h n+1n+1 = 2= 2h+1h+1 取對(duì)數(shù)取對(duì)數(shù) h h log log2 2( (n+1n+1) = ) = h+1h+1 012345678910 11n 證明：此性質(zhì)可以用歸納法證明，在此先證明其中的(2)和(3)。 當(dāng)i0時(shí)，由完全二叉樹的定義得知， 如果2*i+11n，說(shuō)明二叉樹中存在兩個(gè)或兩個(gè)以上的結(jié)點(diǎn)，所以結(jié)點(diǎn)i的左孩子存在且編號(hào)為1； 反之，如果2*i+11n，說(shuō)明二叉樹中只有一個(gè)結(jié)點(diǎn)i

11、，結(jié)點(diǎn)i的左孩子結(jié)點(diǎn)不存在。 同理，如果2i+22n，說(shuō)明結(jié)點(diǎn)i的右孩子存在且編號(hào)為2； 如果2*i+22n，說(shuō)明二叉樹中不存在編號(hào)為2的結(jié)點(diǎn)，即結(jié)點(diǎn)i的右孩子不存在。 假設(shè)對(duì)于編號(hào)為j(0ji）的結(jié)點(diǎn)，(2)和(3)成立。 當(dāng)ij+1時(shí)，根據(jù)完全二叉樹的定義，若其左孩子結(jié)點(diǎn)存在則其左孩子結(jié)點(diǎn)的編號(hào)等于編號(hào)為j的結(jié)點(diǎn)的右孩子的編號(hào)加1，即其左孩子結(jié)點(diǎn)的編號(hào)等于2*j+2+12*i+1； 同樣，當(dāng)ij+1時(shí)，根據(jù)完全二叉樹的定義，若其右孩子結(jié)點(diǎn)存在，則其右孩子結(jié)點(diǎn)的編號(hào)等于其左孩子結(jié)點(diǎn)的編號(hào)加1，即其右孩子結(jié)點(diǎn)的編號(hào)等于2i+1+1=2*i+2， 因此性質(zhì)5的(2)，(3)得證。 由上述(2)和

12、(3)可很容易證明(1)，證明如下： 當(dāng)i0時(shí)，顯然該結(jié)點(diǎn)為根結(jié)點(diǎn)，所以它沒有雙親結(jié)點(diǎn)。 當(dāng)i0時(shí)，設(shè)編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為f。如果i是其雙親結(jié)點(diǎn)的左孩子結(jié)點(diǎn)，根據(jù)性質(zhì)5的(2)有i2*f+1（i為奇數(shù)），即f(i-1)/2； 如果結(jié)點(diǎn)i是其雙親結(jié)點(diǎn)的右孩子結(jié)點(diǎn)，根據(jù)性質(zhì)5的(3)有i2*f+2（i為偶數(shù)），即fi/2-1。 綜合這兩種情況可以得到，當(dāng)i0時(shí)，其雙親結(jié)點(diǎn)的編號(hào)等于i/2-1。因此性質(zhì)5的(1)得證。013245789610111213141516例1：i=5, 2*i+1Lchild=NULL; (*bt)-Rchild=NULL; return 1;2.二叉樹的創(chuàng)建

13、x x117CBDG117C117ClbtCFEH10061006rbt147Ep117C1006生成算法生成算法bitree *Create(elemtype x,bitree *lbt, bitree *rbt) bitree *p; if(p=(bitree*)malloc(sizeof(bitree)=NULL) return NULL; p-data=x; p-Lchild=lbt; p-Rchild=rbt; return p;3.二叉樹的插入ABGDCHEFparentx將結(jié)點(diǎn)將結(jié)點(diǎn)x x插入到結(jié)點(diǎn)插入到結(jié)點(diǎn)parentparent的左孩子處的左孩子處ABGDCHEFparent

14、GDx147EpxCFEHAbtB*parentNULLNULL147EbtCFDHAB*parentE132B147EpxNULLNULL132B147Ebitree *InsertL(elemtype x,bitree *parent) bitree *p; if(parent=NULL) printf(“插入出錯(cuò)!n”); return NULL; if(p=(bitree*)malloc(sizeof(bitree)=NULL) return NULL; p-data=x; p-Lchild=NULL; p-Rchild=NULL; if(parent-Lchild=NULL) par

15、ent-Lchild=p; else p-Lchild=parent-Lchild; parent-Lchild=p; return p;判parentparent是否存在申請(qǐng)新結(jié)點(diǎn)xNULLNULLparentparent無(wú)無(wú)左孩子時(shí)左孩子時(shí)parentparent有有左孩子時(shí)左孩子時(shí)二叉樹插入算法二叉樹插入算法將結(jié)點(diǎn)將結(jié)點(diǎn)x x插入到結(jié)點(diǎn)插入到結(jié)點(diǎn)parentparent的右孩子處原理同上。的右孩子處原理同上。刪除二叉樹刪除二叉樹bt中結(jié)點(diǎn)中結(jié)點(diǎn)parent的左子樹的左子樹ABGDCHEFparentABGDCHEFparent4.二叉樹的刪除btCFDHAB*parentE132BGIp

16、NULL132Bbitree *DeleteL(bitree *bt,bitree *parent) bitree *p; if(parent=NULL | parent-Lchild=NULL ) printf(“出錯(cuò)！出錯(cuò)！n”); return NULL; p= parent-Lchild ; parent-Lchild=NULL; DeleteL(bt,p); DeleteR(bt,p); free(p); return bt;刪除二叉樹刪除二叉樹btbt中結(jié)點(diǎn)中結(jié)點(diǎn)parentparent的右子樹，原理同上。的右子樹，原理同上。刪除算法刪除算法parentparent有有左孩子時(shí)左孩

17、子時(shí)釋放結(jié)點(diǎn)釋放結(jié)點(diǎn)判parentparent和它的左子樹是否存在生成一棵二叉排序樹生成一棵二叉排序樹,過(guò)程如下過(guò)程如下: 若二叉排序樹為空，則令待插結(jié)點(diǎn)為根結(jié)點(diǎn)若二叉排序樹為空，則令待插結(jié)點(diǎn)為根結(jié)點(diǎn), 若二叉排序樹非空，則比較待插結(jié)點(diǎn)若二叉排序樹非空，則比較待插結(jié)點(diǎn)(k1)和根結(jié)和根結(jié)點(diǎn)點(diǎn)(k0)的數(shù)據(jù)值。若的數(shù)據(jù)值。若k1k0,則將其插入到左子樹中；則將其插入到左子樹中；否則，將其插入到右子樹中否則，將其插入到右子樹中. 結(jié)點(diǎn)插入二叉排序樹的左、右子樹過(guò)程同上結(jié)點(diǎn)插入二叉排序樹的左、右子樹過(guò)程同上.例:將序列15,10,18,2,11,8,16,25,11構(gòu)成一棵二叉排序樹,過(guò)程:1510

18、1821181625115.3.3 5.3.3 二叉排序樹的生成二叉排序樹的生成二叉排序樹生成算法步驟（非遞歸）二叉排序樹生成算法步驟（非遞歸）k0, k1, k2, , kn-11.1. K K0 0應(yīng)為二叉排序樹的根；應(yīng)為二叉排序樹的根；2.2. 若若k k1 1kk0 0則則k k1 1結(jié)點(diǎn)應(yīng)插入到結(jié)點(diǎn)應(yīng)插入到k k0 0的左子樹，否則，的左子樹，否則，插入到插入到k k0 0的右子樹；的右子樹；3.3. 讀入讀入k ki i若若k ki ikk0 0，則進(jìn)入左子樹，否則，進(jìn)，則進(jìn)入左子樹，否則，進(jìn)入右子樹，繼續(xù)與子樹之根比較。直到某入右子樹，繼續(xù)與子樹之根比較。直到某結(jié)點(diǎn)結(jié)點(diǎn)k kj

19、j，若有，若有k ki ik= k= kj j且結(jié)且結(jié)點(diǎn)點(diǎn)k kj j的右子樹為空，則結(jié)點(diǎn)的右子樹為空，則結(jié)點(diǎn)k ki i插入到結(jié)點(diǎn)插入到結(jié)點(diǎn)k kj j的右子樹。的右子樹。4.4. 若若inin繼續(xù)執(zhí)行第繼續(xù)執(zhí)行第3 3步。步。#define N 10bitree *creat_bstree(elemtype a) int i; bitree *bt,*s,*p,*q; bt=NULL; for (i=0;idata=ai; s-Lchild=NULL; s-Rchild=NULL; 申請(qǐng)一個(gè)申請(qǐng)一個(gè)新的結(jié)點(diǎn)新的結(jié)點(diǎn)二叉排序樹生成算法描述二叉排序樹生成算法描述空樹的情況空樹的情況尋找合適的尋

20、找合適的插入位置插入位置if (bt=NULL) bt=s;else p=bt; while(p!=NULL) q=p; if (s-datadata) p=p-Lchild; else p=p-Rchild; if (s-datadata) q-Lchild=s; else q-Rchild=s; return bt; 插入插入一、二叉樹的遍歷一、二叉樹的遍歷 二叉樹的遍歷是指按照某種順序訪問二叉樹二叉樹的遍歷是指按照某種順序訪問二叉樹中的每個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)被訪問一次且只被訪中的每個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)被訪問一次且只被訪問一次。問一次。 由二叉樹的遞歸定義，二叉樹的三個(gè)基本組成單元是：根結(jié)點(diǎn)D

21、、左子樹L和右子樹R。根根左子樹左子樹右子樹右子樹Preorder（先序）（先序）DLRInorder（中序）（中序）LDRPostorder（后序）（后序）LRD前序遍歷二叉樹的前序遍歷二叉樹的操作定義操作定義為：為：若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則（1 1）訪問根結(jié)點(diǎn)；（）訪問根結(jié)點(diǎn)；（2 2）前序遍歷左子樹；）前序遍歷左子樹；（3 3）前序遍歷右子樹。）前序遍歷右子樹。1. 前（先）序遍歷（DLR）CFBGDHEBDGEHABGDCHEFACFGHEADBGEHFC遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) retur

22、n; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP- A遞歸前序遍歷算法void Preorder(bitree *

23、p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP- A遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-A遞歸前序遍歷算法v

24、oid Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP- BA遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild)

25、; ACBGHDEFP-BA遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BA遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=N

26、ULL) Preorder(pRchild); ACBGHDEFP-BAD遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADNULL遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preor

27、der(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BAD遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BAD遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata);

28、if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADG遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADGNULL遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL

29、) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADGNULLNULL遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADGNULL遞歸前序遍

30、歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADG遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRc

31、hild); ACBGHDEFP-BADG遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADGC遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(p

32、Rchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADGC遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADGC遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=N

33、ULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADGCE遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADGCENULL遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return;

34、printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADGCENULLNULL遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADGCE遞歸前序遍歷算法void Pr

35、eorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADGCE遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); A

36、CBGHDEFP-BADGCE遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADGCEF遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchi

37、ld !=NULL) Preorder(pRchild); ACBGHDEFP-BADGCEF遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADGCEF遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=N

38、ULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADGCEFH遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADGCEFHNULL遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) retu

39、rn; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADGCEFHNULLNULL遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADGCEFHNULL遞歸前

40、序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); ACBGHDEFP-BADGCEFH遞歸前序遍歷算法void Preorder(bitree *p) if (p=NULL) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preord

41、er(pRchild); ACBGHDEFP-BADGCEFH中序遍歷二叉樹的中序遍歷二叉樹的操作定義操作定義為：為：若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則（1 1）中序遍歷左子樹；）中序遍歷左子樹； （2 2）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)；（3 3）中序遍歷右子樹。）中序遍歷右子樹。2. 中序遍歷（LDR）BGDHEBDGEHABGDCHEFACFGHEDGBHEAFCvoid inorder(treenode *bt) if (bt=NULL) return; if(bt-lchild!=NULL) inorder(bt-lchild); printf(“ %d”,bt-da

42、ta); if(bt-rchild!=NULL) inorder(bt-rchild);中序遍歷算法：后序遍歷二叉樹的后序遍歷二叉樹的操作定義操作定義為：為：若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則（1 1）后序遍歷左子樹；）后序遍歷左子樹； （2 2）后序遍歷右子樹；）后序遍歷右子樹；（3 3）訪問根結(jié)點(diǎn)。）訪問根結(jié)點(diǎn)。3. 后序遍歷（LRD）BGDHEBDGEHABGDCHEFACFGHEDHGBEFAC后序遍歷算法：void postorder(treenode *bt) if (bt=NULL) return; if(bt-lchild!=NULL) postorder

43、(bt-lchild); if(bt-rchild!=NULL) postorder(bt-rchild); printf(“ %d”,bt-data);4. 層序遍歷BDABGDCHEFACFGEHACBEDFHG從二叉樹的第一層開始，從上至下、從左至右從二叉樹的第一層開始，從上至下、從左至右的順序逐點(diǎn)訪問。的順序逐點(diǎn)訪問。練習(xí)：寫出如圖所示二叉樹的各種遍歷序列HIKJGABFCED后序：后序：F E D C B H K J I G AF E D C B H K J I G A中序：中序：B D E F C A H G J K IB D E F C A H G J K I前序：前序：A B

44、C D E F G H I J KA B C D E F G H I J K層序：層序：A B G C H I D J E K FA B G C H I D J E K F上堂課要點(diǎn)回顧樹樹基本概念存儲(chǔ)結(jié)構(gòu)雙親表示雙親表示孩子表示孩子表示孩子兄弟孩子兄弟雙親孩子雙親孩子二叉樹二叉樹基本概念存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)插入、刪除算法遍歷二叉排序樹（前序、中序、后序、層序）（前序、中序、后序、層序）前序遍歷算法執(zhí)行過(guò)程：11001200A1000BCPreOrderPreOrder0 0( (10001000) )A A1000-Lchild!=NULL1000-Lchild!=NUL

45、L PreOrderPreOrder1 1( (11001100) ) B B 1100-Lchild=NULL 1100-Lchild=NULL 1100-Rchild=NULL 1100-Rchild=NULL -/ -/ 1000-Rchild!=NULL1000-Rchild!=NULL PreOrderPreOrder2 2( (12001200) ) C C 1200-Lchild=NULL 1200-Lchild=NULL 1200-Rchild=NULL 1200-Rchild=NULL ENDEND -/-/void Preorder(bitree *p) if (p=NUL

46、L) return; printf(“%d”,pdata); if(pLchild !=NULL) Preorder(pLchild); if(pRchild !=NULL) Preorder(pRchild); void Inorder(treenode *bt) if (bt=NULL) return; if(bt-Lchild!=NULL) Inorder(bt-Lchild); printf(“ %d”,bt-data); if(bt-Rchild!=NULL) Inorder(bt-Rchild);void Postorder(treenode *bt) if (bt=NULL) r

47、eturn; if(bt-Lchild!=NULL) Postorder(bt-Lchild); if(bt-Rchild!=NULL) Postorder(bt-Rchild); printf(“ %d”,bt-data);中序遍歷中序遍歷后序遍歷后序遍歷定理定理1：一棵二叉樹的后序序列和中序序列可：一棵二叉樹的后序序列和中序序列可以唯一的確定這棵二叉樹。（證明略）以唯一的確定這棵二叉樹。（證明略）假定：后序序列和中序序列分別為：假定：后序序列和中序序列分別為： aa1 1，a am m 和和 bb1 1， ，b bm m 若中序序列中與后序序列若中序序列中與后序序列a am m相同的元素為

48、相同的元素為b bj j。A .j =1A .j =1時(shí)，時(shí)，二叉樹無(wú)左子樹，由二叉樹無(wú)左子樹，由 aa1 1，a am-1m-1 和和 bb2 2， ，b bm m 可以唯一的確定二叉樹的右子樹；可以唯一的確定二叉樹的右子樹；B .j= mB .j= m時(shí)，時(shí)，二叉樹無(wú)右子樹，由二叉樹無(wú)右子樹，由 aa1 1，a am-1m-1 和和 bb1 1， ，b bm-1m-1 可以唯一的確定二叉樹的左子樹；可以唯一的確定二叉樹的左子樹；a1，a2 ， ，aj， aj+1， ，am b1， ，bj-1，bj ，bj+1， ，bm 唯一的確定左子樹唯一的確定右子樹個(gè)數(shù)相同若若am = bj 后序后序中序中序AHBDFEKCGEKCGAHBDFECAHBDFKGECADFKGBHECAFKGBHD定理定理2：一棵二叉樹的前序序列和中序序列可：一棵二叉樹的前序序列和中序序列可以唯一地確定這棵二叉樹。（證明略）以唯一地確定這棵二叉樹。（證明略）假定：前序序列和中序序列分別為：假定：前序序列和中序序列分別為： aa1 1，a am m 和和 bb1 1， ，b bm m 若中序序列中與前序序列若中序序列中與前序序列a a