数据结构课程设计判别给定的二叉树是否为二叉排序树

1、课程设计任务书学 院专 业学 生 姓 名学 号题 目判别给定的二叉树是否为二叉排序树内容及要求：设计内容：判别给定的二叉树是否为二叉排序树，设此二叉树以二叉链表存储，且树中结点的关键字均不相同。为实现上述功能，需要解决的关键问题是：建立一棵二叉树及判定二叉树过程。要求：1.设计数据结构：建立的是二叉树，所以逻辑结构为树形结构。定义存储结构为链式存储结构，用typedef定义结点的结构体。2.在Turboc或兼容环境完成上述题目的代码编写与调试；3.程序运行界面交互性好；输入输出数据时，应该有相应的提示。4.给出两组测试数据，可以按路径覆盖的方法给出两组主要的测试数据。任务交付：1. 课程设计论

2、文，包括需求分析、概要设计、详细设计、调试分析、课程总结、参考文献等部分。2. 课程设计论电子文档及程序源代码。进度安排：本课程设计时间为17、18教学周。其中包含设计、代码调试、课程设计论文撰写、验收与答辩几个阶段。第1周 查找资料、完成初步设计、代码设计与初步调试；第2周 调试、测试、验收、课程设计论文撰写、答辩。指导教师（签字）：2011年 12月16日学院院长（签字）： 2011年12月16日目录1 需求分析32 概要设计42.1存储结构设计说明42.2程序功能图42.3算法流程图53 详细设计73.1程序分析73.2程序源代码74 调试分析95 课程总结116参考文献121 需求分析

3、7780905068883456 图1-1 二叉树以图1-1所示的二叉树为例设计，建立一个以二叉链表方式存储的二叉树，输入结点信息时按照完全二叉树的结点顺序输入（1为虚结点，0为输入结束）。由于一棵二叉排序树中序遍历后的序列是递增有序的，因此可利用中序遍历一棵二叉树后的序列是否递增有序来判断是否为二叉排序树。 如图，二叉树的结点输入顺序为77 80 90 50 1 68 88 1 1 34 56 0 （1为虚结点，0为输入结束），中序遍历之后的顺序为50 80 77 34 68 56 90 88 ，由于中序遍历之后的序列不是递增有序的，因此可判断出此二叉树不是二叉排序树。2 概要设计2.1 存

4、储结构设计说明 typedef struct nodeint data; /数据域node *lchild,*rchild; /左孩子指针，右孩子指针Bitree; /结点的结构体定义 2.2程序功能图建立二叉树（按照完全二叉树的结点顺序输入）中序遍历二叉树，并将结点保存在数组中比较数组元素，看是否有序递增判断是否为二叉排序树 图2-1 程序功能图2.3算法流程图选取部分核心流程图如下：开始初始化二叉树Bitree *Creatree()Inorder(Bitree *T)Judgeout(Judgesort_bitree(Btree)判断是否为二叉树是二叉排序树不是二叉排序树序树结束YN结束

5、图2-2 主要流程图开始sign=0,front=0,rear=-1,T=NULLch!=0?ch!=1?rear+sign%2=0?front+sign+YYNYNBrear=Srear=front创建结点SYNsign%2=1?T=Ssign+NYBfrontlchild=SBfrontrchild=Sfront+sign+N结束图2-3 建立二叉树3 详细设计3.1程序分析建立一个以二叉链表方式存储的二叉树，建立二叉树时，按照完全二叉树的结点顺序输入，1表示虚结点，0表示输入结束。若不是虚结点时，则建立一个新结点，并且将其作为左孩子或右孩子结点连接到它的父结点上（第一个结点无父结点）；若

6、是虚结点，则将空结点（NULL）作为左孩子或右孩子结点连接到它的父节点上。判定二叉树时，中序遍历整棵二叉树，访问根结点时将根结点信息存入一个数组中，以用来比较中序遍历后序列是否为空。比较数组元素时，从下标为0的数组元素开始比较，先将下标为i=0的ai与下标为1的ai+1比较，如果ai>ai+1，则结束比较，即该二叉树不是二叉排序树，否则继续比较，直至比较完整个数组元素。3.2程序源代码#include "stdafx.h" /编写的任何.cpp文件都必须首先包含stdafx.h#include<stdio.h>#include<stdlib.h>

7、;#define max 10typedef struct nodeint data; /数据域node *lchild,*rchild; /左孩子指针，右孩子指针Bitree; /结点的结构体定义Bitree *Bmax;int temp=0;int Btreemax;Bitree *Creatree() /建立二叉树Bitree *T,*S;int ch;int front,rear,sign;sign=0; /结点的序号从0开始编号（按照完全二叉树的顺序标记）front=0; /双亲结点下标初值rear=-1; /自身结点下标初值T=NULL; /初始化树Tprintf("建立

8、二叉树(1表示虚结点,0表示输入结束):n");scanf("%d",&ch); /按完全二叉树的顺序输入结点while(ch!=0) if(ch!=1) /输入结点不是虚结点 S=(Bitree *)malloc(sizeof(Bitree); /创建新结点SS->data=ch; /将输入的数据保存到S中S->lchild=S->rchild=NULL; /将S的左右子树为空rear+; /结点下标加1Brear=S; /将S保存到数组B中，即从下标为0开始存储if(rear=front) /双亲结点下标与本身下标相同时，即无双亲结点

9、（只有第一个结点会产生这种情况） T=S;sign+; /结点的序号加1 else /寻找双亲结点 if(sign%2=1) Bfront->lchild=S; /S作为左孩子 if(sign%2=0) Bfront->rchild=S;/S作为右孩子front+;/下标加1，即寻找下一个双亲结点 sign+;/结点序号加1 else /输入结点为虚结点if(sign%2=0) /为右子树时front+; /双亲结点加1 即下一个双亲结点sign+; /结点序号加1 scanf("%d",&ch);return T;void Inorder(Bitree

10、 *T) /中序遍历二叉树T，并将每个结点数据存入数组中 if(T!=NULL) /如果树不为空 Inorder(T->lchild);printf("%dt",T->data);Btreetemp=T->data;temp+;Inorder(T->rchild);int Judgesort_bitree(int Btree) /判断中序遍历后的二叉树是否是二叉排序树 int i,sign=1;for(i=0;i<temp-1;i+) /用for循环语句 看二叉树是否有序递增 if(Btreei>Btreei+1) /不是有序递增的 si

11、gn=0;break;return sign; void Judgeout(int a)/判断输出 将sign赋给a if(a=1)printf("给定二叉树是二叉排序树!n");if(a=0)printf("给定二叉树不是二叉排序树!n");void main()Bitree *T;T=Creatree(); /建立二叉树printf("中序遍历:n");Inorder(T); /中序遍历二叉树printf("n");Judgeout(Judgesort_bitree(Btree); /判断是否为排序二叉树4 调试分析实现了设计的所有要求，选取部分运行示意图。图4-1 给定二叉树是二叉排序树图4-2 给定二叉树不是二叉排序树结果分析：成功的编译了代码，实验结果令人满意。先说下判断二叉树数否为排序二叉树的时间复杂度。二叉树以二叉链表存储