二叉排序树课程设计.doc

二叉排序树源代码：#include#include#include /符号常量#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define MAXSIZE 30#define OVERFLOW -2/自定义类型typedef int Status;typedef int TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchird,*rchild;BiTNode,*BiTree;/InOrderTraverse从小到大输出全部数据Status PrintElement(int e)printf(%d,e); printf( );return OK; Status InOrderTraverse(BiTree T,Status (* Visit)(int e)if(T)if(InOrderTraverse(T-lchird,Visit)if(Visit(T-data)if(InOrderTraverse(T-rchild,Visit) return OK; return ERROR;else return OK;/SearchBST查找关键字key的结点Status SearchBST(BiTree T,TElemType key,BiTree f,BiTree &p)if(!T)p=f;return FALSE;else if(T-data=key)p=T;return TRUE;else if(keydata)return SearchBST(T-lchird,key,T,p);/左子树中继续查找，找后继结点elsereturn SearchBST(T-rchild,key,T,p);/右子树中继续查找/SearchBST/InsertBST插入二叉排序树Status InsertBST(BiTree &T,TElemType key)BiTree p,s;if(!SearchBST(T,key,NULL,p)s=(BiTree)malloc(sizeof(BiTNode);s-data=key;s-lchird=s-rchild=NULL;if(!p)/二叉树若为空T=s;else if (keydata)p-lchird=s;/被插入的结点为左孩子elsep-rchild=s;/被插入的结点为右孩子return TRUE;elsereturn FALSE;/InsertBSTStatus Delete(BiTree &p)BiTree q,s;if(p-rchild=NULL)q=p;p=p-lchird;free(q);else if(p-lchird=NULL)q=p;p=p-rchild;free(q);elseq=p;s=p-lchird;while(s-rchild)q=s;s-rchild;p-data=s-data;if(q!=p)q-rchild=s-lchird;elseq-lchird=s-lchird;free(s);return TRUE;Status DeleteBST(BiTree &T,int key)if(!T)return FALSE;elseif(key=T-data)return Delete(T);else if(keydata)return DeleteBST(T-lchird,key);elsereturn DeleteBST(T-rchild,key);void mymenu()/菜单界面printf(nnn); printf(tt *-*tn); printf(tt *-二叉排序树的应用-*tn); printf(tt *-*tn); printf(tt *-1、查找 - *tn); printf(tt *- 2、插入 -*tn);printf(tt *-3、删除 -*tn);printf(tt *- 4、输出 -*tn);printf(tt *- 5、显示菜单-*tn);printf(tt *- 6、退出 -*tn);printf(tt *-*tn);void main()int i,Num;int aMAXSIZE=0;BiTree T=NULL,p=NULL;mymenu(); printf(建立二叉排序树:n);printf(请输入生成排序树的数据元素个数:);scanf(%d,&Num);while(Num=0) printf(此树为空，请重新输入！n);printf(请输入生成排序树的数据元素个数:); scanf(%d,&Num);printf(请输入生成排序树的数据:);for(i=0;i5) return;elseswitch(w)case 1:printf(请输入你要查找的数:n);int key,h;scanf(%d,&key);h=SearchBST(T,key,NULL,p);/if(TRUE=h)printf(此数存在!n);elseprintf(查找失败!n);break;case 2:printf(请输入你要插入的数:n);int s,k;scanf(%d,&s);k=SearchBST(T,s,NULL,p);/if(TRUE=k)printf(此数已经存在排序树中！n);elseInsertBST(T,s);printf(n插入成功！n);break;case 3:printf(请输入你要删除的数:n);int u,l;scanf(%d,&u);l=SearchBST(T,u,NULL,p);/if(FALSE=l)printf(删除操作失败！原排序树中不存在此数!n);elseDeleteBST(T,u);printf(n删除成功！n);break;case 4: Sta