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

课程设计任务书学 院专 业学 生 姓 名学 号题 目判别给定的二叉树是否为二叉排序树内容及要求：设计内容：判别给定的二叉树是否为二叉排序树，设此二叉树以二叉链表存储，且树中结点的关键字均不相同。为实现上述功能，需要解决的关键问题是：建立一棵二叉树及判定二叉树过程。要求：1.设计数据结构：建立的是二叉树，所以逻辑结构为树形结构。定义存储结构为链式存储结构，用typedef定义结点的结构体。2.在turboc或兼容环境完成上述题目的代码编写与调试；3.程序运行界面交互性好；输入输出数据时，应该有相应的提示。4.给出两组测试数据，可以按路径覆盖的方法给出两组主要的测试数据。任务交付：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程序源代码74 调试分析95 课程总结116参考文献121 需求分析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 存储结构设计说明 typedef struct nodeint data; /数据域node *lchild,*rchild; /左孩子指针，右孩子指针bitree; /结点的结构体定义 2.2程序功能图建立二叉树（按照完全二叉树的结点顺序输入）中序遍历二叉树，并将结点保存在数组中比较数组元素，看是否有序递增判断是否为二叉排序树 图2-1 程序功能图2.3算法流程图选取部分核心流程图如下：开始初始化二叉树bitree *creatree()inorder(bitree *t)judgeout(judgesort_bitree(btree)判断是否为二叉树是二叉排序树不是二叉排序树序树结束yn结束图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表示输入结束。若不是虚结点时，则建立一个新结点，并且将其作为左孩子或右孩子结点连接到它的父结点上（第一个结点无父结点）；若是虚结点，则将空结点（null）作为左孩子或右孩子结点连接到它的父节点上。判定二叉树时，中序遍历整棵二叉树，访问根结点时将根结点信息存入一个数组中，以用来比较中序遍历后序列是否为空。比较数组元素时，从下标为0的数组元素开始比较，先将下标为i=0的ai与下标为1的ai+1比较，如果aiai+1，则结束比较，即该二叉树不是二叉排序树，否则继续比较，直至比较完整个数组元素。3.2程序源代码#include stdafx.h /编写的任何.cpp文件都必须首先包含stdafx.h#include#include#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(建立二叉树(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) /双亲结点下标与本身下标相同时，即无双亲结点（只有第一个结点会产生这种情况） 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 *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;ibtreei+1) /不是有序递增的 sign=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 给定二叉树不是二叉排序树结果分析：成功的编译了代码，实验结果令人满意。先说下判断二叉树数否为排序二叉树的时间复杂度。二叉树以二叉链表存储，在建立二叉树，中序遍历二叉树和判别时的时间复杂度都为o(n)。再说下编程遇到的问题，编程的关键是要建立一棵二叉树和判别是否为排序二叉树。其中判断时，用到了递归的思想。调试时也遇到了一些问题，由于对一些头文件的不熟悉，缺少，导致程序无法运行等小错误通过查阅一些资料得到了解决。再有就是由于程序涉及到指针，因此有时指针随机访问到系统隐藏空间时会出现异常终端，通过改进，异常出现的几率大大降低，可认为程序能近似完美运行。最后说下算法的优缺点，优点是：由于使用二叉链表存储，结构简单，可以方便的构造任何形状的二叉树，并可以方便的实现二叉树的大多数操作。缺点是：查找当前结点的双亲结点操作实现起来比较麻烦。而且存储效率不高，进一步优化的话，可以逐条归类存储。算法改进的话，可以调整下操作界面，使人机交流更简单，方便用户操作。5 课程总结 数据结构的课程设计终于结束，真的很开心。经过一个学期的学习，我觉得课设是对于我们数据结构掌握程度的测验与评估。这两周的课设，从开始的确定命题，到搜集资料，到初步编程，到修改代码，到最终完成代码，这是一个学习的过程，一个升华的过程。我想课设的意义也是在于此吧。这个程序由于使用二叉链表存储，结构简单，可以方便的构造任何形状的二叉树，并可以方便的实现二叉树的大多数操作。但是他也存在不足，查找当前结点的双亲结点操作实现起来比较麻烦。而且存储效率不高，进一步优化的话，可以逐条归类存储。调试时也遇到了一些问题，由于对一些头文件的不熟悉，缺少，导致程序无法运行等小错误通过查阅一些资料得到了解决。再有就是由于程序涉及到指针，因此有时指针随机访问到系统隐藏空间时会出现异常终端，通过改进，异常出现的几率大大降低，可认为程序能近似完美运行。虽然刚开始很困难，但是只要你愿意做，就一定能做到。当然课设也有很多的不足，由于刚学完数据结构没多久，因此没有建立一个系统的知识框架，在编程时大体上还是延续c的思路，并没有过多的采用数据结构在算