内容发布更新时间 : 2024/5/18 5:36:04星期一 下面是文章的全部内容请认真阅读。

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 页

??