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

1、第五章 樹和二叉樹Chapter 5 Tree and Binary Tree本章內(nèi)容本章內(nèi)容n樹樹n二叉樹二叉樹n二叉樹的設(shè)計與實現(xiàn)二叉樹的設(shè)計與實現(xiàn)n二叉樹的遍歷二叉樹的遍歷n樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換n樹的遍歷樹的遍歷n二叉樹的應(yīng)用二叉樹的應(yīng)用bacghdefijbacghdefij5.1 5.1 樹樹bacghdefij特點：特點：除根結(jié)點之外的所有結(jié)點有且只有一個前驅(qū)結(jié)點，根結(jié)點除根結(jié)點之外的所有結(jié)點有且只有一個前驅(qū)結(jié)點，根結(jié)點 沒有前驅(qū)結(jié)點沒有前驅(qū)結(jié)點樹中所有結(jié)點可以有零個或多個后繼結(jié)點樹中所有結(jié)點可以有零個或多個后繼結(jié)點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é)點子樹的根結(jié)點Root:樹的根結(jié)點樹的根結(jié)點DF :樹的根結(jié)點樹的根結(jié)點Root的子樹集合的子樹集合DF= D1 D2 D3 . Dm 并且并且Di Dj= (i j; i=1,2,m ; j=1,2,m )D D：樹：樹T T中結(jié)點的中結(jié)點的集合集合R R：樹中結(jié)點之：樹中結(jié)點之間關(guān)系的集合間關(guān)系的集合abdeijfcgh 主要用于樹的屏幕和打印機(jī)顯示。ijd

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

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

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

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

7、t 3、雙親孩子表示法、雙親孩子表示法J 3A -1B 0C 0D 0E 1F 1G 2H 3I 31237894560123456789孩子結(jié)點指針域孩子結(jié)點指針域 AB C E D F G4、孩子兄弟表示法、孩子兄弟表示法（二重鏈表法）（二重鏈表法）BDACEFG兄弟結(jié)點指針域兄弟結(jié)點指針域孩子結(jié)點指針域孩子結(jié)點指針域孩子兄弟表示孩子兄弟表示C C語言描述語言描述ABGDCHEF二叉樹(1) (1) 二叉樹的特點：二叉樹的特點： 度小于等于度小于等于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個結(jié)點的個結(jié)點的二叉樹。二叉樹。ACFBDE完全二叉樹完全二叉樹45628849181230302582二叉排序樹：二叉排序樹：若為非空二叉樹，若為非空二叉樹，根結(jié)點的左子樹所有結(jié)點的關(guān)鍵字根結(jié)點的左子樹所有結(jié)點的關(guān)鍵字值都小于根結(jié)點關(guān)鍵字值，右子樹值都小于根結(jié)點關(guān)鍵字值，右子樹所有結(jié)點的關(guān)鍵字值都大于或等于所有結(jié)點的關(guān)鍵字值都大于或等于根結(jié)點關(guān)鍵字值。左子樹和右子樹根結(jié)點關(guān)鍵字值。左子樹和右子樹又分別是一棵二叉排序樹。又分別是一棵二叉排序樹。ACEFBD平衡二叉樹：平衡二叉樹：

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

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

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

12、(3)可很容易證明(1)，證明如下： 當(dāng)i0時，顯然該結(jié)點為根結(jié)點，所以它沒有雙親結(jié)點。 當(dāng)i0時，設(shè)編號為i的結(jié)點的雙親結(jié)點的編號為f。如果i是其雙親結(jié)點的左孩子結(jié)點，根據(jù)性質(zhì)5的(2)有i2*f+1（i為奇數(shù)），即f(i-1)/2； 如果結(jié)點i是其雙親結(jié)點的右孩子結(jié)點，根據(jù)性質(zhì)5的(3)有i2*f+2（i為偶數(shù)），即fi/2-1。 綜合這兩種情況可以得到，當(dāng)i0時，其雙親結(jié)點的編號等于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é)點將結(jié)點x x插入到結(jié)點插入到結(jié)點parentparent的左孩子處的左孩子處ABGDCHEFparent

