文档介绍：《数据结构与数据库》
实验报告
实验题目
二叉树的基本操作及运算
学 院：化学与材料科学学院
专业班级：09级材料科学与工程系 PB0920603
姓 ﻩ名:李维谷
学 号:PB０920６２85
邮 箱：
指导教师：贾伯琪
实验时间：2０1０年10月１7日
需要分析
问题描述:
实现二叉树（包括二叉排序树)的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度,求树的非空子孙结点个数、度为２的结点数目、度为2的结点数目,以及二叉树常用运算。
问题分析:
二叉树树型结构是一类重要的非线性数据结构,对它的熟练掌握是学习数据结构的基本要求。由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。处理本问题,我觉得应该：
建立二叉树；
通过递归方法来遍历(先序、中序和后序)二叉树;
通过队列应用来实现对二叉树的层次遍历；
借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等;
运用广义表对二叉树进行广义表形式的打印。
算法规定：
输入形式:为了方便操作，规定二叉树的元素类型都为字符型,允许各种字符类型的输入,没有元素的结点以空格输入表示,并且本实验是以先序顺序输入的.
输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印,.
程序功能:实现对二叉树的先序、中序和后序遍历，层次遍历。计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为２的结点数目。对二叉树的某个元素进行查找,对二叉树的某个结点进行删除。
测试数据：输 入 一:AＢC□□DE□G□□F□□□ （以□表示空格)，查找5,删除E
预测结果：先序遍历 ABCDＥGF
ﻩﻩ 中序遍历 CBEGDFA
ﻩﻩﻩ 后序遍历 CGEFDBＡ
层次遍历 AＢCDEFＧ
广义表打印 A（Ｂ(C，D(E(，Ｇ），F）))
叶子数 ３ 深度 5 宽度 ２ 非空子孙数 6 度为2的数目 2 度为１的数目2
查找５，成功，查找的元素为E
删除E后,以广义表形式打印A（Ｂ（C，D（，F)))
输 入 二：AＢD□□EH□□□CF□Ｇ□□□ （以□表示空格),查找10，删除B
预测结果:先序遍历 ABＤＥHCFG
ﻩ ﻩ 中序遍历 DＢHEAGFＣ
ﻩﻩﻩ ﻩ 后序遍历 DHEＢGFCA
层次遍历 ABCDEFHG
广义表打印 A(Ｂ(D,E（H)），C（Ｆ(,G）））
叶子数 ３ 深度 4 宽度 3 非空子孙数 7 度为2的数目 2 度为1的数目3
查找10,失败.
删除Ｂ后,以广义表形式打印A（，C(F（，G）））
概要设计
程序中将涉及下列两个抽象数据类型:一个是二叉树，一个是队列。
1、设定“二叉树"的抽象数据类型定义:
ADT BｉTrｅe{
ﻩ数据对象D：Ｄ是具有相同特性的数据元素的集合.
数据关系Ｒ：
若，则,称BiTrｅe为空二叉树;
若，则，H是如下二元关系:
在Ｄ中存在唯一的称为根的数据元素ｒoot，它在关系H下无前驱;
若则存在且；
若则中存在唯一的元素，且存在上的关系若则中存在唯一的元素，且存在上的关系；
是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树,称为根的有字树
基本操作：
CreａtｅBiTrｅe&Ｔ)
操作结果：按照T的定义构造一个二叉树。
BiTrｅeＤｅpｔh（＆ T)
初始条件：二叉树T已存在。
操作结果：返回T的深度。
BiTreeWidtｈ（&T)
初始条件:二叉树T已存在。
操作结果：返回Ｔ的宽度。
ＰreOdeｒTｒaveｒsｅ&Ｔ）
初始条件：二叉树Ｔ已存在。
操作结果：先序遍历打印T,
ＩnOderTraveｒse（&T）
初始条件：二叉树T已存在。
操作结果:中序遍历打印T。
PoｓtOderTravｅ