数据结构与算法课程实验报告

实验四：二叉树的基本操作

姓名：沈靖雯

班级：14信息与计算科学（2）班 学号：2014326601094

实验四 二叉树的基本操作

【实验内容】

实现创建和遍历二叉树的基本操作

【实验目的】

掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法；掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想，并学会遍历算法的递归实现和非递归实现。

【问题描述】

（1） 编程实现构造一棵二叉树的算法，适合任意合法输入的二叉树的建

立，并进行相应异常处理。

（2） 编程实现在二叉链表这种存储方式下，实现二叉的遍历，可采用递

归或者非递归实现，遍历算法可在先序、中序和后序遍历算法中任选其一。

【问题实现】

一、实现链队列基本运算

（1）抽象数据类型 ADT BTree {

数据对象D:?D是具有相同特性的数据元素的集合。? 基本操作： CreatBiTree(*T)

操作结果：构造二叉树T。 PreOrderTraverse(T)

初始条件：二叉树T已存在。 操作结果：先序遍历T。 InOrderTraverse(T)

初始条件：二叉树T已存在。 操作结果：中序遍历T。 PostOrderTraverse(T)

初始条件：二叉树T已存在。 操作结果：后序遍历T。 } ADT BTree

（2）主要实现思路与主要程序代码： 1）.首先定义二叉树结点结构；

typedef struct Node { char data; struct Node *lchild,*rchild; //左右孩子指针 }BiTNode,*BTree;

2）.其次定义一个二叉树构造函数int CreatBiTree(BTree *T)；采用递归先序法构造二叉树；

scanf(\

if(ch==' ') *T=NULL;//T为空二叉树 else {

if(!(*T=(BTree)malloc(sizeof(BiTNode)))) return (OVERFLOW); (*T)->data=ch; CreatBiTree(&((*T)->lchild)); CreatBiTree(&((*T)->rchild)); }

3）.定义遍历函数（递归先序为例）；

//先序遍历二叉树，递归实现

void PreOrderTraverse(BTree T) { if(T) { printf(\ PreOrderTraverse (T->lchild); PreOrderTraverse (T->rchild); } }

这里用printf代替visit（），简化程序代码；

4）.定义主函数，总体完成以上所有函数功能的实现(构建二叉树与遍历二叉树）。

程序运行如图1：

图 1

【总结】

实验结果实现了问题的基本要求。

对该问题的操作使我对二叉树的结构更加了解，尤其在二叉树遍历部分，对