1、數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)報(bào)告題目：平衡二叉樹的操作演示班級：信息管理與信息系統(tǒng)11-1姓名：崔佳學(xué)號：201101050903完成日期：2013.06.25一、需求分析1. 初始，平衡二叉樹為空樹，操作界面給出兩棵平衡二叉樹的顯示、查找、插入、刪除、銷毀、合并兩棵樹，幾種選擇。其中查找、插入和刪除操作均要提示用戶輸入關(guān)鍵字。每次插入或刪除一個(gè)節(jié)點(diǎn)后都會(huì)更新平衡二叉樹的顯示。2. 平衡二叉樹的顯示采用凹入表形式。3.每次操作完畢后都會(huì)給出相應(yīng)的操作結(jié)果，并進(jìn)入下一次操作，知道用戶選擇退出二、概要設(shè)計(jì)1.平衡二叉樹的抽象數(shù)據(jù)類型定義：ADT BalancedBinaryTree 數(shù)據(jù)對象D：D是具有相同特性的

2、數(shù)據(jù)元素的集合。各個(gè)數(shù)據(jù)元素均含有類型相同，可唯一標(biāo)志的數(shù)據(jù)元素的關(guān)鍵字。 數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個(gè)集合。 基本操作P： InitAVL(BSTree& T) 操作結(jié)果：構(gòu)造一個(gè)空的平衡二叉樹T DestroyAVL(BSTree& T) 初始條件：平衡二叉樹T存在 操作結(jié)果：銷毀平衡二叉樹T SearchAVL(BSTree T,int key) 初始條件：平衡二叉樹T存在，key為和關(guān)鍵字相同類型的給定值 操作結(jié)果：若T中存在關(guān)鍵字和key相等的數(shù)據(jù)元素，則返回指向該元素的指針，否則為空 InsertAVL(BSTree& T,int key,Status&am

3、p; taller) 初始條件：平衡二叉樹T存在，key和關(guān)鍵字的類型相同 操作結(jié)果：若T中存在關(guān)鍵字等于key的數(shù)據(jù)元素則返回，若不存在則插入一個(gè)關(guān)鍵字為key的元素 DeleteAVL(BSTree& T,int &key,Status& lower) 初始條件：平衡二叉樹T存在，key和關(guān)鍵字的類型相同 操作結(jié)果：若T中存在關(guān)鍵字和key相同的數(shù)據(jù)元素則刪除它ADT BalancedBinaryTree2.本程序包含二個(gè)模塊1） 主程序模塊：void main（） 接收命令； While(“命令”！“退出”) 處理命令； 清屏并得新打印提示信息； 接收下一條命令；

4、2） 平衡二叉樹基本操作實(shí)現(xiàn)平衡二叉樹的抽象數(shù)據(jù)類型的各函數(shù)原型。各模塊之間的調(diào)用關(guān)系如下：主程序模塊平衡二叉樹模塊三、詳細(xì)設(shè)計(jì)1. 根據(jù)題目要求和平衡二叉樹的操作特點(diǎn)，平衡二叉樹采用整數(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)基本操作的函數(shù)原型：#define LH 1 /左高#define EH 0 /等高#define RH -1 /右高#define TRUE 1 #define FALSE 0#define ERROR 0#define OK 1typedef int Status;typedef int ElemType; /本程序處理數(shù)據(jù)對象為整型typedef struct BSTNode ElemTyp

5、e data;int bf;struct BSTNode *lchild,*rchild;BSTNode,*BSTree;1）平衡二叉樹基本操作實(shí)現(xiàn)/構(gòu)造平衡二叉樹TStatus InitAVL(BSTree &T) T=NULL; return OK;/對以*p為根的二叉樹作左旋處理,處理之后p指向新的樹根結(jié)點(diǎn)/即旋轉(zhuǎn)處理之前的右子樹的根結(jié)點(diǎn)void L_Rotate(BSTree &p) BSTree rc; rc=p->rchild; p->rchild=rc->lchild; rc->lchild=p; p=rc;/對以*p為根的二叉樹作右旋處理

