合肥学院计算机科学与技术系课程设计报告2009 ～2010 学年第二学期课程数据结构与算法课程设计名称二叉排序树运算学生姓名顾成方学号********** 专业班级08计科(2) 指导教师王昆仑张贯虹2010 年 5 月题目：（二叉排序树运算问题）设计程序完成如下要求：对一组数据构造二叉排序树，并在二叉排序树中实现多种方式的查找。
基本任务：⑴选择合适的储存结构构造二叉排序树；⑵对二叉排序树T作中序遍历，输出结果；⑶在二叉排序树中实现多种方式的查找，并给出二叉排序树中插入和删除的操作。
⑷尽量给出“顺序和链式”两种不同结构下的操作，并比较。
一、问题分析和任务定义本次程序需要完成如下要求：首先输入任一组数据，使之构造成二叉排序树，并对其作中序遍历，然后输出遍历后的数据序列；其次，该二叉排序树能实现对数据（即二叉排序树的结点）的查找、插入和删除等基本操作。
实现本程序需要解决以下几个问题：1、如何构造二叉排序树。
2、如何通过中序遍历输出二叉排序树。
3、如何实现多种查找。
4、如何实现插入删除等操作。
二叉排序树的定义：⑴其左子树非空，则左子树上所有结点的值均小于根结点的值。
⑵若其右子树非空，则右子树上所有结点的值大于根结点的值。
⑶其左右子树也分别为二叉排序树。
本问题的关键在于对于二叉排序树的构造。
根据上述二叉排序树二叉排序树的生成需要通过插入算法来实现：输入（插入）的第一个数据即为根结点；继续插入，当插入的新结点的关键值小于根结点的值时就作为左孩子，当插入的新结点的关键值大于根结点的值时就作为右孩子；在左右子树中插入方法与整个二叉排序树相同。
当二叉排序树建立完成后，要插入新的数据时，要先判断已建立的二叉排序树序列中是否已有当前插入数据。
因此，插入算法还要包括对数据的查找判断过程。
本问题的难点在于二叉排序树的删除算法的实现。
删除前，首先要进行查找，判断给出的结点是否已存在于二叉排序树之中；在删除时，为了保证删除结点后的二叉树仍为二叉排序树，要考虑各种情况，选择正确的方法。
删除操作要分几种情况讨论，在后面有介绍。
二、概要设计和数据结构选择用二叉链表作为二叉排序树的存储结构，其中key为结点关键值，*lchlid、*rchild 分别为左右孩子指针。
该程序的结构如下图所示：三、详细设计和编码首先定义二叉排序树的数据类型如下：typedef struct node{int key;//关键字项struct node *lchild,*rchild;//左右孩子指针}Bstnode;然后按一定顺序来编写算法程序：1、递归查找算法具体思想如下：（1）若二叉树为空，则查找失败。
（2）否则，将根结点的关键值与待查关键字进行比较，若相等，则查找成功；若根结点关键值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤；若在查找过程的中遇到二叉排序树的叶子结点时，还没有找到待查结点，则查找不成功。
if(t==NULL)return NULL;else{if(t->data==x)return t;if(x<t->data)return(Bsearch(t->lchild,x));elsereturn(Bsearch(t->rchild,x));}二叉排序树递归查找算法流程图2、非递归查找算法查找过程是从根结点开始逐层向下进行的。
并定义一个标记量记录是否找到结点。
Bstnode *searchBST(Bstnode *t,int x){B stnode *p;int flag=0;p=t;//定义*p结点用于逐层查找，丛根结点开始查找w hile(p!=NULL)//二叉排序树不为空{if(p->key==x)//查找成功{printf("该结点值存在!");flag=1;break;}//查找不成功，到下一层继续查找if(x<p->key)p=p->lchild;//查找左子树elsep=p->rchild;//查找右子树}i f(flag==0){printf("找不到值为%d的结点!",x);p=NULL;}r eturn p;}3、插入算法从根结点开始，根据比较规则，逐一与待插入结点的值比较，查找到插入结点在二叉排序树中的未来位置，然后插入该结点。
将一个关键字的值为x的结点s插入到二叉排序树中，方法如下：（1）若二叉排序树为空，则关键字值为x的结点s成为二叉排序树的根。
（2）若二叉排序树非空，则将x与二叉排序树的根进行比较，如果x的值等于根结点关键字的值，则停止插入；如果x的值小于根结点关键字的值，则将x插入左子树；如果x的值大于根结点关键字的值，则将x插入右子树。
在左右子树中插入方法与整个二叉排序树相同。
Bstnode *InsertBST(Bstnode *t,int x)// 插入关键值为x的元素{Bstnode *s,*p,*f;//*s为待插结点，*p 为逐层查找结点，*f为待插结点的父结点 p=t;while(p!=NULL){f=p;//查找过程中，f指向*p的父结点if(x==p->key)//若二叉树中已有关键值为x的元素，无需插入return t;if(x<p->key){p=p->lchild;}else{p=p->rchild;}}s=(Bstnode*)malloc(sizeof(Bstnode));s->key=x;s->lchild=NULL;s->rchild=NULL;if(t==NULL)//原树为空，新结点作为二叉排序树的根return s;if(x<f->key)f->lchild=s;//新结点作为*f左孩子 elsef->rchild=s;//新结点作为*f右孩子 return t;}4、二叉排序树的生成算法建立二叉排序树，就是反复在二叉排序树中插入新的结点。
插入的原则是如果待插入结点的值小于根结点的值，则插入到左子树中，否则插入到右子树中。
大致方法是：首先建一棵空二叉排序树，然后逐个读入元素，每读入一个元素，就建一个新结点，并调用上述二叉排序树的插入算法，将新结点插入到当前已生成的二叉排序树中，最终生成一棵二叉排序树。
Bstnode *CreateBST(){Bstnode *t;int key;t=NULL;//设置二叉排序树的初态为空scanf("%d",&key);while(key!=endflag){t=InsertBST(t,key);scanf("%d",&key);}return t;}5、中序遍历算法void Inorder(Bstnode *t){if(t!=NULL){Inorder(t->lchild);Printf(“%4d\n”,t->key);Inorder(t->rchild);}}先遍历左孩子，再遍历父结点，最后遍历右孩子。
由于是对一个二叉排序树进行中序遍历，遍历结果则是一个有序序列。
6、删除算法（1）待删除结点*p无左孩子，也无右孩子，则*p的父结点对应的孩子指针置空；（2）待删除结点*p有左孩子，无右孩子，则*p的左孩子替代自己；（3）待删除结点*p无左孩子，有右孩子，则*p的右孩子替代自己；（4）待删除结点*p有左孩子，也有右孩子，本课程（数据结构与算法）给出了两种法：方法一：首先找到待删结点*p的前驱结点*s，然后将*p的左子树改为*p父结点的左子树，而*p的右子树改为*s的右子树：f->lchild=p->lchild;s->rchild=p->rchild;free(p);方法二：首先找到待删结点*p的前驱结点*s，然后用结点*s的值替代结点*p的值，再将结点*s删除，结点*s的原左子树改为*s 的双亲结点*q的右子树：p->data=s->data;q->rchild=s->lchild;free(s);我采用的是第二种算法。
7、注意事项：其中，某些函数顺序一定不能颠倒。
例如建立二叉排序树函数一定是在插入算法之后。
编写完基本操作算法后，为最后主函数的输出模块作准备，又分别写了递归查找模块、插入模块、删除模块、显示模块。
四、上机调试1、语法错误及修改：在编写程序时，很容易出现分号漏写和括号不匹配的现象，以及缺少返回值的问题。
例如：在编写非递归查找算法时：Bstnode * searchBST (Bstnode *t,int x){Bstnode *p;int flag=0;p=t;while(p!=NULL){if(p->key==x){printf("找到了!");flag=1;return p;break;}if(x<p->key)p=p->lchild;elsep=p->rchild;}if(flag==0){printf("找不到值为%d的结点",x); return NULL;}}结果编译时出现了警告warning : ' searchBST ' : not all control paths return a value然后我做了改动，改后程序如下：Bstnode *searchBST(Bstnode *t,int x) {Bstnode *p;int flag=0;p=t;while(p!=NULL){if(p->key==x){ printf("该结点值存在!");flag=1;break;}if(x<p->key)p=p->lchild;elsep=p->rchild;}if(flag==0){ printf("找不到值为%d的结点!",x);p=NULL;}return p;}将NULL值赋给指针p，再在程序结尾返回p，此时，编译结果就正确了！2、程序输出调整：在递归查找算法(Bsearch)中针对查找结果如何,没有用明确的输出函数表示出来。
于是我添加了一个递归查找模块如下：search_Bitree(Bstnode *t){int s;Bstnode *p;printf("\n请输入要查找的结点的值:"); scanf("%d",&s);if(s!=0){ p=Bsearch(t,s);if(p==NULL)printf("该结点值不存在!\n");elseprintf("找不到值为%d的结点!\n",s);}}这样主函数便可直接调用该函数来实现查找过程。
