二叉排序树.doc

1. 2. typedef struct BiTNode/ struct BiTNode *lchild, *rchild; / BiTNode, *BiTree;3. #define ok 1#define error 0#define STACK_INIT_SIZE 100#define OVERFLOW -1#define STACKCRE 10#include#includetypedef int Status;typedef struct BiTNodeint data;struct BiTNode * lchild,* rchild;BiTNode,* BiTree;Status Search(BiTree T,int key,BiTree f,BiTree &p)if(!T)p=f;return NULL;else if(key=T-data)p=T;return ok;else if(keydata)return Search(T-lchild,key,T,p);else return Search(T-rchild,key,T,p);Status Insert(BiTree &T,int e)BiTree p,s;if(!Search(T,e,NULL,p)s=(BiTree)malloc(sizeof(BiTNode);s-data=e;s-lchild=NULL;s-rchild=NULL;if(!p)T=s;else if(edata)p-lchild=s;else p-rchild=s;return ok;else return false;Status CreateBiTree(BiTree &T,int n)int i;T=NULL;printf( n);for(i=0;irchild)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-data;if(q!=p)q-rchild=s-lchild;elseq-lchild=s-lchild;delete s;return ok;Status DeleteBST(BiTree &T,int key)if(!T)return false;else if(key=T-data)return Delete(T);else if(keydata)return DeleteBST(T-lchild,key);else return DeleteBST(T-rchild,key);Status PreOrder(BiTree T)if(T!=NULL)printf(%d ,T-data);PreOrder(T-lchild);PreOrder(T-rchild);return ok;bool InsertBST(BiTree &T,int key)BiTree p,s;if(!Search(T,key,NULL,p)s=(BiTree)malloc(sizeof(BiTNode);s-data=key;s-lchild=s-rchild=NULL;if(!p)T=s;else if(keydata)p-lchild=s;elsep-rchild=s;return ok;elsereturn error;int main()BiTree C,p;int N,Key;printf(Nn);scanf(%d,&N);CreateBiTree(C,N);loop :int num;printf(* 1. *n);printf(* 2. *n);printf(* 3. *n);printf(* 4. *n);printf(* 5. *n);scanf(%d,&num);switch(num)case 1:printf(:);scanf(%d,&Key);if(InsertBST(C,Key)printf(n);printf(n);PreOrder(C);printf(n);elseprintf(n);break;case 2:printf(:);scanf(%d,&Key);if(DeleteBST(C,Key)printf(n);if(C!=NULL)printf(n);elseprintf();printf(n);elseprintf(n);PreOrder(C);printf(n);break;case 3:printf(:);scanf(%d,&Key);if(Search(C,Key,NULL,p)printf(n);elsep