二叉排序树 建立_二叉排序树建立过程_c语言二叉排序树

《数据结构》实验报告

班级:姓名：学号:E-mail:日期:

◎实验题目: 建立二叉排序树，并中序遍历输出，输入一个关键字进行查找。 ◎实验目的：熟悉并掌握二叉排序树的建立及遍历输出以及非递归查找。

◎实验内容：输入一组数据，建立二叉排序树，并中序遍历输出，输入一个关键字进行查找。

一、需求分析

1、本程序中，输入一组数据，然后建立一棵二叉排序树存储这些元素，再中序遍历输出检验树建立是否正确，中序遍历输出的次序应为从小到大排列，然后输入一个关键字查找，输出查找成功与否。

2、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据。

3、程序所能达到的功能：建立二叉排序树，并中序遍历输出，输入一个关键字进行查找。

4、测试数据：

输入待排序的数据：10 15 20 5 10 30 9 7 13 45 2 -1（-1是输入结束标志） 中序遍历二叉树输出为：2 5 7 9 10 10 13 15 20 30 45

输入要查找的元素：7

输出：查找成功

二 概要设计

为了实现上述操作，应以二叉链表为存储结构，中序非递归遍历时以栈为中间存储结构。 该程序有四个函数分别为：主函数，插入函数，输出函数，查找函数。主函数通过调用其他三个函数实现上述功能。

三 详细设计

1、定义节点类型

typedef struct node

{

int data;

struct node *lc;

struct node *rc;

}BiTNode,*BiTree;

2、主函数

定义二叉排序树根节点bt，以及整形变量，x待插入数据变量，k查找关键字变量。二叉排序树 建立读取输入的数据存入x中，如果不是结束标志-1就调用插入函数将x插入到二叉排序树中，否则就执行后续操作。然后调用输出函数中序输出二叉排序树。二叉排序树 建立输出待查找的数据存入k中。调用查找函数进行查找。根据返回的指针判断查找成功与否。

3、插入函数

定义指向待插入节点指针q以及指向当前节点指针p，以及整形变量i用于判断插入成功与否。

q指向新申请节点，并将待插入数据存入数据项中。当树为空时，直接将节点插入到根节点。否则待插入节点与根节点进行比较：如果小于根节点，沿左孩子链进行比较，否则沿右孩子链进行比较。直到终端插入该节点。

4、中序遍历函数

当前结点等于根结点.

初始化栈。

当栈不空或者当前结点不空时while循环：

当p不空时进栈，然后沿左孩子路径访问，直至p为空；

此时让p等于栈顶指针，输出p的数据域的值；

当输出了父结点后沿右孩子路径访问。

5、查找函数

定义指向当前节点指针p，并使p指向根节点。当p不空且还未查找到关键字与根节点进行比较。若大于根节点沿右孩子链查找，否则沿左孩子链进行查找。返回指针p。

四 使用说明、测试分析及结果

1、测试结果

输入待排序的数据：10 15 20 5 10 30 9 7 13 45 2 -1（-1是输入结束标志） 中序遍历二叉树输出为：2 5 7 9 10 10 13 15 20 30 45

输入要查找的元素：7

输出：查找成功

符合预期设想

3．运行界面

五、实验总结

在进行这次试验前，我首先写了实验预习报告，用了大概半小时时间写出了解决此问题的大体算法，并且用了半小时时间把具体的设计写了出来，要用了一个小时进行了调试。在进行测试的时候，发现查找的元素不在二叉树中出来的结果是查找成功，最后检查发现时判断条件的时候把等于打成了赋值。做了这么多实验我的细心程度还是达不到期望值。这是我以后实验中特别要注意的地方。 教师评语：

实验成绩：

指导教师签名：

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25005-1.html