数据结构——二叉树的遍历

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

二叉树的遍历方式有很多，主要分为以下三种：

1.二叉前序遍历

规则：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。

注意这里的定义也采用了递归的方式，那么我们如果去理解呢，我们先看一个简单的例子：

这是一个最简单的二叉树，我们按照前序遍历的原则，先根结点-A，再左子树-B，再右子树-C。

所以这棵二叉树的前序遍历为ABC。

这是在二叉树的左右子树都是叶子结点的情况下，我们再来看一个复杂一些的情况：

如图：这里根结点A的左右子树分别是一个二叉树，那么我们可以把左子树和右子树分别当成一个整体T1和T2。

那么按照上文的分析，二叉树的前序遍历为A T1 T2，我们再对T1和T2分别进行前序遍历：

• 按照上文的分析，二叉树的前序遍历为A T1 T2；
• 我们再分别对T1和T2进行前序遍历，T1的前序遍历为BDE, T2的前序遍历为CFG；
• 我们将T1和T2的前序遍历替换到第一步，二叉树的前序遍历为ABDECFG。

对于更复杂的例子，我们都可以通过上面的步骤来完成前序遍历：

前序遍历算法如下，采用递归：

    private void preOrderTraverse(BiNode biNode) {
        if (biNode == null) {
            return;
        }
        //前序遍历输出结点
        LogUtil.d(TAG, biNode.data.toString());
        preOrderTraverse(biNode.leftChild);
        preOrderTraverse(biNode.rightChild);
    }

2.二叉中序遍历

规则：若二叉树为空，则空操作返回，否则先中序遍历左子树，然后访问根结点，最后中序遍历右子树。

同样此处定义也采用了递归形式，有了前序遍历的分析，我们可以用同样的思路来对图2中序遍历：

• 二叉树的中序遍历为T1 A T2；
• 我们再分别对T1和T2进行中序遍历，T1的中序遍历为DBE, T2的中序遍历为FCG；
• 我们将T1和T2的中序遍历替换到第一步，二叉树的中序遍历为DBEAFCG。

再来看一个复杂的例子：

中序遍历算法：

   private void inOrderTraverse(BiNode biNode) {
        if (biNode == null) {
            return;
        }

        inOrderTraverse(biNode.leftChild);
        //中序遍历输出结点
        LogUtil.d(TAG, biNode.data.toString());
        inOrderTraverse(biNode.rightChild);
    }

3.二叉后序遍历

规则：若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。

同样我们采用整理拆分的思路：

• 二叉树的后序遍历为T1 T2 A；
• 我们再分别对T1和T2进行后序遍历，T1的后序遍历为DEB, T2的后序遍历为FGC；
• 我们将T1和T2的前序遍历替换到第一步，二叉树的前序遍历为DEBFCGA。

对于复杂的二叉树也一样：

后序遍历算法：

private void postOrderTraverse(BiNode biNode) {
        if (biNode == null) {
            return;
        }
        postOrderTraverse(biNode.leftChild);
        postOrderTraverse(biNode.rightChild);
        //后序遍历输出结点
        LogUtil.d(TAG, biNode.data.toString());

    }

二叉树的遍历算法，由于定义中采用了递归，所以理解起来比较抽象，采用先整体后拆分的方法，可以帮助对二叉树遍历的理解。

————————————————————————————————————

文末推荐个人开发的app，Google Play : 数据结构与算法教程 （需要*）

    

提供了丰富的动画演示、模拟场景来帮助你更好的理解抽象的数据结构和复杂的算法。（文中的动图都是从app中截取的片段）