实验三 二叉树的应用举例

一、 实验目的

要求学生必须掌握二叉树的建立及先序、中序、后序三种遍历方式，在此基础上实现树的一些简单应用问题

二、 实验内容及步骤

1.二叉链表的建立，先（中、后）序遍历

输入：字符串序列

输出：先（中、后）序序列

处理方法：通过补虚结点，使二叉树中各实际结点均具有左右孩子，再对该二叉树按先序遍历进行输入。以字符串的形式:根、左子树、右子树定义一棵二叉树：

1) 空树以空白字符‘#’表示

2) 只含一个根结点的二叉树（图1示）以字符串‘A##’表示

3) 一般的二叉树，以图2为例，以下列字符串表示：AB#C##D##

4) 无论先序、中序、后序遍历二叉树，遍历时的搜索路线是相同的：从根节点出发，逆时针沿二叉树外

缘移动，对每个节点均途经三次。

先序遍历：第一次经过节点时访问。中序遍历：第二次经过节点时访问。后序遍历：第三次经过节点时访问

图1

图2

2. 统计二叉树中叶子结点的个数，计算二叉树的深度。

输入：字符串序列

输出：叶子结点的个数，二叉树的深度

处理方法：

1) 先序遍历二叉树。在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的

参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。

2) 后序遍历二叉树。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由

此，先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。

程序：

#include<iostream.h>

#include <stdlib.h>

#define TRUE 1

#define FALSE 0