6.5.1　二叉树遍历的应用

在以上讨论的遍历算法中，访问结点的数据域信息，即操作Visite（bt－data）具有更一般的意义，需根据具体问题，对bt数据进行不同的操作。下面介绍几个遍历操作的典型应用。

1.查找数据元素

Search（bt，x）在bt为二叉树的根结点指针的二叉树中查找数据元素x。查找成功时返回该结点的指针；查找失败时返回空指针。

算法实现如下，注意遍历算法中的Visite（bt－data）等同于其中的一组操作步骤。

算法6.21 查找数据元素

2.统计出给定二叉树中叶子结点的数目

（1）顺序存储结构的实现

算法6.22 统计叶子结点个数1

（2）二叉链表存储结构的实现

算法6.23 统计叶子结点个数2

3.创建二叉树二叉链表存储，并显示

设创建时，按二叉树带空指针的先序次序输入结点值，结点值类型为字符型。输出按中序输出。

CreateBinTree（BinTree＊bt）是以二叉链表为存储结构建立一棵二叉树T的存储，bt为指向二叉树T根结点指针的指针。设建立时的输入序列为：AB0D00CE00F00。

建立如图6－7（b）所示的二叉树存储。

InOrderOut（bt）为按中序输出二叉树bt的结点。

算法实现如下，注意在创建算法中，遍历算法中的Visite（bt－data）被读入结点、申请空间存储的操作所代替；在输出算法中，遍历算法中的Visite（bt－data）被C语言中的格式输出语句所代替。

算法6.24 先序序列建立二叉树

4.表达式运算

我们可以把任意一个算数表达式用一棵二叉树表示，图6－23所示为表达式3x2＋x－1／x＋5的二叉树表示。在表达式二叉树中，每个叶结点都是操作数，每个非叶结点都是运算符。对于一个非叶子结点，它的左、右子树分别是它的两个操作数。

图6－23 表达式3x2＋x－1／x＋5的二叉树表示示意

对该二叉树分别进行先序、中序和后序遍历，可以得到表达式的三种不同表示形式。

前缀表达式 ＋－＋＊3＊xxx／1x5

中缀表达式 3＊x＊x＋x－1／x＋5

后缀表达式 3xx＊＊x＋1x／－5＋

中缀表达式是经常使用的算术表达式，前缀表达式和后缀表达式分别称为波兰式和逆波兰式，它们在编译程序中有着非常重要的作用。