244305643.doc
《数据结构与数据库》
实验报告
实验题目
二叉树的基本操作及运算
学
院：化学与材料科学学院
专业班级：09级材料科学与工程系 PB0920603 姓 学 邮
名：李维谷 号：PB09206285 箱：liwg@mail.ustc.edu.cn
指导教师：贾伯琪
第 1 页 共 36 页
244305643.doc
实验时间：2010年10月17日
一、 需要分析
问题描述：
实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。
问题分析：
二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。处理本问题，我觉得应该：
1、 建立二叉树；
2、 通过递归方法来遍历（先序、中序和后序）二叉树； 3、 通过队列应用来实现对二叉树的层次遍历；
4、 借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等； 5、 运用广义表对二叉树进行广义表形式的打印。
算法规定：
输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。
输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。对二叉树的一些运算结果以整型输出。
程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。
测试数据：输 入 一：ABC□□DE□G□□F□□□ （以□表示空格）,查找5,删除E
预测结果：先序遍历 ABCDEGF
中序遍历 CBEGDFA 后序遍历 CGEFDBA
层次遍历 ABCDEFG
第 2 页 共 36 页
244305643.doc
广义表打印 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： 若D?? ，则R??，称BiTree为空二叉树； 若D?? ，则R??H?，H是如下二元关系：
（1） 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2） 若D??root???, 则存在D??root???Dl,Dr?,且Dl?Dr??;
（3） 若Dl??,则Dl中存在唯一的元素xl,?root,xl??H,且存在Dl上的关系
Hl?H;若Dr??,则Dr中存在唯一的元素xr,?root,xr??H,且存在Dr上的
关系Hr?H;H??root,xl?,?root,xr?,Hl,Hr；
（4） ?Dl,?Hl??是一棵符合本定义的二叉树，称为根的左子树，?Dr,?Hr??是一棵符合本
定义的二叉树，称为根的有字树
基本操作：
CreateBiTree&T)
操作结果：按照T的定义构造一个二叉树。
第 3 页 共 36 页
??