建立二叉排序树,并中序遍历输出,输入一个关键字进行查找
《数据结构》实验报告
班级: 姓名: 学号: 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、中序遍历函数
当前结点等于根结点.
建树 ① 依次输入 n 个关键字 ② 插入二叉排序树中 ③ 中序输出创建过程 删除任意结点 插入一个结点 查找关键字 中序输出操作后二叉排序树 是否继续 否 结束...
对排序二叉树的建立需知道其定义及其通过插入结点 来建立排序二叉树,遍历及其输出结果。 该设计根据输入的数据进行建立排序二叉树。对排序二叉树的遍历,其关键是运用...
关键词:二叉排序树的创建;中序遍历输出;插入结点;查找结点;删除结点 目录 1 引言...1 1.1 课程设计的目的......
二叉排序树的建立及查找运算的实现_天文/地理_自然科学_专业资料。试验七课程...",z); else printf("该二叉排序树中不存在此节点!"); } 在屏幕上输出的...
2、输出的形式:输出二叉排序的中序遍历结果,在输入待查找的数据后,输出查找的结果。 3、程序所能达到的功能:输入顶点数据后,创建二叉排序树,接着进行中序遍历,...
二、实验内容和要求 [问题要求] 从键盘读入一组数据,建立二叉排序树并对其进行查找、插入、遍历、打印输出操作。 测试数据元素关键词序列. [问题分析] 建立二叉...
二叉排序树的建立_IT/计算机_专业资料。最优二分树(最优二叉搜索树) 45 12 53 37 24 ? 二叉搜索树 3 100 1. 若它的左子树不空,则左子树上所有 若它...
设计报告 设计题目<一>:一、设计要求 1.问题描述 6.4.1 二叉排序树基本操作的实现 从键盘读入一组数据,建立二叉排序树并对其进行查找、插入、遍历、打印输出...
建树 ① 依次输入 n 个关键字 ② 插入二叉排序树中 ③ 中序输出创建过程 删除任意结点 插入一个结点 查找关键字 中序输出操作后二叉排序树 是否继续 否 结束...
("请输入二叉排序树的各节点元素(请以-1为结束标志):\n"); create(t);//创建二叉排序树 printf("建立的二叉排序树按非递归中序遍历输出为:\n"); in...
热门文档