中南大学 数据结构实验报告一---二叉树的操作算法

中南大学

信息科学与工程学院

数据结构 实验报告

实验名称： 二叉树的操作算法 班 级： 物联网1103班 学 号： 姓 名： 指导老师： 刘 安 丰 实验时间： 2013年4月22日

中南大学 数据结构实验报告一---二叉树的操作算法

数据结构实验一 物联网 1103 樊列龙 0909113224

一、实验目的 1、掌握二叉树的定义； 2、掌握二叉树的基本操作； 3、学会使用递归和非递归的方法遍历二叉树； 4、熟悉使用 C++/STL 提供的方法； 5、理解面向对象的思想的优势； 3、提高编程能力，使用一种语言描述算法算法(本次实验使 用 C++语言描述) 。

二、实验内容

实现二叉树的常用操作算法：包括二叉树的建立、遍历、求高 度、线索化等操作。

三、ADT 设计 二叉树的抽象数据类型： ADT BinaryTree { 数据对象 D:D 是具有相同特性的数据元素的集合。 数据关系 R: 若 D=Φ ,则 R= Φ ,则称 BinaryTree 为空二叉树； 若 D≠Φ ,则 R={H},H 是如下的二元关系： ( 1) 、在 D 中存在唯一的称为根的数据元素 root,

1

中南大学 数据结构实验报告一---二叉树的操作算法

数据结构实验一 物联网 1103 樊列龙 0909113224

它在关系 H 下无前驱。 ( 2) 、 若 D-{root}≠Φ , 则存在 D-{root}={D1, Dr}, 且 D1∩Dr=Φ ; (3) 、若 D ≠ Φ ,则 D1 中存在唯一的元素 X1, <root,X1>∈H,且存在 D1 上的关系 H1∈H。 } 基本操作： 1、void PreOrderTraverse 2、void InOrderTraverse 3、void PostOrderTraverse 4、void BiTreeDepth 5、void DestroyBiTree 6、bool BiTrrEmpty() const 7、BiTNode<T>* Root() 输出二叉树的前序遍历结果  输出二叉树的中序遍历结果  输出二叉树的后序遍历结果 求二叉树的深度 销毁二叉树 判断二叉树为空 找到二叉树根节点

8、void LevelOrderTraverse() 层次遍历二叉树

四、算法设计分析(一) 、非递归先序遍历二叉树前序遍历的算法借助栈来实现： (1)栈中存放已被访问的节点 (2)先要往左走到最底端，也就是此时节点的左孩子为 NULL (3)然后向右走一步(通过出栈来获得其双亲节点数据，将当前指针

2

中南大学 数据结构实验报告一---二叉树的操作算法

数据结构实验一 物联网 1103 樊列龙 0909113224

指向它的右孩子即可)

(4)以这个右孩子为新的头节点，如果它为 NULL,则继续出栈获得上 一个双亲节点，在向右一步，重复 这个过程，直到栈为空或者有一个节点的右孩子不为 NULL (5)有了新的头节点后，重复(2) (3) ,直到栈为空，也就是遍历完 毕.

(二) 、非递归中序遍历二叉树(1)构造栈，头节点入栈，栈中元素为存放着未被访问的节点 (2)向左走到最底端，退栈，访问这个节点，然后向右走一步 (3)以右节点为新的头节点，继续(2) ,直到栈为空，表示遍历结束

(三) 、非递归中序遍历二叉树(1)我们需要的不是栈了，

而是队列 (2)当访问一个节点的时候，我们要考虑其左右孩子，若有不为空的 孩子就让它入队列，在其双亲节点后面排队 (3)采取从左到右、从上到下的层次，每让最前端的出队列被访问时， 就应该让它的不为空的孩子指针入队列 (4)当队列为空的时候，就表示遍历完毕了

3

中南大学 数据结构实验报告一---二叉树的操作算法

数据结构实验一 物联网 1103 樊列龙 0909113224

五、实验结果

树是否为空？true, 树的深度 = 0 树是否为空？false, 树的深度 = 4 先序输出结果：A B D G E C F 中序遍历结果：G D B E A C F 后序遍历结果：G D E B F C A 层次遍历结果：A B C D E F G

树是否为空？true, 树的深度 = 0

4

中南大学 数据结构实验报告一---二叉树的操作算法

数据结构实验一 物联网 1103 樊列龙 0909113224

六、实验总结 在编写程序时， 遇到了一个程序保存后编译正确却运行不了之 后请教了我们班的同学才知道是第一个函数出了问题改了之后就 好了。 做程序编写时必须要细心，有时候问题出现了，可能会一直查 不出来。自己也不容易发现。在编写这个程序时。我就出现了这个 问题，之后一定要尽量避免此类问题出现。

5

中南大学 数据结构实验报告一---二叉树的操作算法

数据结构实验一 物联网 1103 樊列龙 0909113224

六、实验源程序 stdhead.h/* ========================================================================== *\ * @Copyright (c) 2013, CSU 樊列龙, All rights reserved. * * @fileName: stdhead.h * @brief: 包含一些常用的头文件 * * @version: * @author: 樊列龙 * @time: 2013-4-23/上午4:42:02 * \* ========================================================================= */ #ifndef STDHEAD_H_ #define STDHEAD_H_ #include #include #include #include #include #include #include #include <iostream> <fstream> <queue> <stack> <stdio.h> <string> <cstring> <cassert>

using namespace std; #endif /* STDHEAD_H_ */

BiTNode.h/* ========================================================================== *\

6

中南大学 数据结构实验报告一---二叉树的操作算法

数据结构实验一 物联网 1103 樊列龙 0909113224 * @Copyright (c) 2013, CSU CocoonFan All rights reserved. * @fileName: BiTNode.h * @brief: 二叉链表节点类型结构体 …… 此处隐藏：5953字，全部文档内容请下载后查看。喜欢就下载吧 ……