1、二叉樹的遍歷 按前序遍歷 按中序遍歷 按后序遍歷按前序遍歷二叉樹 首先訪問根結點 然后按前序遍歷根結點的左子樹 最后按前序遍歷根結點的右子樹ABDCEFGvoid r_preorder(t)NODE *t; if (t!=NULL) printf(“%c”,t-data); r_preorder(t-lchild); r_preorder(t-rchild); 按中序遍歷二叉樹 首先以中序遍歷根結點的左子樹 然后訪問根結點 最后按中序遍歷根結點的右子樹DBAECFGD B A E C F G按中序遍歷二叉樹void r_midorder(t)NODE *t; if (t!=NULL) r_mi

2、dorder(t-lchild); printf(“%c”,t-data); r_midorder(t-rchild); DBAECFGA B D top將樹根的所有左孩子入棧A B topD出棧,并輸出A B 將D的右孩子入棧A B出棧,并輸出.B的右孩子入棧 A出棧,并輸出C 將A的右孩子入棧,再將此結點的所有左孩子入棧E toptoptoptopC topE出棧,并輸出.E的右孩子入棧 topC出棧F topC的右孩子進棧,再將該結點的所有左孩子入棧 F出棧G toptopF的右孩子進棧,再將該結點的所有左孩子入棧 topG出棧,并輸出#include struct node char