14、GDx147EpxCFEHAbtB*parentNULLNULL147EbtCFDHAB*parentE132B147EpxNULLNULL132B147Ebitree *InsertL(elemtype x,bitree *parent) bitree *p; if(parent=NULL) printf(“插入出錯!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是否存在申請新結(jié)點xNULLNULLparentparent無無左孩子時左孩子時parentparent有有左孩子時左孩子時二叉樹插入算法二叉樹插入算法將結(jié)點將結(jié)點x x插入到結(jié)點插入到結(jié)點parentparent的右孩子處原理同上。的右孩子處原理同上。刪除二叉樹刪除二叉樹bt中結(jié)點中結(jié)點parent的左子樹的左子樹ABGDCHEFparentABGDCHEFparent4.二叉樹的刪除btCFDHAB*parentE132BGIp

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

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

19、j，若有，若有k ki ik= k= kj j且結(jié)且結(jié)點點k kj j的右子樹為空，則結(jié)點的右子樹為空，則結(jié)點k ki i插入到結(jié)點插入到結(jié)點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; 申請一個申請一個新的結(jié)點新的結(jié)點二叉排序樹生成算法描述二叉排序樹生成算法描述空樹的情況空樹的情況尋找合適的尋

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; 插入插入一、二叉樹的遍歷一、二叉樹的遍歷 二叉樹的遍歷是指按照某種順序訪問二叉樹二叉樹的遍歷是指按照某種順序訪問二叉樹中的每個結(jié)點，使每個結(jié)點被訪問一次且只被訪中的每個結(jié)點，使每個結(jié)點被訪問一次且只被訪問一次。問一次。 由二叉樹的遞歸定義，二叉樹的三個基本組成單元是：根結(jié)點D

21、、左子樹L和右子樹R。根根左子樹左子樹右子樹右子樹Preorder（先序）（先序）DLRInorder（中序）（中序）LDRPostorder（后序）（后序）LRD前序遍歷二叉樹的前序遍歷二叉樹的操作定義操作定義為：為：若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則（1 1）訪問根結(jié)點；（）訪問根結(jié)點；（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é)點；）訪問根結(jié)點；（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é)點。）訪問根結(jié)點。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從二叉樹的第一層開始，從上至下、從左至右從二叉樹的第一層開始，從上至下、從左至右的順序逐點訪問。的順序逐點訪問。練習(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上堂課要點回顧樹樹基本概念存儲結(jié)構(gòu)雙親表示雙親表示孩子表示孩子表示孩子兄弟孩子兄弟雙親孩子雙親孩子二叉樹二叉樹基本概念存儲結(jié)構(gòu)順序存儲順序存儲鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯Σ迦?、刪除算法遍歷二叉排序樹（前序、中序、后序、層序）（前序、中序、后序、層序）前序遍歷算法執(zhí)行過程：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時，時，二叉樹無左子樹，由二叉樹無左子樹，由 aa1 1，a am-1m-1 和和 bb2 2， ，b bm m 可以唯一的確定二叉樹的右子樹；可以唯一的確定二叉樹的右子樹；B .j= mB .j= m時，時，二叉樹無右子樹，由二叉樹無右子樹，由 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 唯一的確定左子樹唯一的確定右子樹個數(shù)相同若若am = bj 后序后序中序中序AHBDFEKCGEKCGAHBDFECAHBDFKGECADFKGBHECAFKGBHD定理定理2：一棵二叉樹的前序序列和中序序列可：一棵二叉樹的前序序列和中序序列可以唯一地確定這棵二叉樹。（證明略）以唯一地確定這棵二叉樹。（證明略）假定：前序序列和中序序列分別為：假定：前序序列和中序序列分別為： aa1 1，a am m 和和 bb1 1， ，b bm m 若中序序列中與前序序列若中序序列中與前序序列a a