6、,處理之后p指向新的樹根結(jié)點(diǎn)/即旋轉(zhuǎn)處理之前的左子樹的根結(jié)點(diǎn)void R_Rotate(BSTree &p) BSTree lc; lc=p->lchild; p->lchild=lc->rchild; lc->rchild=p; p=lc;/對以指針T所指結(jié)點(diǎn)為根的二叉樹作右平衡處理/本算法結(jié)束時(shí)T指向新的根結(jié)點(diǎn)void LeftBalance(BSTree &T) BSTree lc,rd; lc=T->lchild; switch(lc->bf) case LH: T->bf=lc->bf=EH; R_Rotate(T);

7、break; case RH: rd=lc->rchild; switch(rd->bf) case LH: T->bf=RH; lc->bf=EH; break; case EH: T->bf=lc->bf=EH; break; case RH: T->bf=EH; lc->bf=LH; break; rd->bf=EH; L_Rotate(T->lchild); R_Rotate(T); /對以指針T所指結(jié)點(diǎn)為根的二叉樹作右平衡處理/本算法結(jié)束時(shí)T指向新的根結(jié)點(diǎn)void RightBalance(BSTree& T) BS

8、Tree rc,rd; rc=T->rchild; switch(rc->bf) case RH: T->bf=rc->bf=EH; L_Rotate(T); break; case LH: rd=rc->lchild; switch(rd->bf) case RH: T->bf=LH; rc->bf=EH; break; case EH: T->bf=rc->bf=EH; break; case LH:T->bf=EH; rc->bf=RH; break; rd->bf=EH; R_Rotate(T->rch

9、ild); L_Rotate(T); /查找關(guān)鍵字為key的結(jié)點(diǎn)/如有返回指向此結(jié)點(diǎn)的指針，如無返回空Status SearchAVL(BSTree T,int e)if(!T) return ERROR;if(T->data=e) printf("t結(jié)果: %d%dnt",T->data,T->bf); return OK; else if(T->lchild)if(SearchAVL(T->lchild,e)return OK; if(T->rchild)if(SearchAVL(T->rchild,e)return OK; r

10、eturn ERROR; /若在平衡的二叉排序樹中不存在和e相同的關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)數(shù)據(jù)元素為e的新結(jié)點(diǎn)并返回1，否則返回0。/若因插入而使二叉排序樹失去平衡，則做平衡旋轉(zhuǎn)處理/布爾變量taller反映T長高與否Status InsertAVL(BSTree &T,ElemType e,Status &taller) if(!T) T=(BSTree)malloc(sizeof(BSTNode); T->data=e; T->lchild=T->rchild=NULL; T->bf=EH; taller=TRUE; else if(e=T->

11、data) taller=FALSE; return FALSE; if(e<T->data) if(!InsertAVL(T->lchild,e,taller) return FALSE; if(taller) switch(T->bf) case LH: LeftBalance(T); taller=FALSE; break; case EH: T->bf=LH; taller=TRUE; break; case RH: T->bf=EH; taller=FALSE; break; else if(!InsertAVL(T->rchild,e,ta

12、ller) return FALSE; if(taller) switch(T->bf) case RH: RightBalance(T); taller=FALSE; break; case EH: T->bf=RH; taller=TRUE; break; case LH: T->bf=EH; taller=FALSE; break; return TRUE; /打印空格void Printblank(int i) while(i >=0) printf(" "); i-; /以凹入表的形式顯示平衡二叉樹Tvoid ViewTree(BSTree

13、 T,int i) if(T) Printblank(i); printf("%d%dn",T->data,T->bf); else Printblank(i); printf("NULLn"); return; ViewTree(T->lchild,i+5); ViewTree(T->rchild,i+5);/銷毀平衡二叉樹void DestroyAVL(BSTree &T)if(T)if(T->lchild)DestroyAVL(T->lchild);if(T->rchild)DestroyAVL(T

14、->rchild);free(T);T=NULL;Status Delete(BSTree& p,int &e,int &flag) BSTree q,s; if(!p->rchild) q=p; if(p->lchild) p->lchild->bf=p->bf; e=p->lchild->data; p=p->lchild; free(q); flag=1; else if(!p->lchild) q=p; p->rchild->bf=p->bf; e=p->rchild->d

15、ata; p=p->rchild; free(q); flag=1; else q=p; s=p->lchild; while(s->rchild)q=s; s=s->rchild; p->data=s->data; if(q!=p)q->rchild=s->lchild; else q->lchild=s->lchild; p->bf=RH; e=q->data; free(s); return TRUE; /若二叉排序樹T中存在關(guān)鍵字等于e的數(shù)據(jù)元素時(shí)，則刪除該數(shù)據(jù)元素結(jié)點(diǎn)/并返回TRUE，否則返回FALSEStatu

16、s DeleteBST(BSTree& T,int &e,int &flag) if(!T)return FALSE; else if(e=T->data)return Delete(T,e,flag); else if(e<T->data) if(!DeleteBST(T->lchild,e,flag) return FALSE; return TRUE; else if(!DeleteBST(T->rchild,e,flag) return FALSE; return TRUE; void DelBalance(BSTree&

17、T,int e, Status &lower,int &flag) if(!T) lower=TRUE; return; if(e=T->data)if(flag=1) switch(T->bf)case RH:case LH: T->bf=EH; lower=TRUE; break; else switch(T->bf) case RH: lower=FALSE; break; case EH: T->bf=LH; lower=FALSE; break; case LH: LeftBalance(T); lower=TRUE; break; re

18、turn ; if(e<T->data) DelBalance(T->lchild,e,lower,flag); if(lower) switch(T->bf) case LH: T->bf=EH; lower=TRUE; break; case EH:T->bf=RH; lower=FALSE; break; case RH:RightBalance(T); lower=TRUE; break; if(e>T->data) DelBalance(T->rchild,e,lower,flag); if(lower) switch(T->

19、;bf) case RH: T->bf=EH; lower=TRUE; break; case EH: T->bf=LH; lower=FALSE; break; case LH: LeftBalance(T); lower=TRUE; break; return ;/刪除平衡二叉樹結(jié)點(diǎn)Status DeleteAVL(BSTree &T,int &e,Status &lower)int flag=0;if(!DeleteBST(T,e,flag) return FALSE;else DelBalance(T,e,lower,flag);return TRU

20、E;2）主函數(shù)Main及其它輔助函數(shù)的實(shí)現(xiàn) /*主函數(shù)*/void main() void Print(); void About(); BSTree T,t,p; int e,s; Status taller,lower; InitAVL(T); InitAVL(t); InitAVL(p); Print(); scanf("%d",&s); while(s!=6) switch(s) case 1: /顯示 printf("按凹入表形式打印二叉樹結(jié)構(gòu)：n"); printf("T:n"); PrintTree(T,1);

21、printf("t:n"); PrintTree(t,1); break; case 2: /查找 printf("t選擇樹(1,2):"); scanf("%d",&s); printf("t關(guān)鍵字(整數(shù)):"); scanf("%d",&e); if(s=1) s=SearchAVL(T,e); if(s=2) s=SearchAVL(t,e); if(!s) printf("t查找失敗nt"); break; case 3: /插入 printf(&qu

22、ot;t選擇樹(1-T,2-t):"); scanf("%d",&s); printf("t關(guān)鍵字(整數(shù)):"); scanf("%d",&e); if(s=1) InsertAVL(T,e,taller); printf("T:n"); PrintTree(T,1); if(s=2) InsertAVL(t,e,taller); printf("t:n"); PrintTree(t,1); break; case 4: /刪除 printf("t選擇樹(1-

23、T,2-t):"); scanf("%d",&s); printf("t關(guān)鍵字(整數(shù)):"); scanf("%d",&e); if(s=1)if(DeleteAVL(T,e,lower)printf("t刪除成功nt");elseprintf("t刪除失敗nt"); if(s=2)if(DeleteAVL(t,e,lower)printf("t刪除成功nt");elseprintf("t刪除失敗nt"); break; case 5: /銷毀 printf("t選擇樹(1,2):"); scanf("%d",&s); if(s=1) DestroyAVL(T); if(s=2) DestroyAVL(t); pr