3、data; struct node *lchild; struct node *rchild; ;typedef struct node NODE;struct snode NODE *addr; struct snode *link; ;typedef struct snode SNODE;void s_midorder(t) NODE *t;SNODE *top,*p;top=NULL;while(t!=NULL| top!=NULL) while (t!=NULL) p=(SNODE*) malloc(sizeof(SNODE); p-addr=t; p-link=top; top=p;

4、 t=t-lchild;if (top!=NULL) t=top-addr; printf(“%c”,t-data); p=top; top=top-link; free(p); t=t-rchild; 按后序遍歷二叉樹 首先按后序遍歷根結點的左子樹 然后按后序遍歷根結點的右子樹 最后訪問根結點DBEGFCAvoid r_posorder(t)NODE *t; if (t!=NULL) r_posorder(t-lchild); r_posorder(t-rchild); printf(“%c”,t-data); 前序：ABDEGCFH中序：DBGEAFHC后序：DGEBHFCA二叉樹的遍歷

5、前序和中序相同的二叉樹, 中序和后序相同的二叉樹,. 前序和后序相同的二叉樹,前序：ABDEGCFH中序：DBGEAFHC由二叉樹的前序和中序可以唯一地確定一棵二叉樹中序：DBGEAFHC后序：DGEBHFCA由二叉樹的中序和后序可以唯一地確定一棵二叉樹前序:ABCDEFGH后序:CDBEGHFA層次:ABEFCDGH前序:ABCDEFGH中序:CDBEGHFA后序:CDHGFEBA二叉樹的遍歷 將有序樹轉化為相應的二叉樹 有序樹的前序=二叉樹的前序 有序樹的后序=二叉樹的中序NODE *copy(t) NODE *t; NODE *p; if (t= =NULL) return(NULL);

6、 else p=(NODE*) malloc(sizeof(NODE); p-data=t-data; p-lchild=copy(t-lchild); p-rchild=copy(t-rchild); return(p); 判斷兩棵二叉樹是否相等 兩棵二叉樹若都為空,則相等 兩棵樹的根結點的值相等,并且兩棵樹根結點的左右子樹分別相等,則兩棵樹相等AAt1t2int equaltree(t1,t2) NODE *t1,*t2; if (t1= =NULL& t2=NULL) return(1); if (t1!=NULL & t2!=NULL) if (t1-data= =t2

7、-data) if (equaltree(t1-lchild,t2-lchild) return( equaltree(t1-rchild,t2-rchild); return(0); 二叉樹的前序遍歷序列中,任意一個結點處在其子女結點的前面. 由于二叉樹中每個結點的度最大為2,所以二叉樹就是二次有序樹. 在一非空二叉樹的中序遍歷序列中,根結點的右邊只有右子樹上的所有結點 任何一棵二叉樹的葉子結點在前序 中序和后序遍歷序列中的相對次序是不發生改變的.判斷題: 已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,則它的前序遍歷是( ) 某二叉樹的前序遍歷序列是abdgcefh,中序

8、遍歷的序列是dgbaechf,則后序遍歷的順序是( ) 如果某二叉樹的前序為stuwv,中序為uwtvs,則該二叉樹的后序為( ). 如下圖所示的二叉樹是由有序樹T1轉換而來的二叉樹,則樹T1有( )個葉子結點. 假設二叉樹中所有非葉子結點都有左右子樹,若有n個葉子結點,則該二叉樹共有( )個結點 若深度為h的二叉樹上只有度為0和度為2的結點,則此類二叉樹中包含的結點數至少為( ). 若一棵二叉樹,左右子樹均有三個結點,其左子樹的前序序列與中序序列相同,右子樹的中序序列與后序序列相同,試構造該樹 如果T2是由有序樹T轉換而來的二叉樹,則T中結點的前序就是T2中結點的( ).1.編寫后序遍歷二叉

9、樹的非遞歸過程.2.設計一個算法求二叉樹的高度.3.設計統計一個二叉樹中所有葉子結點的數目的算法.4.編寫一個將二叉樹中每個結點的左右孩子交換的算法.算法題:1.深度為k(設根的層數為0)的完全二叉樹至少有( )個結點,至多有( )個結點.2.設高度為h的二叉樹只有度為0和2的結點,則此類二叉樹的結點數至少為( ),至多為( ).3.一棵有124個葉子結點的完全二叉樹,最多有( )個結點. A.247 B.248 C.249 D.250 E.2514.具有n個結點的滿二叉樹,其葉結點的個數為( ).1.判斷正誤: 完全二叉樹的某結點若無左孩子,則它必是葉子結點 將一棵樹轉換成二叉樹后,根結點沒

10、有左子樹. 用二叉樹的前序和中序可以導出二叉樹的后序遍歷.2.由二叉樹的前序和后序遍歷序列( )唯一地確定這棵二叉樹. A.能 B.不能3.有二叉樹中序序列為:ABCEFGHD 后序序列:ABFHGEDC， 請畫出此二叉樹。4.若一棵二叉樹,左右子樹均有三個結點,其左子樹的前序序列與中序序列相同,右子樹的中序序列與后序序列相同,試構造該樹 二叉樹的存貯 二叉樹的鏈接存貯 樹的標準存貯結構 樹的逆存貯結構 樹的擴充標準存貯結構 二叉樹的順序存貯結構 把樹中的結點按某種適當的次序依次存放到一組連續的存貯單元中,使得結點的這種適當的次序能反映樹結構的部分信息按層次序的存儲形式 首先對該二叉樹中每個結

11、點進行編號,然后以各結點的編號為下標,把各結點的值對應存儲到一維數組中 首先把樹根結點的編號定為首先把樹根結點的編號定為0 然后按層次從上到下然后按層次從上到下,每層從左到右的順序每層從左到右的順序,對每一結點進行編號對每一結點進行編號 當它的雙親結點的編號為當它的雙親結點的編號為i時時,若它為左孩子若它為左孩子,則編號則編號 為為2i+1,若為右孩子若為右孩子,則編號為則編號為2(i+1)A B C D E G F H0 1 2 3 4 5 6 7 8 9 10 11 12按前序的存貯形式 附加左標志位和右指針 附加兩個標志位前序:ABDFCEGH附加左標志位和右指針 左標志位:存放結點k后

12、面的結點是否為k的左子結點 ltag=0 結點k后面的結點是k的左子結點 ltag=1 結點k 無左子結點 右指針rchild:指向結點k的右子結點 ltag data rchild附加左標志位和右指針ABDFCEGH0101001142-1-1-1-17-1Ltag data rchild01234567#define MAXN 100struct node int ltag; char data; int rchild;typedef struct node NODE;NODE aMAXN;附加左標志位和右指針ABDFCEGH0101001142-1-1-1-17-1Ltag data r

13、child01234567查找結點k的左子結點:if(ap.ltag= =0) printf(“%c”,ap+1.data);else ;查找結點k的右子結點:if (ap.rchild= =-1)else printf(“%c”,aap.rchild.data);查找結點k的按前序的前面結點:if (p-10) ;else printf(“%c”,ap-1.data);查找結點k的按前序的后面結點:if (p+1=n) ;else printf(“%c”,ap+1.data);查找結點k的父結點:if(p-10) else if (ap-1.ltag= =0) printf(“%c”,ap-

14、1.data); else for(q=p-1;aq.rchild!=p;q-) ; printf(“%c”,aq.data); 附加兩個標志位 左標志位:存放結點k后面的結點是否為k的左子結點 ltag=0 結點k后面的結點是k的左子結點 ltag=1 結點k 無左子結點 右標志位:結點k是否有右子結點 rtag=0 結點k有右子結點 rtag=1 結點k無右子結點 ltag data rtagLtag data rtagABDFCEGH010100110011110101234567struct lrnode char data; char ltag,rtag; ;typedef stru

15、ct rlnnode LRNODE;查找k的左子結點: if (ap.ltag= =0) printf(“%c”,ap+1.data); else ;Ltag data rtagABDFCEGH0101001100111101查找樹中所有結點的右子結點 棧:存放rtag=0且尚末找到右子結點的結點的地址 從根結點開始往下查找 rtag=0的結點,依次把這些結點的地址進棧 ltag=1的結點,此結點的后一個結點一定是棧頂結點的右子結點,棧頂結點退棧 直到樹中的結點都找到右子結點為止#include #define MAXN 100struct node char data; struct nod

16、e *lchild; struct node *rchild; ;typedef struct node NODE;struct lrnode char data; char ltag,rtag; ;typedef struct lrnode LRNODE;NODE *transfer(tree,n) LRNODE tree ; int n; NODE *stackMAXN,*root,*p,*q; int top,i; if(n= =0) return(NULL); root=(NODE*)malloc(sizeof(NODE); p=root; top=0;for(i=0;idata=tr

17、eei.data; if(treei.rtag= =0) stacktop+=p; else p-rchild=NULL; q=(NODE*)malloc(sizeof(NODE); if (treei.ltag= =0) p-lchild=q; else p-lchild=NULL; p=stack-top; p-rchild=q; p=q; p-data=treen-1.data;p-lchild=NULL;p-rchild=NULL;return(root); 順序查找 二分查找 分塊查找 散列查找查找樹 查找樹T是一棵二叉樹,它是或空,或滿足 以下三個條件: 如果樹T的根結點的左子樹非

18、空,則左子樹中所有結點的鍵值都小于t的根結點的鍵值 如果樹T的根結點的右子樹非空,則右子樹中所有結點的鍵值都大于t的根結點的鍵值 樹T的根結點的左右子樹也都是查找樹中序:2,3,6,7,8,10,12,18中序:10,15,17,18,20,22,25,27,28,30#include struct node char data; struct node *lchild,rchild; ;typedef struct node NODE;NODE *t,*p,*q;查找具有鍵值為a的結點1.找結點82.找結點4查找具有鍵值為a的結點如果t為空,則查找失敗;否則轉(2)如果t-data等于a,則

19、查找成功;否則轉(3)如果a小于t-data,則t=t-lchild,轉 (1); 否則,t=t-rchild,轉(1).void search (t,a,p_p,p_q) NODE *t,*p_p,*p_q; char a; *p_p=NULL; *p_q=t; while (*p_q!=NULL) if (*p_q)-data= =a) return; *p_p=*p_q; if (adata) *p_q=(*p_q)-lchild; else *p_q=(*p_q)-rchild;查找具有鍵值為a的結點 *p_p=NULL *p_q=NULL 查找失敗,查找樹為空 *p_p!=NULL

20、*p_q=NULL 查找失敗,*p_p指向查找路徑中最后一個結點 *p_p=NULL *p_q!=NULL 查找成功, *p_q指向根結點 *p_p!=NULL *p_q!=NULL 查找成功,*p_q指向a結點,*p_p指向a的父結點search(t,a,&p,&q)在給定查找樹中插入鍵值為a的結點1.插入結點42.插入結點133.插入結點12在給定查找樹中插入鍵值為a的結點 調用search( ) 鍵值為a的結點在樹T中,則不做插入; 如鍵值為a的結點不在樹T中,則把它插入在樹T的適當位置 若查找樹為空,則新的數據元素就是查找樹的根結點 若查找樹為非空,則新的數據元素應插入

21、適當的位置.int insert (p_t,a) NODE *p_t; char a; NODE *p,*q,*r; search(*p_t,a,&p,&q); if (q!=NULL) return(1); r=(NODE*)malloc(sizeof(NODE); r-data=a; r-lchild=NULL; r-rchild=NULL; if (p= =NULL) *p_t=r; else if (p-dataa) p-lchild=r; else p-rchild=r; return(0);查找樹的構造K=5,10,6,20,17,12,19,2查找樹的構造 K=k

22、0,k1,.kn-1,從k0開始依次取序列中的元素,每取出一個ki 若查找樹為空,則新的數據元素就是查找樹的根結點 若查找樹為非空,則新的數據元素與該查找樹的根結點的值進行比較,若小于根結點,則將新的數據元素插入到根結點的左子樹中,否則插入到右子樹中K=5,10,6,20,17,12,19,2查找樹中刪除結點1.刪除11,262.刪除103.刪除294.刪除15查找樹中刪除結點 若被刪除結點為葉子結點,則可以直接進行刪除; 若被刪除結點沒有左子樹,則可以用其右子樹的根結點取代被刪除結點的位置; 若被刪除結點沒有右子樹,則可以用其左子樹的根結點取代被刪除結點的位置; 若被刪除結點的左右子樹均存在

23、,則要找到被刪除結點的右子樹中值最小的結點,用該結點取代被刪除結點的位置1.已知下圖中二叉排序樹的各結點的值依次為32-40 請標出結點的值.1.已知8個數據元素為(34,76,45,18,26,54,92,65),按照依次插入結點的方法生成一棵二叉查找樹,則該樹的深度為( ). 最后兩層上的結點總數為( ).2.在一棵二叉查找樹中,按( )遍歷得到的結點序列是 一個有序序列.3.設K1,K2,K3是三個不同的關鍵字且K1K2K3，請畫出按不同的輸入順序建立相應的二叉排序樹。 4.已知一組元素為(50,28,78,65,23,36,13,42,71), 請完成以下操作: (1)畫出按元素排列順

24、序逐點插入所生成的二 叉排序樹BT. (2)分別計算在BT中查找各元素所要進行的元 素間的比較次數及平均比較次數. (3)畫出在BT中刪除(23)后的二叉樹. 84,68,42,66,48,22,36,26,4684,68,42,66,48,22,36,26,4668,66,42,46,48,22,36,26,8466,48,42,46,26,22,36,68,84.22,26,36,42,46,48,66,68,84堆和堆排序 T是一棵完全二叉樹,如果T中的任一結點的值不小于它的左子結點的值,且不小于它的右子結點的值,稱T是一個堆(heap)堆和堆排序 按層次序把樹T中的所有結點存放在數組an中,T是一個堆,an中元素具有的性質: 若2i+1=a2i+1; 若2i+2=a2i+284,68,42,66,48,22,36,26,4684,68,42,66,48,22,36,26,4668,66,