数据结构 创建二叉排序树与查找.doc

《数据结构》实验报告
◎实验题目:创建二叉排序树与查找
◎实验目的：1、掌握使用Visual C++6.0上机调试程序的基本方法；
2、 掌握二叉排序树的创建和二叉排序树查找的方法。
3、 提高自己分析问题和解决问题的能力，在实践中理解教材上的理论。
◎实验内容：建立至少10个顶点的二叉排序树，然后对其进行中序遍历，接着进行查找， 判断待查找数据是否存在。
一、需求分析
1、输入的形式和输入值的范围：根据提示，首先输入顶点中的数据，在进行查找操作时，输入待查找的数据，接着选择下一步要进行的操作(A.新二叉排序树;B.继续查找;C.结束操作)。
2、输出的形式：输出二叉排序的中序遍历结果，在输入待查找的数据后，输出查找的结果。
3、程序所能达到的功能：输入顶点数据后，创建二叉排序树，接着进行中序遍历，再输入待查找数据进行查找操作。
4、测试数据：
请输入顶点数据:53 25 76 20 48 14 60 84 33 78
中序遍历结果为:14 20 25 33 48 53 60 76 78 84
输入待查找数据:33
待查找数据存在
选择操作(A.新二叉排序树;B.继续查找;C.结束操作):B
输入待查找数据:54
待查找数据不存在
选择操作(A.新二叉排序树;B.继续查找;C.结束操作):C
谢谢使用!
Press any key to continue
二 概要设计
1、 二叉排序树又称二叉查找树，对一个二叉树若规定：任一结点如果有左子树，其左子树各结点的数据必须小于该结点的数据；任一结点如果有右子树，其右子树各结点的数据必须大于该结点的数据。按这样规定构成的二叉树称为二叉排序树。对二叉排序树进行中序遍历所得到的结点序列是一个有序序列。
2、 创建二叉排序树的非递归算法执行的步骤如下：
①生成一个新结点；
②与根结点进行比较，如果小于根结点，沿左链域比较，如果大于根结点，沿右链域比较；
③直至到终端，插入该结点。
以序列53，25，76，20，48，14，60，84，33，78为例，所创建的二叉排序树如图所示。
3、 二叉排序树查找
二叉排序树查找的基本思路：查找过程从根结点开始，首先将它的关键字与给定值k进行比较，，如果相等，则查找成功，输出有关的信息；如果不等，若根结点关键字大于给定值k，向左子树继续查找，否则向右子树继续查找。向子树查找又是树状查找，先以子树的根结点数据与k进行比较，如果不相等又转向它的左子树或右子树继续查找。

4、本程序的基本操作和模块：
建立二叉排序树的函数：Create(BiTNode *B)
二叉树的中序遍历函数：Inorder(BiTNode *B,SeqStack &K)
查找函数：Search(BiTNode *B,int key)
主函数：main( )
函数的调用关系如下图所示:

三 详细设计
（一） 元素类型、结点类型
1、 二叉树结点的类型描述
typedef struct node
{
char data; //data用于存储二叉树中的字母
struct node *lchild; //lchild为指向该结点左孩子的指针
struct node *rchild; //rchild为指向该结点下一层的指针
}BiTNode;
2、顺序栈的类型描述
typedef struct
{
BiTNode *pin[40]; //指针数组，用于存储广义表结点指针
int top; //栈顶指针
}SeqStack;
（二） 每个模块的分析
1、 主程序模块
main()
{
①定义根结点指针
②定义栈并初始化栈
③申请根结点空间，令根结点B的lchild域和rchild域为空
④调用创建二叉排序树函数
⑤调用中序遍历二叉树函数
⑥调用查找函数进行查找
}
2、 建立二叉排序树的函数
void Create(BiTNode *B)
{
①定义指向当前结点的指针p，新结点的指针q，初始时p为空
②输入不是回车时执行以下操作
{
输入结点数据
◎若该数据是第一个数据
{
第一个数据存到根节点，p指针指向根结点
}
◎若该数据不是第一个数据
{
①申请新结点q，将该数据存入q的data域
令新结点q的lchild域和rchild域为空
②p指向根结点
③当p指针所指结点和q指针所指结点中的数据不同时执行以下操作
{
◎如果p结点数据小于新结点q中的数据,执行以下操作
{
如果p的右孩子为空，令p的右孩子为q
将p的右孩子赋p
}
◎如果p结点数据大于新结点q中的数据,执行以下操作
{
如果p的左孩子为空，令p的左孩子为q
将p的左孩子赋p
}
}
}
}
}
3、 查找函数
void Search(BiTNode *B,int key)
{
①定义指向当前结点的指针p，初始时p指向根结点
②当p不为空且p所指结点的数据不为待查找数据时，执行以下操作
{
如果当前结点中的数据小于待查找数据，则令p指向它的右孩子
如果当前结点中的数据大于待查找数据，则令p指向它的左孩子
}
循环结束后，若p为空则待查找数据不存在;否则待查找数据存在
}

