二叉排序树的建立与输出.doc

数据结构实验报告班级: 姓名： 学号: 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运行界面五、实验总结 在进行这次试验前，我首先写了实验预习报告，用了大概半小时时间写出了解决此问题的大体算法，并且用了半小时时间把具体的设计写了出来，要用了一个小时进行了调试。在进行测试的时候，发现查找的元素不在二叉树中出来的结果是查找成功，最后检查发现时判断条件的