計算機軟件基礎5.樹和二叉樹

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

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

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

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

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

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

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

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

10、點等右刪除結點等 ”表示上取整證明：設完全二叉樹的高度為證明：設完全二叉樹的高度為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)。 當i0時，由完全二叉樹的定義得知， 如果2*i+11n，說明二叉樹中存在兩個或兩個以上的結點，所以結點i的左孩子存在且編號為1； 反之，如果2*i+11n，說明二叉樹中只有一個結點i

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

12、(3)可很容易證明(1)，證明如下： 當i0時，顯然該結點為根結點，所以它沒有雙親結點。 當i0時，設編號為i的結點的雙親結點的編號為f。如果i是其雙親結點的左孩子結點，根據(jù)性質(zhì)5的(2)有i2*f+1（i為奇數(shù)），即f(i-1)/2； 如果結點i是其雙親結點的右孩子結點，根據(jù)性質(zhì)5的(3)有i2*f+2（i為偶數(shù)），即fi/2-1。 綜合這兩種情況可以得到，當i0時，其雙親結點的編號等于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將結點將結點x x插入到結點插入到結點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是否存在申請新結點xNULLNULLparentparent無無左孩子時左孩子時parentparent有有左孩子時左孩子時二叉樹插入算法二叉樹插入算法將結點將結點x x插入到結點插入到結點parentparent的右孩子處原理同上。的右孩子處原理同上。刪除二叉樹刪除二叉樹bt中結點中結點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中結點中結點parentparent的右子樹，原理同上。的右子樹，原理同上。刪除算法刪除算法parentparent有有左孩子時左孩

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

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

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

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

21、、左子樹L和右子樹R。根根左子樹左子樹右子樹右子樹Preorder（先序）（先序）DLRInorder（中序）（中序）LDRPostorder（后序）（后序）LRD前序遍歷二叉樹的前序遍歷二叉樹的操作定義操作定義為：為：若二叉樹為空，則空操作；否則若二叉樹為空，則空操作；否則（1 1）訪問根結點；（）訪問根結點；（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）訪問根結點；）訪問根結點；（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）訪問根結點。）訪問根結點。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從二叉樹的第一層開始，從上至下、從左至右從二叉樹的第一層開始，從上至下、從左至右的順序逐點訪問。的順序逐點訪問。練習：寫出如圖所示二叉樹的各種遍歷序列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上堂課要點回顧樹樹基本概念存儲結構雙親表示雙親表示孩子表示孩子表示孩子兄弟孩子兄弟雙親孩子雙親孩子二叉樹二叉樹基本概念存儲結構順序存儲順序存儲鏈式存儲鏈式存儲插入、刪除算法遍歷二叉排序樹（前序、中序、后序、層序）（前序、中序、后序、層序）前序遍歷算法執(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