4、 中序遍历二叉树树的函数
void Display(GLNode *G,SeqStack &K)
{
①定义表示当前结点的指针p，并令p指根结点。
②当栈不为空或当前结点指针p不为空时，执行以下操作
while(K.top!=-1||p!=NULL)
{
a. 如果当前结点指针p为空，执行以下操作：
出栈，栈顶元素所指的结点作为当前结点p
输出当前结点p中的数据
令当前结点p的rchild域所指的结点作为当前结点p
b. 如果当前结点指针p不为空，执行以下操作：
当前结点指针p入栈
令当前结点p的rchild域所指的结点作为当前结点p
}
}

四 使用说明、测试分析及结果
1、 程序使用说明：
（1） 本程序运行环境为Visual C++ 6.0；
（2） 根据界面提示进行操作：输入多个数据时以空格分隔，每次输入按回车表示输入结束
2、 测试结果与分析：
请输入顶点数据:53 25 76 20 48 14 60 84 33 78
中序遍历结果为:14 20 25 33 48 53 60 76 78 84
输入待查找数据:33
待查找数据存在
选择操作(A.新二叉排序树;B.继续查找;C.结束操作):B
输入待查找数据:54
待查找数据不存在
选择操作(A.新二叉排序树;B.继续查找;C.结束操作):C
谢谢使用!
Press any key to continue
由上测试结果分析得，该程序功能满足题目要求。
3、 调试过程中遇到的问题及解决方法
本次实验的错误的主要发生在二叉排序树查找，对进行循环操作的条件判断不够完整，输出数据的条件判断不正确，使运行中出现错误。原因是在p为空时，仍判断p中数据是否与待查找数据相等。
另外，本次实验中的其它小错误都很快修改正确。
4、 运行界面

五、实验总结
本次实验提前作了预习，老师在课堂上有详细的讲解，所以此次实验比较顺利，我在11月23日完成了本次实验。
本次实验，我很感谢老师和同学对我的指点。通过本次实验，对二叉排序树有了更深的认识，学会了如何利用二叉排序树查找数据，对一些细节更加理解，收获了很多。
教师评语：

实验成绩：
指导教师签名：
批阅日期：
代码：
# include<stdio.h>
# include<stdlib.h>
//——————————————————————————————————————————
typedef struct node //二叉树结点的类型描述
{
char data; //data用于存储二叉树中的字母
struct node *lchild; //lchild为指向该结点左孩子的指针
struct node *rchild; //rchild为指向该结点下一层的指针
}BiTNode;
//——————————————————————————————————————————
typedef struct //顺序栈的类型描述
{
BiTNode *pin[40]; //指针数组，用于存储广义表结点指针
int top; //栈顶指针
}SeqStack;
//——————————————————————————————————————————
void Create(BiTNode *B) //建立二叉排序树的函数
{
int m;
char r;
BiTNode *p,*q; //定义指向当前结点的指针p,新结点的指针q
p=NULL; //初始时p为空
printf("请输入顶点数据:");
while(r!='\n') //输入回车表示循环结束
{
scanf("%d%c",&m,&r); //输入结点数据
if(p==NULL) //第一个数据置到根节点，p指针指向根结点
{
B->data=m;
p=B;
}
else //对于其它数据执行以下操作
{
q=(BiTNode *)malloc(sizeof(BiTNode)); //申请新结点q
q->data=m; //令该数据存入当前结点的data域
q->lchild=NULL;q->rchild=NULL; //令新结点q的lchild域和rchild域为空
p=B;
while(p->data!=q->data) //当p指针所指结点和q指针所指结点中的数据不同时执行以下操作
{
if(p->data<q->data) //如果p结点数据小于新结点q中的数据,执行以下操作
{
if(p->rchild==NULL) //如果p的右孩子为空，令p的右孩子为q
p->rchild=q;
p=p->rchild; //将p的右孩子赋p
}
else //如果p结点数据大于新结点q中的数据,执行以下操作
{
if(p->lchild==NULL) //如果p的左孩子为空，令p的左孩子为q
p->lchild=q;
p=p->lchild; //将p的左孩子赋p
}
}
}
}
}

