二叉排序树判定
- 格式：docx
- 大小：142.85 KB
- 文档页数：7
二叉排序树的判别
一．问题描述
1.输入一个给定的二叉树，并判断其是否为二叉排序树。
2.对给定的二叉树用链式存储结构实现。
3.输入的关键字应不同。
二．设计与主要函数的实现
注：因此程序以0代表空树的输入，故关键字输入时不能有0。
首先应对输入的二叉树进行存储，先对其节点进行创建，一个节点中应有一个数据，
一个左孩子指针以及一个右孩子指针。
主要实现为：structBitNode{ 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<
boolIfInc(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<
cout<<" "<
在这次课程设计中，通过对课堂知识的复习，加深了我对二叉树建立，遍历，二叉排序树判
定等知识的掌握。同时对程序设计和调试也更熟练，对于程序设计也有了更好的理解。另外
我深知程序设计不光只是要得到相应的运行结果就可以的，还有考虑它的健壮性，以及与用
户之间的交流，要能够直观的，简洁的表示该程序的使用方法和功能，而且还要有很好的重
复使用性，这样的算法才是好的算法。我也意识到在很多方面存在不足，需要更加努力，在
反复实践的过程中不断提高自己的编程能力。对自定义类型进行传参时，应特别注意是否需
要进行引用。在含有结点时应注意其是否为空，若为空，则不能对其值进行赋值，而应对其
地址赋值！
五．运行结果截图
是二叉排序树的结果：
不是二叉排序树的结果：
六．参考文献
一、问题分析和任务定义
题目：二叉排序树运算
任务定义：对一组数据构造二叉排序树，并在二叉排序树中实现多种方式的查找。
基本任务：
（1）选择合适的存储结构构造二叉排序树；
（2）对二叉排序树T作中序遍历，输出结果；
（3）在二叉排序树中实现多种方式的查找，并给出二叉排序树中插入和删除的操作。
（4）尽量给出“顺序和链式”两种不同结构下的操作，并比较。若要完成题目的要求，需
要解决以下几个问题：
1、选择一种数据结构存储二叉树的信息。
2、建立一个新的二叉排序树
3、在二叉排序树中插入，删除，查找相关节点
二、数据结构的选择和概要设计
1、数据结构的选择：
题目要求选择合适的存储结构构造二叉排序树，选择链式结构存储。用链表的方式构造节点，
存储二叉排序树中的节点！节点类型和指针类型如下！
typedefstruct node {
int key;
int other
struct node *lchild,*rchild;
}Bstnode;
2、概要设计：
为了完成所需的功能，需要的函数及其功能如下：
main()：主函数模块
Bsearch()：查找相应的节点
InsertBST ()：插入一个新节点
CreateBST ()：创建一棵二叉排序树
Inorder ()：对二叉排序树进行中序遍历
menu()：主函数显示菜单模块
DeleteBST ()：删除节点
主函数流程图：
图（a）主函数流程图
