5.3.4　实验提示

本实验主要采用递归的方法来实现相关的操作，采用结构定义二叉树结点的类型，采用普通函数对二叉树进行每一种操作的处理。

至于非递归的方法，请读者自己思考。

下面列出了具体的程序供读者参考。

程序：

定义二叉树结点结构和操作的头文件bitree.h

// 定义二叉树结点值的类型为字符型

　　typedef char ElemType;

// 定义二叉树结点类型

// 初始化二叉树，即把树根指针置空

　　void InitBiTree(BiTreeNode * ＆BT);

// 根据存于字符数组的二叉树广义表建立对应的二叉树存储结构

　　void CreateBiTree(BitreeNode * ＆BT，char * a);

// 判断二叉树是否为空

　　bool BiTreeEmpty(BiTreeNode * BT);

// 按任一种遍历次序输出二叉树中的所有结点

　　void TraverseBiTree(BiTreeNode * BT, int mark);

// 求二叉树的深度

　　int BitreeDepth(BiTreeNode * BT);

// 求二叉树中的所有结点数

　　int BiTreeCount(BiTreeNode * BT);

// 求二叉树中的所有叶子结点数

　　int BiTreeLeafCount(BiTreeNode * BT);

// 按照广义表形式输出整个二叉树

　　void PrintBiTree(BiTreeNode * BT);

// 清除二叉树，使之变成一棵空树

　　void ClearBiTree(BiTreeNode * ＆amp;BT);

二叉树操作的实现文件bitree.cpp

说明：字符串流类包括输入字符串流类istrstream，输出字符串流类ostrstream和输入输出字符串流类strstream三种。它们都被定义在系统头文件strstrea.h中。只要在程序中带有该头文件，就可以使用任一种字符串流类定义字符串流对象。每个字符串流对象简称为字符串流。

#include ＜iostream.h＞

#include ＜stdlib.h＞

#include ＜strstrea.h＞

// 初始化二叉树，即把树根指针置空

// 根据存于字符数组的二叉树广义表建立对应的二叉树存储结构

// 按任一种遍历次序输出二叉树中的所有结点

// 求二叉树的深度

// 求二叉树中的所有结点数

// 求二叉树中的所有叶子结点数

// 按照广义表形式输出整个二叉树

// 清除二叉树，使之变成一棵空树

二叉树操作的主程序文件bitreeMain.cpp