二叉排序树.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(创建N个节点的排序二叉树：n);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);elseprintf(查找失败！n);break;case 4:PreOrder(C);printf(n);break;case 5:exit(1);break; printf(继续选择操作!n); goto loop; return ok;4. 实验总结：通过这次的实验，我认识到：仅仅掌握课本上的知识是不够的，在实际操作时， 常常遇到一些问题，自己看不懂，更无法解决。不过，经过自己不断的思考，尝 试着去更改代码中出现的问题。虽然开始很困难，但在老师和同学的帮助下，我 逐渐的熟悉了许多操作，为后继工作的顺利进行做了准备。 个人的力量是薄弱的，我学会了咨询别人，不再胆怯，不再保守。 在过程 中和同学相互讨论，询问老师，不断进步。 也许，我们可以说，编一个程仅仅是开始，调试和运行相比之下更难。实践 中收获的远比想象的多。 看到自己完成了所要求的任务，有一种无法用言语来形容的欣慰之感，这也 是无法从学习书本知识中得到的。