实验四 二叉树的操作

班级：计算机1002班

姓名：**

学号：**

完成日期：20XX.6.14

题目：对于给定的一二叉树，实现各种约定的遍历。

一、实验目的：

（1）掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法；

（2）掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想，并学会遍历算法的递归实现和非递归实现。

二、实验内容：构造二叉树，再实现二叉树的先序、中序、后序遍历，最后统计二叉树的深度。

三、实验步骤：

(一) 需求分析

1. 二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。因为树的每一个左右子树又是一颗二叉树，所以用递归的方法来建立其左右子树。二叉树的遍历是一种把二叉树的每一个节点访问并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句来实现。

2．程序的执行命令为：

1）构造结点类型，然后创建二叉树。

2）根据提示，从键盘输入各个结点。

3）通过选择一种方式（先序、中序或者后序）遍历。

4）输出结果，结束。

(二)概要设计

1.二叉树的二叉链表结点存储类型定义

typedef struct Node

{

DataType data;

struct Node *LChild;

struct Node *RChild;

}BitNode,*BitTree;

2.建立如下图所示二叉树：void CreatBiTree(BitTree *bt)用扩展先序遍历序列创建二叉树，如果是当前树根置为空，否则申请一个新节点。

3.本程序包含四个模块

1) 主程序模块：

2)先序遍历模块

…… …… 余下全文