开始前的一些碎碎念

仔细算算，距离我搭建好这个博客已经有进一个月了。

但。。。。？

为什么我还是一篇博文也写不出来！？

明明我也是有个博主梦的好嘛？

img

果然这样下去还是不行的，要不用技术贴来水水博客好了。

img

说干就干！正好最近在学习二叉树，这次就来聊聊自己对先序遍历 (pre-order) 、中序遍历 (in-order) 和后序遍历 (post-order) 的理解吧！

二叉树的结构

若要谈三种遍历方式，必定逃不过二叉树本身。先放上二叉树的解释。

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

一棵深度为k，且有2^k-1个结点的二叉树，称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树。具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子结点，至多有2k-1个结点。

来源：百度百科

我们可以看到，二叉树确实非常非常有用(￣▽￣)~*，而二叉树的结构其实也就是：

  • 每个节点最多只能有两个子节点
  • 整棵树从根节点（root node）出发，到无元素存储的外部节点（external node）结束。

先序（pre-order）、中序（in-order）和后序（post-order）

一、先序（pre-order）

那么，介绍完二叉树的结构之后问题就来了，什么是先序遍历呢？

当我们去搜索一棵二叉树上所有元素的时候，我们难免需要遵守一种规律。而先序遍历的规则是这样的：

  1. 首先，我们会去问候根节点，这个时候我们就可以对这个节点干些想干的事情了⁄(⁄⁄•⁄ω⁄•⁄⁄)⁄

  2. 之后呢，我们会按顺序干以下两件事

    a) 问候这个节点的左子节点，并将该节点当成新的根节点，重复步骤1 - 2直到没有新节点可以被访问

    b) 问候这个节点的右子节点，并将该节点当成新的根节点，重复步骤1 - 2直到没有新节点可以被访问

我们可以很明显地看到，这个其实是一个递归过程，而代码是这样的：

private void queryNodePreorder(ITree tree, IPosition nowRoot) {
    /* 这里可以对nowRoot节点干些事情 */
    if (tree.isLeaf(nowRoot)) { // 如果nowRoot是叶节点退出递归
        return;
    } else {
        // 按顺序去访问nowRoot的左右子节点
        queryNodePreorder(tree, tree.getLeftChild(nowRoot)); 
        queryNodePreorder(tree, tree.getRightChild(nowRoot));
    }
}

二、中序（In-order）

其实中序遍历和先序遍历相差无几。下面先给出中序遍历的规则：

  1. 首先，还是要找到根节点，但是不同于先序，我们暂时先不访问它

  2. 之后呢，不同于先序，我们会按顺序干以下四件事

    a) 找到这个节点的左子节点（先不访问），并将该节点当成新的根节点，重复步骤1 - 2直到找到最左的那个子节点

    b) 然后从这个新的节点开始访问，访问完之后访问它的父节点

    c) 父节点之后是父节点的右子节点，同样也是不访问，只是找到它

    d) 再对这个右子节点重复步骤a - c，直到将整棵树操作完

用文字说明有点绕了，还是放上代码吧

private void queryNodeInorder(ITree tree, IPosition nowRoot) {
    if (tree.isLeaf(nowRoot)) { // 如果nowRoot是叶节点退出递归
        return;
    } else {
        // 按顺序去访问nowRoot的左右子节点
        queryNodeInorder(tree, tree.getLeftChild(nowRoot)); 
        /* 不同于先序，我们会在这里对nowRoot节点干事情 */
        queryNodeInorder(tree, tree.getRightChild(nowRoot));
    }
}

三、后序（post-order）

说实话，我现在还不太清楚后序为什么叫（post-order）。。但原理还是很清晰的：

  1. 首先，还是要找到根节点，但是不同于先序，我们暂时先不访问它

  2. 然后我们会按顺序干下面几件事：

    a) 找到左子节点，不访问

    b) 找到该节点的左子节点，并重复此步骤，直到找到叶节点

    c) 访问该叶节点

    d) 访问该叶节点的父节点的右子节点

    e) 将该右子节点当成新的根节点重复操作a - d

    f ) 访问完右子节点后访问根节点

(；´д｀)ゞ这文字写得我都恶心了。。。

还是放上代码吧，简单易懂：

private void queryNodePostorder(ITree tree, IPosition nowRoot) {
    if (tree.isLeaf(nowRoot)) { // 如果nowRoot是叶节点退出递归
        return;
    } else {
        // 按顺序去访问nowRoot的左右子节点
        queryNodePostorder(tree, tree.getLeftChild(nowRoot)); 
        queryNodePostorder(tree, tree.getRightChild(nowRoot));
        /* 在这里对nowRoot节点进行访问 */
    }
}

总结

这篇博文大概就是这样啦，先序、中序和后序，再也不会傻傻分不清楚了ヽ(￣▽￣)ﾉ

下篇博文打算聊聊如何用先序、中序和后序的组合看出原来的二叉树结构，希望自己能坚持下去呀！~

٩꒰▽ ꒱۶⁼³₌₃ 学习去咯