数据结构实验三——二叉树基本操作及运算实验报告.doc

FILENAME 数据结构实验三——二叉树基本操作及运算实验报告.doc 第 PAGE 2 页 共 NUMPAGES 27 页 《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 需要分析 问题描述： 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。 问题分析： 二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。处理本问题，我觉得应该： 建立二叉树； 通过递归方法来遍历（先序、中序和后序）二叉树； 通过队列应用来实现对二叉树的层次遍历； 借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等； 运用广义表对二叉树进行广义表形式的打印。 算法规定： 输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。 输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。对二叉树的一些运算结果以整型输出。 程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。 测试数据：输 入 一：ABC□□DE□G□□F□□□ （以□表示空格）,查找5,删除E 预测结果：先序遍历 ABCDEGF 中序遍历 CBEGDFA 后序遍历 CGEFDBA 层次遍历 ABCDEFG 广义表打印 A（B（C,D（E（,G）,F））） 叶子数 3 深度 5 宽度 2 非空子孙数 6 度为2的数目 2 度为1的数目2 查找5，成功，查找的元素为E 删除E后，以广义表形式打印A（B（C,D（,F））） 输 入 二：ABD□□EH□□□CF□G□□□ （以□表示空格）,查找10,删除B 预测结果：先序遍历 ABDEHCFG 中序遍历 DBHEAGFC 后序遍历 DHEBGFCA 层次遍历 ABCDEFHG 广义表打印 A（B(D,E(H)),C(F(,G))） 叶子数 3 深度 4 宽度 3 非空子孙数 7 度为2的数目 2 度为1的数目3 查找10，失败。 删除B后，以广义表形式打印A（，C（F（，G））） 概要设计 程序中将涉及下列两个抽象数据类型：一个是二叉树，一个是队列。 1、设定“二叉树”的抽象数据类型定义： ADT BiTree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R： 若，则，称BiTree为空二叉树； 若，则，H是如下二元关系： 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； 若则存在且; 若则中存在唯一的元素,且存在上的关系若则中存在唯一的元素,且存在上的关系； 是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的有字树 基本操作： CreateBiTreeT) 操作结果：按照T的定义构造一个二叉树。 BiTreeDepth( T) 初始条件：二叉树T已存在。 操作结果：返回T的深度。 BiTreeWidth(T) 初始条件：二叉树T已存在。 操作结果：返回T的宽度。 PreOderTraverseT) 初始条件：二叉树T已存在。 操作结果：先序遍历打印T， InOderTraverse(T) 初始条件：二叉树T已存在。 操作结果：中序遍历打印T。 PostOderTraverse(T) 初始条件：二叉树T已存在。 操作结果：后序遍历打印T。 LevelTraverse(T) 初始条件：二叉树T已存在。 操作结果：层次遍历T。 DeleteXTree(T,TElemType x) 初始条件：二