二叉排序樹(shù)的實(shí)現(xiàn)

1、題目二叉排序樹(shù)的實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康呐c要求編寫(xiě)程序?qū)崿F(xiàn)二叉排序樹(shù)的節(jié)點(diǎn)插入，刪除，遍歷，樹(shù)型顯示等操作。要求生成的二叉排序樹(shù)，不低于 4 層，節(jié)點(diǎn)數(shù)目不少于 17 個(gè)，其中刪除的三種情況都要在測(cè)試中給出，包括銷毀、清空、節(jié)點(diǎn)刪除(只刪除該節(jié)點(diǎn)，保留其子樹(shù))，遍歷包括前中后三種，要用非遞歸算法，最后提交報(bào)告(打印版和電子版)。二、實(shí)驗(yàn)方案程序頭文件為stdio.h和stdlib.h,部分宏定義如下所示：#defineKeyTypeint#defineEQ(a,b)(a)=(b)#defineLT(a,b)(a)(b)#defineLQ(a,b)(a)lchild=NULL;T-rchild=NULL

2、;T=NULL;)return0;)intSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p)查找關(guān)鍵字，指針 p 返回(if(!T)(p=f;returnFALSE;)elseifEQ(key,T-data.key)(p=T;returnTRUE;)elseifLT(key,T-data.key)returnSearchBST(T-lchild,key,T,p);elsereturnSearchBST(T-rchild,key,T,p);)intInsertBST(BiTree&T,ElemTypee)插入節(jié)點(diǎn)元素(BiTrees,p;

3、if(!SearchBST(T,e.key,NULL,p)(s=(BiTree)malloc(sizeof(BiTNode);s-data=e;s-lchild=s-rchild=NULL;if(!p)T=s;elseifLT(e.key,p-data.key)p-lchild=s;elsep-rchild=s;returnTRUE;)elsereturnFALSE;intShowBST(BiTreeT,intnlayer)顯示樹(shù)形二叉排序樹(shù)(inti;if(T=NULL)returnFALSE;ShowBST(T-rchild,nlayer+1);for(i=0;idata);ShowBST

4、(T-lchild,nlayer+1);returnOK;)intVisit(ElemTypee)/Visit 函數(shù)(printf(%d,e.key);returnOK;)intInitStack(SqStack&S)構(gòu)造空棧(S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;/InitStackintPush(SqStack&S,SElemTypee)插入元

5、素 e 為新棧頂(if(S.top-S.base=S.stacksize)(S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;returnOK;/PushintPop(SqStack&S,SElemType&e)刪除棧頂，應(yīng)用 e 返回其值(if(S.top=S.base)returnERRO

6、R;e=*-S.top;returnOK;/PopintStackEmpty(SqStackS)判斷是否為空棧(if(S.base=S.top)returnTRUE;returnFALSE;intPreOrderTraverse(BiTreeT,int(*Visit)(ElemTypee)/先序遍歷，運(yùn)用棧(SqStackS;BiTreep;InitStack(S);p=T;while(p|!StackEmpty(S)(if(p)(Push(S,p);if(!Visit(p-data)returnERROR;p=p-lchild;else(Pop(S,p);p=p-rchild;returnO

7、K;intInOrderTraverse(BiTreeT,int(*Visit)(ElemTypee)中序遍歷，運(yùn)用棧(SqStackS;BiTreep;InitStack(S);p=T;while(p|!StackEmpty(S)if(p)(Push(S,p);p=p-lchild;)else(Pop(S,p);if(!Visit(p-data)returnERROR;p=p-rchild;)returnOK;)intPostOrderTraverse(BiTreeT,int(*Visit)(ElemTypee)/后序遍歷，運(yùn)用棧(SqStackS,SS;BiTreep;InitStack(

8、S);InitStack(SS);p=T;while(p|!StackEmpty(S)(if(p)(Push(S,p);Push(SS,p);p=p-rchild;)else(if(!StackEmpty(S)(Pop(S,p);p=p-lchild;)while(!StackEmpty(SS)(Pop(SS,p);if(!Visit(p-data)returnERROR;)returnOK;)intDelete(BiTree&p)三種刪除節(jié)點(diǎn)的操作實(shí)現(xiàn)BiTreeq,s;if(!p-rchild)右子樹(shù)為空q=p;p=p-lchild;free(q);)elseif(!p-lchil

9、d)左子樹(shù)為空q=p;p=p-rchild;free(q);)elseq=p;s=p-lchild;while(s-rchild)q=s;s=s-rchild;)p-data=s-data;if(q!=p)q-rchild=s-lchild;elseq-lchild=s-lchild;deletes;)returnTRUE;)intDeleteBST(BiTree&T,KeyTypekey)/實(shí)現(xiàn)二叉排序樹(shù)的刪除操作if(!T)returnFALSE;elseif(EQ(key,T-data.key)/T-data.key 等于 keyreturnDelete(T);elseif(LT

10、(key,T-data.key)T-data.key 是否小于 keyreturnDeleteBST(T-lchild,key);elsereturnDeleteBST(T-rchild,key);return0;源程序主函數(shù)為：voidmain()(inti,nlayer;ElemTypek,d;BiTreeBT,p;BT=NULL;p=NULL;nlayer=1;printf(請(qǐng)輸入插入的二叉樹(shù)節(jié)點(diǎn)的數(shù)值(輸入數(shù)字scanf(%d,&k.key);for(i=0;k.key!=NULL;i+)(if(!SearchBST(BT,k.key,NULL,p)(InsertBST(BT,

11、k);scanf(%d,&k.key);else(printf(輸入數(shù)據(jù)重復(fù)！n);return;printf(二叉排序樹(shù)樹(shù)形輸出為：n);ShowBST(BT,nlayer);printf(請(qǐng)輸入刪除的數(shù)據(jù)：)；scanf(%d,&d.key);DeleteBST(BT,d.key);ShowBST(BT,nlayer);printf(先序遍歷為：);PreOrderTraverse(BT,Visit);printf(n 中序遍歷為：);InOrderTraverse(BT,Visit);printf(n 后序遍歷為：);PostOrderTraverse(BT,Visit)

12、;printf(n 清空該二叉排序樹(shù).n);/清空二叉樹(shù)ClearBiTree(BT);0 結(jié)束節(jié)點(diǎn)賦值)：n);/查找關(guān)鍵字二叉樹(shù)節(jié)點(diǎn)數(shù)值插入樹(shù)形顯示二叉排序樹(shù)刪除關(guān)鍵字/先序遍歷、中序遍歷、后序遍歷ShowBST(BT,nlayer);printf(n 銷毀該二叉排序樹(shù).n);銷毀二叉樹(shù)ClearBiTree(BT);三、實(shí)驗(yàn)結(jié)果和數(shù)據(jù)處理運(yùn)行過(guò)程中，輸入節(jié)點(diǎn)數(shù)值為：45,30,59,24,10,55,40,53,28,49,12,50,37,62,90,88,93,運(yùn)行界面如下：曲Filesvc+vc3clSDev98lyPro-jo|常輸入插入的二只樹(shù)節(jié)點(diǎn)的數(shù)值（輸入數(shù)字謔吉束節(jié)點(diǎn)賦值

13、）:4B30E?2410卜4053Q8同12S0372向的93刪除右子樹(shù)為空的節(jié)點(diǎn) 53,運(yùn)行結(jié)果如下:*D:PrograFil6svc+vc女裝、EDe=98T yrPr( (js二叉指序樹(shù)TDebug、二又排.302810石輸入刪除的數(shù)據(jù)：53*ressanukeutucontinue口兇為為為只歷歷歷二遍遍遍該空42420 035354 48 8242 22 21 14 42 2flfl2 20 0- -工樹(shù)1 12 2序:i:iT T1228403759554956629088933037404S49ER555962889093374A30504955889390625945刪除左子樹(shù)

14、為空的節(jié)點(diǎn) 62,運(yùn)行界面如下:D:PrugraAFilesvc-H-vc=8tMSDev98MyProjectsZlxffffWDebugZlxff.-10請(qǐng)輸入刪除的數(shù)據(jù)：6293銷毀該二叉排序樹(shù).Pressanykeytocontinue刪除兩個(gè)子樹(shù)都不為空的節(jié)點(diǎn) 24,運(yùn)行界面為：國(guó)*D:PrograFilewEdAvc安裝IBSDc7981開(kāi)工口jcctwh二叉排序樹(shù)Dcbugh二叉排.10請(qǐng)輸入刪除的數(shù)據(jù)：2493招毀該二反排序樹(shù).essaoykeytocontinue為為為叉歷歷歷二遍遍遍該先中后清8 82 22 21 110104 420203 37 73 30 03 38 82 24 42 22 2101004047 73 34 42 2828201012 21 1-MXlS37375 53 32 25 50 033335 599499480980989895 508082 29 98 86 62 22 20 06666919109093 355955995895845845833335 555555 55 50 03 3sSsS5 5 99995445447507503 34 45 50 000004 4434