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

1、題目二叉排序樹的實現(xiàn)一、實驗目的與要求編寫程序?qū)崿F(xiàn)二叉排序樹的節(jié)點插入，刪除，遍歷，樹型顯示等操作。要求生成的二叉排序樹，不低于 4 層，節(jié)點數(shù)目不少于 17 個，其中刪除的三種情況都要在測試中給出，包括銷毀、清空、節(jié)點刪除(只刪除該節(jié)點，保留其子樹)，遍歷包括前中后三種，要用非遞歸算法，最后提交報告(打印版和電子版)。二、實驗方案程序頭文件為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é)點元素(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)顯示樹形二叉排序樹(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)刪除棧頂，應用 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)/先序遍歷，運用棧(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)中序遍歷，運用棧(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)/后序遍歷，運用棧(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é)點的操作實現(xiàn)BiTreeq,s;if(!p-rchild)右子樹為空q=p;p=p-lchild;free(q);)elseif(!p-lchil

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

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

14、為空的節(jié)點 62,運行界面如下:D:PrugraAFilesvc-H-vc=8tMSDev98MyProjectsZlxffffWDebugZlxff.-10請輸入刪除的數(shù)據(jù)：6293銷毀該二叉排序樹.Pressanykeytocontinue刪除兩個子樹都不為空的節(jié)點 24,運行界面為：國*D:PrograFilewEdAvc安裝IBSDc7981開工口jcctwh二叉排序樹Dcbugh二叉排.10請輸入刪除的數(shù)據(jù)：2493招毀該二反排序樹.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