二叉树的插入删除查找输出.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 main()int i,Num;int aMAXSIZE=0;BiTree T=NULL,p=NULL;Status (*Visit)(int); Visit=PrintElement;printf(请输入生成排序树的数据元素个数:);scanf(%d,&Num);printf(请输入生成排序树的数据:);for(i=0;iNum;i+)/读入一个数并插入到二叉生成树中scanf(%d,&ai);InsertBST(T,ai);/插入的过程相当于构建排序二叉树while(1)printf(1、查找 2、插入 3、删除 4、输出 5、退出);int w;printf(n请输入你要的操作:n);scanf(%d,&w);if(5=w)break;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);printf(n输出剩余