二叉排序树的实现

1、题目二叉排序树的实现一、实验目的与要求编写程序实现二叉排序树的节点插入，删除，遍历，树型显示等操作。要求生成的二叉排序树，不低于 4 层，节点数目不少于 17 个，其中删除的三种情况都要在测试中给出，包括销毁、清空、节点删除(只删除该节点，保留其子树)，遍历包括前中后三种，要用非递归算法，最后提交报告(打印版和电子版)。二、实验方案程序头文件为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)查找关键字，指针 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)插入节点元素(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 函数(printf(%d,e.key);returnOK;)intInitStack(SqStack&S)构造空栈(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)三种删除节点的操作实现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)/实现二叉排序树的删除操作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;源程序主函数为：voidmain()(inti,nlayer;ElemTypek,d;BiTreeBT,p;BT=NULL;p=NULL;nlayer=1;printf(请输入插入的二叉树节点的数值(输入数字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(输入数据重复！n);return;printf(二叉排序树树形输出为：n);ShowBST(BT,nlayer);printf(请输入删除的数据：)；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 结束节点赋值)：n);/查找关键字二叉树节点数值插入树形显示二叉排序树删除关键字/先序遍历、中序遍历、后序遍历ShowBST(BT,nlayer);printf(n 销毁该二叉排序树.n);销毁二叉树ClearBiTree(BT);三、实验结果和数据处理运行过程中，输入节点数值为：45,30,59,24,10,55,40,53,28,49,12,50,37,62,90,88,93,运行界面如下：曲Filesvc+vc3clSDev98lyPro-jo|常输入插入的二只树节点的数值（输入数字谑吉束节点赋值

13、）:4B30E?2410卜4053Q8同12S0372向的93删除右子树为空的节点 53,运行结果如下:*D:PrograFil6svc+vc女装、EDe=98T yrPr( (js二叉指序树TDebug、二又排.302810石输入删除的数据：53*ressanukeutucontinue口凶为为为只历历历二遍遍遍该空42420 035354 48 8242 22 21 14 42 2flfl2 20 0- -工树1 12 2序:i:iT T1228403759554956629088933037404S49ER555962889093374A30504955889390625945删除左子树

14、为空的节点 62,运行界面如下:D:PrugraAFilesvc-H-vc=8tMSDev98MyProjectsZlxffffWDebugZlxff.-10请输入删除的数据：6293销毁该二叉排序树.Pressanykeytocontinue删除两个子树都不为空的节点 24,运行界面为：国*D:PrograFilewEdAvc安装IBSDc7981开工口jcctwh二叉排序树Dcbugh二叉排.10请输入删除的数据：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