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

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

2、，可以按路径覆盖的方法给出两组主要的测试数据。 任务交付： 1. 课程设计论文，包括需求分析、概要设计、详细设计、调试分析、课程总结、 参考文献等部分。 2. 课程设计论电子文档及程序源代码。 进度安排： 本课程设计时间为 17、18 教学周。其中包含设计、代码调试、课程设计论文撰写、 验收与答辩几个阶段。 第 1 周 查找资料、完成初步设计、代码设计与初步调试； 第 2 周 调试、测试、验收、课程设计论文撰写、答辩。 指导教师（签字） ： 2011 年 12 月 16 日 学院院长（签字） ： 2011 年 12 月 16 日 目录目录 1 需求分析 3 2 概要设计 4 2.1 存储结构设

3、计说明 4 2.2 程序功能图 . 4 2.3 算法流程图 . 5 3 详细设计 7 3.1 程序分析 . 7 3.2 程序源代码 . 7 4 调试分析 9 5 课程总结 11 6 参考文献 . 12 1 1 需求分析需求分析 图图 1-1 二叉树二叉树 以图 1-1 所示的二叉树为例设计， 建立一个以二叉链表方式存储的二叉 树，输入结点信息时按照完全二叉树的结点顺序输入（1 为虚结点，0为输 入结束） 。由于一棵二叉排序树中序遍历后的序列是递增有序的，因此可利 用中序遍历一棵二叉树后的序列是否递增有序来判断是否为二叉排序树。 如图，二叉树的结点输入顺序为 77 80 90 50 1 68 8

4、8 1 1 34 56 0 （1 为 虚结点，0为输入结束） ，中序遍历之后的顺序为 50 80 77 34 68 56 90 88 ， 由于中序遍历之后的序列不是递增有序的，因此可判断出此二叉树不是二 叉排序树。 77 80 90 50 68 88 34 56 2 概要设计概要设计 2.2.1 1 存储结构设计说明存储结构设计说明 typedef struct node int data; /数据域 node *lchild,*rchild; /左孩子指针，右孩子指针 Bitree; /结点的结构体定义 2.22.2 程序功能图程序功能图 图图 2 2- -1 1 程序功能图程序功能图 建立二叉树（按照完全二叉树的结点顺序输入） 中序遍历二叉树，并将结点保存在数组中 判断是否为二叉排序树 比较数组元素，看是否有序递增 2.32.3 算法流程图算法流程图 选取部分核心核心流程图如下： 图图 2 2- -2 2 主要流程图主要流程图 开始 初始化二叉树 Bitree *Creatree() Inorder(Bitree *