数据结构课程设计--二叉排序树.docx

江 苏 大 学数据结构课程设计学院 计算机学院班级 信息安全1001学号 3100604001完成日期 2012年1月8日实验内容：二叉排序树的建立，插入，删除和查找给出一组关键值，建立相应的二叉排序树，完成（1） 结点的删除操作。要求可以实现删除结点，叶子结点以及其他任意功能；（2） 插入一个新结点的操作；（3） 对给定的值在二叉排序树进行查找；（4） 随时显示操作结果。实验说明：二叉排序树的储蓄结构typedef struct bitnodeint data;struct bitnode *lchild,*rchild;bitnode,*bitree; 二叉排序树的插入 1. 若p是空树，则将结点s作为根结点插入；否则2. 若s-datap-data，则把结点s插入到p的左子树中；否则3. 把结点s插入到p的右子树中。 二叉排序树的删除 1. 若结点p是叶子，则直接删除结点p； 2. 若结点p只有左子树，则只需重接p的左子树； 若结点p只有右子树，则只需重接p的右子树； 3. 若结点p的左右子树均不空，则 3.1 查找结点p的右子树上的最左下结点s以及结点s的双亲结点par；3.2 将结点s数据域替换到被删结点p的数据域；3.3 若结点p的右孩子无左子树，则将s的右子树接到par的右子树上；否则，将s的右子树接到结点par的左子树上；3.4 删除结点s；实验分析程序的主要流程图：否是开始建树： 依次输入i个关键字 插入二叉排序树中 中序输出创建过程删除任意结点插入一个结点查找关键字中序输出操作后二叉排序树是否继续结束（1） 主要模块： 1）主函数模块 main()建立i个关键字的二叉排序树并输出；从二叉树排序树t中删除任意结点,其关键字为dkey；在二叉树排序树t中，插入一个结点ikey,其关键字为ikey；在二叉排序树t中递归查找关键字等于 fkey 的数据元素；2）创建二叉排序树模块bitree creatbst(bitree t int key)建立i个关键字的二叉排序树； 返回结点t； 输出过程； 3）删除模块void deletebst(bitree t, int key)从二叉树排序树t中删除任意结点,其关键字为key； 可以实现删除根结点、叶子结点以及其它任意结点的功能； 4）插入模块int insertbst(bitree t,int key)在二叉树排序树t中，插入一个结点s(递归算法)； 被creatbst函数调用；5）查找模块 int searchbst(bitree t,int key)在根指针t所指二叉排序树中递归查找关键字等于 key 的数据元素； 若成功，返回指向该数据元素结点的指针； 否则返回空指针；2.源程序代码：#include#include#include#define error 0#define ture 1#define ok 1#define null 0typedef struct bitnodeint data;struct bitnode *lchild,*rchild;bitnode,*bitree;/*以下是建立一个二叉排序树*/bitree createbst(bitree t,int key)bitree oldp=t;bitree p=t;int flag;if(t=null)t=(bitree)malloc(sizeof(bitnode);t-data=key;t-lchild=t-rchild=null;elsewhile(p)oldp=p;p=(flag=keydata)?p-lchild:p-rchild; if(flag)oldp-lchild=(bitree)malloc(sizeof(bitnode); oldp-lchild-data=key;oldp-lchild-lchild=oldp-lchild-rchild=null;elseoldp-rchild=(bitree)malloc(sizeof(bitnode); oldp-rchild-data=key;oldp-rchild-lchild=oldp-rchild-rchild=null;return t; void inorder(bitree t)if(t!=null) inorder(t-lchild); printf(%3d#,t-data); inorder(t-rchild);/*以下是在一个二叉排序树查找一个数是否存在*/int searchbst(bitree t,int key)bitree p=t;if(t=null)return 0;while(p)if(p-data=key)return 1;if(keydata)p=p-lchild;/在左子树中继续查找elsep=p-rchild;/在右子树中继续查找return 0; /*以下是在一个二叉排序树插入一个给定的值*/int insertbst(bitree t,int key)bitree s,p,f;p=t;f=null;if(!searchbst(t,key)s=(bitree)malloc(sizeof(bitnode);if(!s)printf(申请空间失败！n);exit(0);s-data=key;s-lchild=null;s-rchild=null;while(p)f=p;p=keydata?p-lchild:p-rchild;if(keyf-data)f-rchild=s;elsef-lchild=s;inorder(t);printf(n);return 1;elsereturn 0;/*以下是在一个二叉排序树删除一个给定的值*/void deletebst(bitree tptr,int key) bitnode* parent=null,*p=tptr,*q,*child; while(p)if(p-data=key)break;parent=p;p=(keydata)?p-lchild:p-rchild;if(!p)return;q=p;if(q-lchild&q-rchild)for(parent=q,p=q-rchild;p-lchild;parent=p,p=p-lchild);child=(p-lchild)?p-lchild:p-rchild;if(!parent)tptr=child;elseif(p=parent-lchild)parent-lchild=child;else parent-rchild=child; if(p!=q) q-data=p-data;free(p);/*主函数*/void main()bitree t;int i=0,dkey,fkey, ikey,flag,s; t=null; for(;i6;i+) printf(输入第%d个关键字：n,i+1); scanf(%d,&ikey);t=createbst(t,ikey); printf(output the result:); inorder(t);printf(n1 for deleten);printf(2 for insertbstn);printf(3 for searchbstn);printf(please choose the function:n);scanf(%d,&flag);while(flag)switch(flag)case 1: printf(nplease input the number to delete:n); scanf(%d,&dkey); deletebst(t,dkey); printf(output the result:); inorder(t);printf(n);break; case 2: printf(nplease input the number to insertbst:n); scanf(%d,&ikey); s=insertbst(t,ikey); printf(output the result:); inorder(t);printf(n);break; case 3: printf(nplease input the number to find:n); scanf(%d,&fkey); s=searchbst(t,fkey); if(s) printf(we find %dn,fkey); else printf(we can not find it!n);break; default : printf(sorry we do not have the function!n);break; printf(please choose the function:n);scanf(%d,&flag);3测试结果4 实验总结通过这次的实验，我认识到：仅仅掌握课本上的知识是不够的，在实际操作时，常常遇到一些问题，自己看不懂，更无法解决。不过，经过自己不断的思考，尝试着去更改代码中