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

《数据结构课程设计---判别给定的二叉树是否为二叉排序树》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

3、程序源代码74调试分析95课程总结116参考文献121需求分析7780905068883456图1-1二叉树以图1-1所示的二叉树为例设计，建立一个以二叉链表方式存储的二叉树，输入结点信息时按照完全二叉树的结点顺序输入（1为虚结点，0为输入结束）。由于一棵二叉排序树中序遍历后的序列是递增有序的，因此可利用中序遍历一棵二叉树后的序列是否递增有序来判断是否为二叉排序树。如图，二叉树的结点输入顺序为77809050168881134560（1为虚结点，0为输入结束），中序遍历之后的顺序为5080773468569088，由于中序遍历之后的序列不是递增有

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

5、ort_bitree(Btree))判断是否为二叉树是二叉排序树不是二叉排序树序树结束YN结束图2-2主要流程图开始sign=0,front=0,rear=-1,T=NULLch!=0?ch!=1?rear++sign%2==0?front++sign++YYNYNB[rear]=Srear=front创建结点SYNsign%2==1?T=Ssign++NYB[front]→lchild=SB[front]←rchild=Sfront++sign++N结束图2-3建立二叉树3详细设计3.1程序分析建立一个以二叉链表方式存储的二叉树，建立二叉树时，

6、按照完全二叉树的结点顺序输入，1表示虚结点，0表示输入结束。若不是虚结点时，则建立一个新结点，并且将其作为左孩子或右孩子结点连接到它的父结点上（第一个结点无父结点）；若是虚结点，则将空结点（NULL）作为左孩子或右孩子结点连接到它的父节点上。判定二叉树时，中序遍历整棵二叉树，访问根结点时将根结点信息存入一个数组中，以用来比较中序遍历后序列是否为空。比较数组元素时，从下标为0的数组元素开始比较，先将下标为i=0的a[i]与下标为1的a[i+1]比较，如果a[i]>a[i+1]，则结束比较，即该二叉树不是二叉排序树，否则继续比较，直至比较完整个数组元

7、素。3.2程序源代码#include"stdafx.h"//编写的任何.cpp文件都必须首先包含stdafx.h#include#include#definemax10typedefstructnode{intdata;//数据域node*lchild,*rchild;//左孩子指针，右孩子指针}Bitree;//结点的结构体定义Bitree*B[max];inttemp=0;intBtree[max];Bitree*Creatree(){//建立二叉树Bitree*T,*S;intch;intfront,r

8、ear,sign;sign=0;//结点的序号从0开始编号（按照完全二叉树的顺序标记）front=0;//双亲结点下标初值rear=-1