二叉树遍历及其相关特性

本节中，我们把分治技术应用到二叉树中。我们把二叉树定义为若干顶点的一个有限集合，它要么为空，要么由一个根和两棵称为L和R的不相交二叉树构成，它们分别为根的左右子树。如图5.4。

定义本身把二叉树划分为同样类型的两个更小的组成部分——左子树和右子树，因此，许多关于二叉树的问题可以应用分治技术来解决。作为一个例子，我们来考虑一下二叉树高度的递归算法。

树的高度定义为从叶子到根之间的最长路径长度。所以，二叉树的高度可以这样计算，它是根的左，右子树的最大高度加1（加1代表根所在的那一层）。为了方便起见，我们把空树的高度定义为-1.

算法 Height(T)
    //递归计算二叉树的高度
    //输入：一棵二叉树T
    //输出：T的高度
    if T = ∅ return -1
    else return max{Height(TL),Height(TR)}+1

我们以给定的二叉树的顶点数n(T)来度量问题实例的规模。对于A(n(T)),我们有下面的递推关系：

当n(T) > 0时，A(n(T)) = A(n(TL)) + A(n(TR)) + 1,
A(0) = 0

检查树是否为空，这才是二叉树书算法中的典型操作。例如，对于空树来说，执行了一次T=∅的比较运算，但是加法运算一次也没有执行。对于一棵单顶点的树来说，比较运算和加法运算的执行次数分别是三次和一次。

用特殊的顶点代替空子树分析树的算法。特殊的顶点（在图5.5中用小方块表示）被称为外部顶点;原来的顶点（用小圆圈表示）被称为内部顶点.根据定义，一棵扩展的空二叉树是一个单独的外部顶点。

对于扩展树的每一个内部顶点，高度算法都要执行一次加法运算，而且不论对外部顶点还是内部顶点，该算法都要执行一次比较运算以判断它们的子树是否为空。为了确定该算法的效率，我们需要知道一棵包含n个内部顶点的扩展二叉树最多能够具有几个外部顶点。从图4.5很容易看出，外部顶点的数量x都是比内部顶点的数量大一：

x = n+1

我们使用归纳法来证明该等式。当n＝0时，根据定义，一棵空树的确只是一个外部顶点，归纳的第一步时正确的。对于一般情况，我们假设，当任意扩展二叉树具有0≦k≦n个内部顶点时，

x = k+1

设T是一棵具有n个内部顶点和x个外部顶点的扩展二叉树，T的左子树的内部顶点和外部顶点个数分别为nL和xL，T的右子树的内部顶点和外部顶点个数分别为nR和xR。因为n > 0,所以T有一个根，因为根是它的内部顶点，所以n＝nL+nR+1.分别对左右子树应用前面的假设，我们得到下面的等式：

x = xL+xR = (nL+1) + (nR+1) = (nL+nR+1)+1 = n+1

所以假设得证。

回到Height算法，其中，检查树是否为空的比较操作次数为：

C(n) = n+x = 2n+1

而加法操作的次数为：

A(n) = n

这种类型中最重要的例子很可能是二叉树的三种经典遍历算法：前序，中序，后序。这三种遍历算法都递归地访问二叉树的顶点，也就是说，访问二叉树的根，它的左子树和右子树。它们仅仅在访问根的时序上有所不同：

前序遍历,根在访问左右子树（就是先左后右的次序）之前被访问。
中续遍历,根在访问左子树后，访问右子树前被访问。
后续遍历,根在访问左右子树（先左后右的次序）之后被访问。

它们的效率和我们刚才讨论的高度算法的效率其实是一样的，因为对于扩展二叉树的每一个顶点，都需要做一个递归调用。

最后，还要指出，并不是所有二叉树的算法都需要遍历左右两棵 子树。例如，二叉查找树的查找，插入和删除操作只需要遍历两棵子树的一棵。因此，它们不应该作为分治技术的应用，而应该作为减可变规模技术的应用，这个技术我们会在5.6节中讨论。