资源描述：
《《二叉树基本操作实验报告》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、e446270a103f8a658993f3b659f8ccda.doc《数据结构与数据库》实验报告实验题目二叉树的基本操作及运算学院：化学与材料科学学院专业班级：09级材料科学与工程系PB0920603姓名：李维谷学号：PB09206285邮箱：liwg@mail.ustc.edu.cn指导教师：贾伯琪实验时间：2010年10月17日第27页共27页e446270a103f8a658993f3b659f8ccda.doc一、需要分析问题描述：实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点
2、个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。问题分析：二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。处理本问题，我觉得应该：1、建立二叉树；2、通过递归方法来遍历（先序、中序和后序）二叉树；3、通过队列应用来实现对二叉树的层次遍历；4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等；5、运用广义表对二叉树进行广义表形式的打印。算法规定：输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输
3、入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。对二叉树的一些运算结果以整型输出。程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E预测结果：先序遍历ABCDEGF中序遍历CBEGDFA后序遍历CGEFDBA层次遍历ABCD
4、EFG广义表打印A（B（C,D（E（,G）,F）））叶子数3深度5宽度2非空子孙数6度为2的数目2度为1的数目2第27页共27页e446270a103f8a658993f3b659f8ccda.doc查找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
5、查找10，失败。删除B后，以广义表形式打印A（，C（F（，G）））一、概要设计程序中将涉及下列两个抽象数据类型：一个是二叉树，一个是队列。1、设定“二叉树”的抽象数据类型定义：ADTBiTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若，则，称BiTree为空二叉树；若，则，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若则存在且;（3）若则中存在唯一的元素,且存在上的关系若则中存在唯一的元素,且存在上的关系；（4）是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的有字树基本操
6、作：CreateBiTree&T)操作结果：按照T的定义构造一个二叉树。BiTreeDepth(&T)初始条件：二叉树T已存在。操作结果：返回T的深度。第27页共27页e446270a103f8a658993f3b659f8ccda.docBiTreeWidth(&T)初始条件：二叉树T已存在。操作结果：返回T的宽度。PreOderTraverse&T)初始条件：二叉树T已存在。操作结果：先序遍历打印T，InOderTraverse(&T)初始条件：二叉树T已存在。操作结果：中序遍历打印T。PostOderTraverse(&T)初始条件：二叉树T已存在。操作结果：后
7、序遍历打印T。LevelTraverse(&T)初始条件：二叉树T已存在。操作结果：层次遍历T。DeleteXTree(&T,TElemTypex)初始条件：二叉树已存在。操作结果：删除元素为x的结点以及其左子树和右子树。CopyTree(&T)初始条件：二叉树T已存在。操作结果：以T为模板，复制另一个二叉树。｝ADTBiTree2、设定队列的抽象数据类型定义：ADTQueue{数据对象：D={数据关系：R1={<>
8、,,i=2,…，n}约定端为队列头，端为队列尾。基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。EnQueue(&Q,
