《数据结构》课程设计—二叉树操作.docVIP

《数据结构》课程设计报告 题 目 二叉树的操作 学 号 姓 名 班 级 专 业 学 院 信息科学技术学院 指导教师 戴小鹏 日 期 2014年12月22日 一 需求分析： 1．1问题描述 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。 1．2基本要求 输入的形式和输入值的范围； 为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。 输出的形式； 通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。对二叉树的一些运算结果以整型输出。 (3) 程序所能达到的功能； 建立二叉树； 通过递归方法来遍历（先序、中序和后序）二叉树； 通过队列应用来实现对二叉树的层次遍历； 借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等； 运用广义表对二叉树进行广义表形式的打印。 二 概要设计 1、设定“二叉树”的抽象数据类型定义： ADT BiTree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若，则，称BiTree为空二叉树； 若，则，H是如下二元关系： 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； 若则存在且; 若则中存在唯一的元素,且存在上的关系若则中存在唯一的元素,且存在上的关系； 是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的有字树 基本操作： CreateBiTreeT) 操作结果：按照T的定义构造一个二叉树。 BiTreeDepth( T)初始条件：二叉树T已存在。操作结果：返回T的深度。BiTreeWidth(T) 初始条件：二叉树T已存在。 操作结果：返回T的宽度。 PreOderTraverse（T) 初始条件：二叉树T已存在。操作结果：先序遍历打印 InOderTraverse(T)初始条件：二叉树T已存在。操作结果：中序遍历打印T。 PostOderTraverse(T)初始条件：二叉树T已存在。操作结果：后序遍历打印T。 LevelTraverse(T)初始条件：二叉树T已存在。操作结果：层次遍历T。 DeleteXTree(T,TElemType x：初始条件：二叉树已存在。操作结果：删除元素为x的结点以及其左子树和右子树。 CopyTree(T)：初始条件：二叉树T已存在。操作结果：以T为模板，复制另一个二叉树。｝ADT BiTree 2、设定队列的抽象数据类型定义： ADT Queue{ 数据对象：D={ 数据关系：R1={|,,i=2,…，n} 约定端为队列头，端为队列尾。 基本操作： InitQueue(Q)操作结果：构造一个空队列Q。 EnQueue(Q,e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。 DeQueue(Q)初始条件：队列Q已存在。操作结果：删除Q的对头元素，并返回其值。 QueueEmpty(Q) 初始条件：队列Q已存在。操作结果：若Q为空队列，则返回1，否则0。} ADT Queue 3、本程序包含四个模块 1）主程序模块 void main( ) { 初始化；先序输入二叉树各结点元素；各种遍历二叉树；对二叉树进行常见运算；复制二叉树；在复制的二叉树上进行二叉树的常见操作； ｝ 2）二叉树模块——实现二叉树的抽象数据类型和基本操作 3）队列模块——实现队列的抽象数据类型及今本操作 4）广义表打印模块——以广义表形式打印二叉树 5）二叉树运算模块——对二叉树的叶子、非空子孙结点数目、度为2或1的结点数 详细设计 1、主程序中需要的全程量 #define M 10 // 统计二叉树宽度时需用数组对每层宽度进行存储，这M表示数组的长度 2、队列的建立与基本操作 typedef struc QNodte{ BiTree d