二叉排序树的构建与输出

《数据结构》实验报告 班级:姓名：学号: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-144348-1.html