数据结构报告5

天津理工大学

计算机与通信工程学院

实验报告

2014 至 2015 学年 第 二 学期

课程名称 学号 专业 实验时间 主讲教师 实验（五） 20125657 计科 学生姓名 数据结构 王成 年级 实验地点 2012 7-220 教学班号 2 2015 年 5 月 24 日 2015 年 5 月 31 日 董玉涛 实验名称 二叉排序树 计算机科学与工程系

软件环境 Windows98/2000, VC++6.0或turbo C 硬件环境 PⅡ以上微型计算机 实验目的 理解二叉排序树的概念，掌握实现算法。 实验内容（应包括实验题目、实验要求、实验任务等） 二叉排序树 设计一个程序，对从键盘输入的一组整数，建立起一棵二叉排序树，并对其进行中序遍历，验证是否是递增有序序列。 2

计算机科学与工程系

实验过程与实验结果（可包括实验实施的步骤、算法描述、流程、结论等） 实验步骤及算法描述和流程： 1. 创建二叉链表的结点存储结构 结点中的数据为整型 2. 创建二叉排序树 2.1 对输入的数据进行大小的判断 若根节点为空，输入的数据直接赋给根节点，否则，需要将输入的数据与根节点比较，小于根节点则作为根节点的左子树，大于根节点则作为根节点的右子树，利用递归调用，将数据输入到整个二叉排序树。 2.2 建立二叉排序树 输入数据，调用2.1 创建的函数，建立二叉排序树 3. 中序遍历二叉排序树并判断是否有序 当根节点不为空时 3.1 递归调用遍历根节点的左子树 3.2 输出根节点 3.3 判断输出序列是否为有序序列 初始化整型变量t，初值为根节点的值，如果根节点的值小于t，则不是有序序列 3.4 递归调用遍历根节点的右子树 4. 主函数 4.1 输入数组长度n 4.2 调用生成二叉排序树的函数，输入n个整数，建立二叉排序树 4.3 调用函数以中序遍历输出二叉排序树并判断是否为有序序列 结论： 输入10个整数：56,48,12,30,69,47,49,21,36,49 输出 12,21,30,36,47,48,49,56,69 序列是递增有序序列 程序设计中相同的数据仅记录一遍 问题： 如果序列不是递增有序序列，那么将会输出多个“不”字 3

计算机科学与工程系

附录（可包括源程序清单或其它说明）

#include #include using namespace std;

typedef struct BiTNode{ //二叉链表节点存储结构 int data;

struct BiTNode *lchild;

struct BiTNode *rchild; //左右孩子指针 }BiTNode,*BiTree;

void insert(BiTree &T,int k){ //二叉排序树的递归算法 if(T==NULL){ T=(BiTree)malloc(sizeof(BiTNode)); T->data=k; T->lchild=T->rchild=NULL; }

else if(kdata) insert(T->lchild,k); else if(k>T->data) insert(T->rchild,k); }

void createBST(BiTree &T,int n){ //二叉排序树的建立 T=NULL; int k;

for(int i=1;i<=n;i++){ cin>>k; //输入关键字 insert(T,k); } }

void InOrder(BiTree root){ //中序遍历二叉树排序树 if(root==NULL) return; int t=root->data,k=1; InOrder(root->lchild); cout<data<<\" \";

if(root->dataInOrder(root->rchild); }

void main(){ BiTree T; int n;

cout<<\"请输入一组整数的长度n=\"; cin>>n;

cout<<\"请输入\"<cout<<\"是递增有序序列！\"<4

计算机科学与工程系

}

运行结果：

5