//——————————————————————————————————————————
void Search(BiTNode *B,int key) //查找函数
{
BiTNode *p; //定义指向当前结点的指针p
p=B; //初始时p指向根结点
while(p!=NULL&&p->data!=key) //当p不为空且p所指结点的数据不为待查找数据时，执行以下操作
{
if(p->data<key) //如果当前结点中的数据小于待查找数据，则令p指向它的右孩子
p=p->rchild;
else //如果当前结点中的数据大于待查找数据，则令p指向它的左孩子
p=p->lchild;
}
if(p==NULL) printf("待查找数据不存在\n",key);//循环结束后，若p为空则待查找数据不存在;否则待查找数据存在
else printf("待查找数据存在\n",key);
printf("\n");
}
//——————————————————————————————————————————
void Inorder(BiTNode *B,SeqStack &K) //二叉树的中序遍历函数
{
printf("中序遍历结果为:"); //提示以下结果为中序遍历结果
BiTNode *p; //p指针指向当前结点
p=B; //当前结点为根结点
while(K.top!=-1||p!=NULL) //当栈不为空或当前结点指针p不为空时，执行以下操作
{
if(p==NULL) //如果当前结点指针p为空，执行以下操作
{
p=K.pin[K.top]; //出栈，栈顶元素所指的结点作为当前结点p
K.top--;
printf("%d ",p->data); //输出当前结点p中的数据
p=p->rchild; //令当前结点p的rchild域所指的结点作为当前结点p
}
else //如果当前结点指针p不为空，执行以下操作
{
K.top++; //当前结点指针p入栈
K.pin[K.top]=p;
p=p->lchild; //令当前结点p的rchild域所指的结点作为当前结点p
}
}
printf("\n");
}
//——————————————————————————————————————————
int main()
{
int key;
char a='A',b='B',c;
BiTNode *B; //定义根结点指针
SeqStack K; //定义栈并初始化栈
K.top=-1;
while(a=='A') //A表示创建新的二叉排序树
{
B=(BiTNode *)malloc(sizeof(BiTNode)); //申请根结点
B->rchild=NULL;B->lchild=NULL; //令根结点B的lchild域和rchild域为空
Create(B); //创建二叉排序树
Inorder(B,K); //中序遍历二叉树中的数据
while(b=='B') //B表示查找数据操作
{
printf("输入待查找数据:");
scanf("%d",&key); //输入待查找数据
getchar();
Search(B,key); //进行查找
printf("选择操作(A.新二叉排序树;B.继续查找;C.结束操作):");
scanf("%c",&c); //根据提示，选择下一步操作
printf("\n");
b=c;
}
a=c;
b='B';
}
printf("谢谢使用!\n");
return 0;
}
/**
请输入顶点数据:53 25 76 20 48 14 60 84 33 78
中序遍历结果为:14 20 25 33 48 53 60 76 78 84
输入待查找数据:33
待查找数据存在

选择操作(A.新二叉排序树;B.继续查找;C.结束操作):B

输入待查找数据:54
待查找数据不存在

选择操作(A.新二叉排序树;B.继续查找;C.结束操作):C

谢谢使用!
Press any key to continue
*/