数据结构实验报告5

计算机科学与工程系PAGEPAGE2计算机科学与工程系实验（五）实验名称二叉排序树软件环境Windows98/2000,VC++6.0或turboC硬件环境PⅡ以上微型计算机实验目的理解二叉排序树的概念，掌握实现算法。实验内容（应包括实验题目、实验要求、实验任务等）二叉排序树设计一个程序，对从键盘输入的一组整数，建立起一棵二叉排序树，并对其进行中序遍历，验证是否是递增有序序列。实验过程与实验结果（可包括实验实施的步骤、算法描述、流程、结论等）实验步骤及算法描述和流程：创建二叉链表的结点存储结构结点中的数据为整型创建二叉排序树对输入的数据进行大小的判断若根节点为空，输入的数据直接赋给根节点，否则，需要将输入的数据与根节点比较，小于根节点则作为根节点的左子树，大于根节点则作为根节点的右子树，利用递归调用，将数据输入到整个二叉排序树。建立二叉排序树输入数据，调用2.1创建的函数，建立二叉排序树中序遍历二叉排序树并判断是否有序当根节点不为空时递归调用遍历根节点的左子树输出根节点判断输出序列是否为有序序列初始化整型变量t，初值为根节点的值，如果根节点的值小于t，则不是有序序列3.4递归调用遍历根节点的右子树主函数输入数组长度n调用生成二叉排序树的函数，输入n个整数，建立二叉排序树调用函数以中序遍历输出二叉排序树并判断是否为有序序列结论：输入10个整数：56,48,12,30,69,47,49,21,36,49输出12,21,30,36,47,48,49,56,69序列是递增有序序列程序设计中相同的数据仅记录一遍问题：如果序列不是递增有序序列，那么将会输出多个“不”字附录（可包括源程序清单或其它说明）#include<iostream>#include<stdio.h>usingnamespacestd;typedefstructBiTNode{//二叉链表节点存储结构 intdata; structBiTNode*lchild; structBiTNode*rchild;//左右孩子指针}BiTNode,*BiTree;voidinsert(BiTree&T,intk){//二叉排序树的递归算法 if(T==NULL){ T=(BiTree)malloc(sizeof(BiTNode)); T->data=k; T->lchild=T->rchild=NULL; } elseif(k<T->data)insert(T->lchild,k); elseif(k>T->data)insert(T->rchild,k);}voidcreateBST(BiTree&T,intn){//二叉排序树的建立 T=NULL; intk; for(inti=1;i<=n;i++){ cin>>k;//输入关键字 insert(T,k); }}voidInOrder(BiTreeroot){//中序遍历二叉树排序树 if(root==NULL)return; intt=root->data,k=1; InOrder(root->lchild); cout<<root->data<<""; if(root->data<t)//判断是否为有序序列 cout<<"不"; InOrder(root->rchild);}voidmain(){ BiTreeT; intn; cout<<"请输入一组整数的长度n="; cin>>n; cout<<"