武汉理工大学数据结构课程设计二叉排序树的判别

课 程 设 计

题 目 学 院

二叉排序树的判别

计算机科学与技术

专 业 物联网工程 班 级 姓 名 指导教师

物联网1101班

刘春

2013 年 7 月 2 日

课程设计任务书

学生姓名： 专业班级： 物联网1101班 指导教师： 刘春 工作单位：计算机科学与技术学院 题 目:二叉排序树的判别 初始条件：

试写一个判别给定二叉树是否为二叉排序树的程序。 （1） 此二叉树以二叉链表作存储结构； （2） 树中结点的关键字均不同。 （3） 正、反测试用例自己设计；

要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写

等具体要求）

课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容： 1、 问题描述

简述题目要解决的问题是什么。 2、 设计

存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计； 3、 调试报告

调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。 4、 经验和体会（包括对算法改进的设想）

5、 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，

6、 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。

时间安排：

1、第20周（6月29日至7月3日）完成。

2、7月3 日8：00到计算中心检查程序、交课程设计报告、源程序（CD盘）。

指导教师签名： 年 月 日

系主任（或责任教师）签名： 年 月 日

二叉排序树的判别

一．问题描述

1.输入一个给定的二叉树，并判断其是否为二叉排序树。 2.对给定的二叉树用链式存储结构实现。 3.输入的关键字应不同。

二．设计与主要函数的实现

注：因此程序以0代表空树的输入，故关键字输入时不能有0。

1.首先应对输入的二叉树进行存储，先对其节点进行创建，一个节点中应有一个数据，一个左孩子指针以及一个右孩子指针。 主要实现为： struct BitNode{ int data;

BitNode *lchild,*rchild; };

2.用先序遍历的递归方式创建二叉树，对数据进行逐个输入，当子树为空时输入0。

主要实现函数为：

void CreatBiTree(BitNode *&T) //二叉树的创建，按先序遍历逐个输入二叉树节点的数字，取0为空节点 {

int c;

cin>>c; //该节点的值 if(c==0) { T=NULL; } else{ T=new BitNode; T->data=c; CreatBiTree(T->lchild); CreatBiTree(T->rchild); } }

3.判断二叉树是否为二叉排序树。

二叉排序树的定义为：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树；

首先对该二叉树进行中序遍历，再通过判断其是否递增即可知是否为二叉排序树。

中序遍历的非递归算法,并将中序遍历后的数据存于指针数组w中，该指针数组原来均存储的为0。 主要函数实现：

void InOrderTraverse(BitNode *T,int *&w,SqStack &S) //非递归的中序遍历 {

InitStack(S); int e;

BitNode *p=T; int *q=w;

while(p||!StackEmpty(S)) {

if(p) {

Push(S,*p); p=p->lchild; } else {

p=Pop(S); e=(*p).data; *q=e; q++;

cout<<e<<" "; p=(*p).rchild; } }

cout<<" "<<endl; p=NULL; }

对中序遍历后的数据进行判断，判断其是否递增。 bool IfInc(int *&w) {

int *p=NULL; int *q=NULL; p=w; q=p; q++;

while(*q!=0)

}

{

if(*p>*q) {

return 0; } else {

p++; q++; } }

p=NULL; q=NULL; return 1;

三．调试

调试一向是编程中比较繁杂环节，由于编程水平还有限，我的程序中常出现不少错误。在设计中，我使用的是Visual C++ 6.0为平台。建立好CPP文件后，对代码进行编译，出现了诸多问题。比如说，引用使用错误，模板定义有误，参数前后不一致，函数无法跳出循环等错误，也存在会在语句后面丢掉分号、输入的标点符号不是英语输入中的而是中文输入中等小问题。对待这些错误需要相当大的耐性，在细心的检查后一一更正了。在编译没有错误之后开始组建。在组建出现了内存泄露，这是在编程中经常出现的问题。

出错部分：

void InOrderTraverse(BitNode *T,int *&w,SqStack *&S) {

InitStack(S); int e;

BitNode *p=NULL; int *q=NULL; p=T; q=w;

while(p||!StackEmpty(S)) {

if(p) {

Push(S,p->data); p=p->lchild; } else {

e=Pop(S);*q++=e;

p=p->rchild; //出错位置！ } }

p=NULL; q=NULL; }

上面标出的出错位置中，因p原来就已是空指针，其根本没有右孩子。所以会出现内存出错的提示。如图：

通过调整后对Pop()的返回值进行了变化，返回的为结点地址。 修改后主要函数如下：

void InOrderTraverse(BitNode *T,int *&w,SqStack &S) //非递归的中序遍历 {

InitStack(S); int e;

BitNode *p=T; int *q=w;

while(p||!StackEmpty(S)) {

if(p) {

Push(S,*p); p=p->lchild; } else {

p=Pop(S); e=(*p).data; *q=e; q++;

cout<<e<<" "; p=(*p).rchild; } }

cout<<" "<<endl; p=NULL; }

四．经验和体会

在这次课程设计中，通过对课堂知识的复习，加深了我对二叉树建立，遍历，二叉排序树判定等知识的掌握。同时对程序设计和调试也更熟练，对于程序设计也有了更好的理解。另外我深知程序设计不光只是要得到相应的运行结果就可以的，还有考虑它的健壮性，以及与用户之间的交流，要能够直观的，简洁的表示该程序的使用方法和功能，而且还要有很好的重复使用性，这样的算法才是好的算法。

我也意识到在很多方面存在不足，需要更加努力，在反复实践的过程中不断提高自己的编程能力。

对自定义类型进行传参时，应特别注意是否需要进行引用。在含有结点时应注意其是否为空，若为空，则不能对其值进行赋值，而应对其地址赋值！

五．运行结果截图

是二叉排序树的结果：

不是二叉排序树的结果：

六．参考文献

【1】《数据结构（C++语言版）第二版》，殷人昆，编著，出版社：清华大学出版，社出版时间：2008年11月 【2】《c++程序设计教程》，闵联营，何克右，编著，出版社：武汉理工大学出版社，出版时间：2005年7月 【3】《数据结构习题集(C语言版)》，严蔚敏，吴伟民，米宁编著，清华大学出版社，出版或修订时间：1999年2月

本科生课程设计成绩评定表

班级： 姓名： 学号：

及格（60-69分）、60分以下为不及格

指导教师签名：

201 年 月 日