二叉树的应用

6.5　二叉树的应用

本节介绍二叉树的基本应用,包括求二叉树的叶结点数、总结点数、二叉树的深度等,重点介绍标识符树的应用。

6.5.1　二叉树的基本应用

1.统计二叉树叶子结点数

（1）基本思想。若二叉树结点的左子树和右子树都为空,则该结点为叶子结点。可先对全局变量count＋1,然后依次递归统计T的左子树叶子结点数和T的右子树叶子结点数。

（2）具体算法如下。

2.求二叉树结点总数

（1）基本思想。若二叉树根结点不为空,则计数器count加1,然后依次递归统计T的左子树结点数和T的右子树结点数。

（2）具体算法如下。

3.求二叉树的深度

（1）基本思想。若二叉树为空,则返回0；否则,递归统计左子树的深度,然后递归统计右子树的深度,递归结束后,返回其中较大的一个深度值,即是二叉树的深度。

（2）具体算法如下。

4.查找数据元素

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

（1）基本思想。先判断二叉树的根结点是否与x相等,若相等则返回,否则,分别在T－＞lchild为根结点指针的二叉树中递归查找数据元素x,以及在T－＞rchild为根结点指针的二叉树中递归查找数据元素x。

（2）具体算法如下。

6.5.2　标识符树与表达式

将算术表达式用二叉树来表示,称为标识符树,又称为二叉表示树。

1.标识符树的特点

（1）运算对象（标识符）都是叶结点。

（2）运算符都是根结点。

2.由表达式产生标识符树的方法

（1）读入表达式的一部分产生相应的二叉树后,再读入运算符时,将该运算符与二叉树根结点的运算符比较优先级的高低。

①若读入优先级高于根结点的优先级,则读入的运算符作为根的右子树,原来二叉树的右子树成为读入运算符的左子树。

②若读入优先级等于或低于根结点的优先级,则读入运算符作为树根,而原来二叉树作为它的左子树。

（2）遇到括号时,先使括号内的表达式产生一棵二叉树,再把它的根结点连接到前面已产生的二叉树根结点的右子树上去。

（3）单目运算符＋、－,加运算对象θ（表示正负号）。

例如,－A表示为如图6－29所示的标识符树。

3.应用举例

【例6－7】　画出表达式A＊B＊C的标识符树（见图6－30）,并求它的前序序列和后序序列。

图6－29　标识符树

图6－30　例6－7的标识符树

（1）其前序序列为:＊＊A B C

（2）其后序序列为:A B＊C＊

【例6－8】　画出表达式A＊（B＊C）的标识符树（见图6－31）,并求它的前序序列和后序序列。

（1）其前序序列为:＊A＊B C

（2）其后序序列为:A B C＊＊

【例6－9】　画出表达式－A＋B－C＋D的标识符树（见图6－32）,并求它的前序序列和后序序列。

（1）其前序序列为:＋－＋－θA B C D

（2）其后序序列为:θA－B＋C－D＋

图6－31　例6－8的标识符树

图6－32　例6－9的标识符树

图6－33　例6－10的标识符树

【例6－10】　画出表达式（A＋（B－C））/（（D＋E）＊（F＋G－H）的标识符树（见图6－33）,并求它的前序序列和后序序列。

（1）其前序序列为:/＋A－B C＊＋D E－＋F G H

（2）其后序序列为:A B C－＋D E＋F G＋H－＊/

从上面的几个例子可知,只要将算术表达式用标识符树来表示,然后再求出它的后序遍历的序列,就能方便地得到原表达式的后缀表达式,这一结果和利用堆栈求得的后缀表达式的结果是完全一致的。

同样的道理,对该二叉树进行先序遍历和中序遍历,可以得到表达式的前缀表达式和中缀表达式。其中,中缀表达式就是通常使用的算术表达式,前缀表达式和后缀表达式分别称为波兰式和逆波兰式,它们在编译程序中有着非常重要的作用。