二叉树基本操作+数据结构+实验报告

中南大学

数据结构实验报告

题 目 二叉树基本操作 学生姓名 联系电话 指导老师 专业班级 完成时间 2007年11月25 日

第 2 页 共 12 页

目 录

一、 系统功能介绍…………………………………2

二、 需求分析………………………………………2

三、 概要设计………………………………………2

四、 详细设计………………………………………5

五、 调试分析………………………………………8

六、 使用说明………………………………………8

七、 测试结果………………………………………9

八、 心得体会………………………………………10

九、 附录（程序代码）……………………………11

2

第 3 页 共 12 页

一、系统功能介绍

该程序是用C-Free编写的，主要功能是实现二叉树的定义和基本操作，包括定义二叉树的结构类型以及各个操作的具体函数的定义和主函数的定义。

各操作主要包括：初始化二叉树、按先序次序建立二叉树、检查二叉树是否为空、前序、中序、后序遍历树的方式、求树的深度、求树的结点数目、清空二叉树等九个对树的操作。

二、需求分析

本程序由C-free工具编写完成了初始化，建立二叉树，检查树空与否，用前序、中序、后序遍历二叉树，求树的深度，求树的结点数目，清空二叉树等功能。

1）输出的形式和输出值的范围：在选择操作中，都以整型（数字）选择操作，插入和输出的数值都是char类型的字符；

2）输出的形式：在每次操作后，都会提示操作是否成功或者操作的结果；

3）程序达到的功能：完成初始化、检查是否为空、请空、遍历、求树的深度、求树的结点数目等功能；

4)测试数据设计：

A,按先序次序建立二叉树。依次输入a,b,c,d,e,f,g.建立二叉树。 B,分别按先序，中序和后序遍历输出二叉树中的结点元素。 C,求树的高度和结点数。

三、概要分析

为了实现上述功能，定义二叉树的抽象数据类型。 ADT BinTree{

数据对象D:D是具有相同特性的数据元素的集合。 数据关系R:

若D=￠，称BinTree为空二叉树

若D≠￠,则R={H},H是如下的二元关系；

（1） 在D中存在唯一的称为根的数据元素root,它在关系H下无前驱； （2） 若D-{root}≠￠，则存在D-{root}={D1,Dr},且D1∩Dr=￠；

（3） 若D≠￠，则中存在唯一的元素x1,∈H,，且存在D1上的关系H1H;若则

中存在唯一的元素且存在上的饿关系

（4） 是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为

根的右子树。

基本操作 P：

3

第 4 页 共 12 页

BinTree BinTreeInit() {

操作结果：构造空的二叉树 初始条件：给出二叉树的定义 }

BinTree BinTreeCreat(BinTree &BT) {

操作结果：用先序序列创建一个二叉树 初始条件：构造了空的二叉树 }

int BinTreeEmpty() {

操作结果：返回0或1，即树的空与否 初始条件：二叉树存在 }

void PreBinTraverse(BinTree BT) {

操作结果：按先序序列遍历输出二叉树 初始条件：二叉树存在 }

void InBinTraverse(BinTree BT) {

操作结果：按中序序列遍历输出二叉树 初始条件：二叉树存在 }

void PastBinTraverse(BinTree BT) {

操作结果：按后序序列遍历输出二叉树 初始条件：二叉树存在 }

int BinTreeDepth(BinTree BT) {

操作结果：返回二叉树的深度 初始条件：二叉树存在 }

int BinTreeCount(BinTree BT) {

操作结果：返回二叉树的结点个数 初始条件：二叉树存在 }

void BinTreeClear(BinTree &BT) {

操作结果：清空释放二叉树的结点 初始条件：二叉树存在

4

第 5 页 共 12 页

} }

四、详细设计

流程图

BinTreeInit()BinTreeCreat()BinTreeEmpty() PreBinTraverse(BT)Main()BinTraverse()InBinTraverse(BT) PastBinTraverse(BT) BinTreeDepth()BinTreeCount()BinTreeClear() 实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。 typedef int DataType; 树节点类型定义

typedef struct BitNode{ int data;

struct BitNode *lchild,*rchild;

}BitNode,*BitTree;1. 初始化二叉树，即把树根指针置空 1. Status BinTreeInit() { BitTree BT;

BT=(BinTree)malloc(sizeof(BinNode)); BT=NULL; return OK; }

2. 按先序次序建立一个二叉树

5