二叉排序树的实现

1、题目二叉排序树的实现一、实验目的与要求编写程序实现二叉排序树的节点插入，删除， 遍历，树型显示等操作。要求生成的二 叉排序树，不低于 4层，节点数目不少于17个，其中删除的三种情况都要在测试中给出，包括销毁、清空、节点删除(只删除该节点，保留其子树) ，遍历包括前中后三种，要用非 递归算法，最后提交报告(打印版和电子版)。二、实验方案程序头文件为"stdio.h"和"stdlib.h",部分宏定义如下所示：#define KeyType int#define EQ(a,b) (a)=(b)#define LT(a,b) (a)< (b)#defin

2、e LQ(a,b) (a)<=(b)二叉树的二叉链表存储表示以及先序遍历、中序遍历和后序遍历所运用到的栈的顺序存 储表示。typedef struct KeyType key;关键字域 ElemType;typedef struct BiTNode定义二叉树二叉链表ElemType data;struct BiTNode *lchild, *rchild;BiTNode,*BiTree,*SElemType;typedef structSElemType *base;SElemType *top;int stacksize;SqStack;源程序中包括了销毁树、清空树、关键字查找、节点插

3、入生成二叉排序树、删除节点、树形显示、以及先序遍历、中序遍历、后序遍历等等基本操作函数原型说明 int DestroyBiTree(BiTree &T) / 销毁树 if(T!=NULL)free(T);return 0; int ClearBiTree(BiTree &T) / 清空树 if(T!=NULL)(T->lchild=NULL;T->rchild=NULL;T=NULL;return 0;int SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p) 查找关键字 指针 p 返回 (if(!T)(p=

4、f;return FALSE;else if EQ(key,T->data.key)(p=T;return TRUE;else if LT(key,T->data.key)return SearchBST(T->lchild,key,T,p);elsereturn SearchBST(T->rchild,key,T,p);int InsertBST(BiTree &T,ElemType e) 插入节点元素(BiTree s,p;if(!SearchBST(T,e.key,NULL,p)(s=(BiTree)malloc(sizeof(BiTNode);s->

5、;data=e;s->lchild=s->rchild=NULL;if(!p)T=s;else if LT(e.key,p->data.key)p->lchild=s;elsep->rchild=s;return TRUE;else return FALSE;int ShowBST(BiTree T,int nlayer)/显示树形二叉排序树(int i;if(T=NULL)return FALSE;ShowBST(T->rchild,nlayer+1);for(i=0;i<nlayer;i+)printf(" ");printf(

6、"%dn",T->data);ShowBST(T->lchild,nlayer+1);return OK;int Visit(ElemType e) /Visit 函数(printf("%d ",e.key);return OK;int InitStack(SqStack &S) 构造空栈(S.base=(SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType);if(!S.base) exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_

7、SIZE;return OK;/InitStackint Push(SqStack &S, SElemType e) 插入元素 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;return OK;/Pushint P

8、op(SqStack &S,SElemType &e)删除栈顶，应用 e 返回其值(if(S.top=S.base) return ERROR;e=*-S.top;return OK;/Popint StackEmpty(SqStack S)判断是否为空栈(if(S.base=S.top) return TRUE;return FALSE;int PreOrderTraverse(BiTree T,int(*Visit)(ElemType e)先序遍历,运用栈(SqStack S;BiTree p;InitStack(S);p=T;while(p| !StackEmpty(S)

9、(if(p)(Push(S,p);if(!Visit(p->data) return ERROR;p=p->lchild;else(Pop(S, p);p=p->rchild;return OK;int InOrderTraverse(BiTree T, int(*Visit)(ElemType e) 中序遍历，运用栈 (SqStack S;BiTree p;InitStack(S);p=T;while(p| !StackEmpty(S)(if(p)(Push(S,p);p=p->lchild;else(Pop(S,p);if(!Visit(p->data) re

10、turn ERROR;p=p->rchild;return OK;int PostOrderTraverse(BiTree T,int(*Visit)(ElemType e) / 后序遍历，运用栈 (SqStack S,SS;BiTree p;InitStack(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,

11、p);if(!Visit(p->data) return ERROR; return OK; int Delete(BiTree &p) / 三种删除节点的操作实现 BiTree q,s; if(!p->rchild)右子树为空 q=p; p=p->lchild; free(q); else if(!p->lchild)左子树为空 q=p; p=p->rchild; free(q); else q=p; s=p->lchild; while(s->rchild) q=s; s=s->rchild; p->data=s->dat

12、a; if(q!=p) q->rchild=s->lchild; else q->lchild=s->lchild; delete s; return TRUE; int DeleteBST(BiTree &T,KeyType key) / 实现二叉排序树的删除操作 if(!T) return FALSE;else查找关键字/二叉树节点数值插入/树形显示二叉排序树删除关键字/先序遍历、中序遍历、后序遍历if (EQ(key,T->data.key)/T->data.key 等于 keyreturn Delete(T);else if (LT(key,

13、T->data.key) /T->data.key 是否小于 key return DeleteBST(T->lchild,key);elsereturn DeleteBST(T->rchild,key);return 0;源程序主函数为：void main ()(int i,nlayer;ElemType k,d;BiTree BT,p;BT=NULL;p=NULL;nlayer=1;printf("请输入插入的二叉树节点的数值(输入数字0结束节点赋值)：n");scanf("%d",&k.key);for(i=0;k.

14、key!=NULL;i+)(if(!SearchBST(BT,k.key,NULL,p)(InsertBST(BT,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(&qu

15、ot;先序遍历为：");PreOrderTraverse(BT,Visit);printf("n中序遍历为：");InOrderTraverse(BT, Visit);printf("n后序遍历为：");PostOrderTraverse(BT,Visit);printf("n清空该二叉排序树.n”);清空二叉树ClearBiTree(BT);ShowBST(BT,nlayer);printf("n销毁该二叉排序树.n");/销毁二叉树ClearBiTree(BT);三、实验结果和数据处理运行过程中，输入节点数值为

16、：45 , 30, 59, 24, 10, 55, 40, 53, 28, 49, 12, 50, 37,62, 90, 88, 93,运行界面如下：吸Filesvc+lSDev98lyProjscts序材ID-bu小二又排. * 1口I隋输入插入的二卫树节点的数值（输入数字。结束节点赋值）=4B30E?241 0切4053Q812S&37£2丽93删除右子树为空的节点 53,运行结果如下:-lnlxl JD: Progra> Filesvc+vci：装5腿=98丫1：（1 jeci:邑气二,又排序树'DebugZl又排,302810.输入删除的数据：5342

17、fl20 -1树12序-tiT 为为为契 历历历二 遍遍遍该 ffffffs42 035 482 422 11012 284037595549566290889330 37404S49ER55596288909337 4A3&504955889390625945*ress anu key tu continue删除左子树为空的节点 62,运行界面如下:D: Progra> Filesvc+vc装'SDer98MyrPrD jects、二又排序WDebug二又排. .10请输入删除的数据：6293为为为叉历历历二遍遍遍该先中后清82211042 035 473 03824221 010 4 73 4 28 2 01 2 140 375955534950889340 45495053555988909330 504953558893905945453710为为为叉历历历二遍遍逊该先中后清435559S73 04820i21 035 445 40473 031822110218 -2树10bir4 0 5 03 0 4 78 8 55 3 S-M XlS销毁该二叉排序树.Press any key to cont in Lie删除两个子树都不为空的节点24,运行界面为：国 *D: Pr