红黑树00——前传-树的构建与遍历.md

1. 树的遍历方式

树的遍历是指访问树节点的数据（可以是打印，也可以是做其他的事情）。树的遍历有广度优先与深度优先两大类。

1. 广度优先：先处理同一层的兄弟结点（增加宽度），再处理子结点。广度优先遍历又叫层序遍历，是从上往下从左到右的遍历方式。
2. 深度优先：先处理子结点（增加深度），再处理同级的兄弟结点。另外，深度优先遍历，根据被遍历结点与其左右子结点的位置，分为三种情况：
   • 先序遍历（pre-order）：[DLR]( data, left, right )，先访问结点数据，再递归遍历左子树，然后递归遍历右子树；
   • 中序遍历（in-order）：[LDR]( left, data, right )，先递归遍历左子树，再访问结点数据，然后递归遍历右子树；
   • 后序遍历（post-order）：[LRD]( left, right, data )，先递归遍历左子树，再递归遍历右子树，最后访问结点数据。

注意：刚学习的时候很容易忘记递归，经常遍历左结点之后立马就回去了，这样会遍历不全。记住，我们是深度优先，只要当前遍历的结点不为null，就继续往下处理子结点，直到遇到null再回归。

1.1 怎样牢记三种遍历方式

• 先左后右——LR：左右子树顺序固定不变。
• x1-L-x2-R-x3，显然看得出，我们可以在x1, x2, x3的任意一个位置上遍历结点本身。在最前边就叫前序遍历，在中间的叫中序遍历，在最后的叫后序遍历。

1.2 遍历示例

图1-遍历示例

我们分别用不同的遍历方式遍历上图二叉树，结果为：

• 层序遍历：3-1-5-2-4；
• 先序遍历：3-1-2-5-4；
• 中序遍历：1-2-3-4-5；
• 后序遍历：2-1-4-5-3.

2. 代码实现

2.1 层序遍历

层序遍历的思路挺有用的，希望大家能熟记，之后在别的地方会用到。

在层序遍历中，当我们遍历完某一层的最后一个结点后，接下来要遍历下一层的第一个结点（假设存在），但这两个结点之间没有一点关系，没有任何连接，怎样才能从上一层的最后一个跳到下一层的第一个呢？

答案是：我们需要借助一种数据结构——队列。我们可以在遍历上一层的每个结点的时候，把该结点的子结点放入队列中，当上一层处理完之后，再从队列里面取出结点就是下一层的结点，且是从左到右的顺序。利用队列先进先出的特性，能保证遍历顺序的正确性。根结点比较特殊，直接入队列即可。

    // 遍历：可以对node做任何你想做的事情，这里我们仅仅打印。
    private void doSomethingWithNode(Node node) {
        System.out.printf("%s\t", node.data);
    }

    // 层序遍历（广度优先遍历）
    public void layerTraversal() {
        if (root == null) {
            return;
        }
        // 这里用到自己实现的队列（我会在其他的文章里面详解队列的原理与实现），你可以换成系统自带的。
        LinkQueue<Node> queue = new LinkQueue<>();
        queue.enqueue(root);
        while (!queue.isEmpty()) {
            Node node = queue.dequeue();
            doSomethingWithNode(node);
            if (node.left != null) {
                queue.enqueue(node.left);
            }
            if (node.right != null) {
                queue.enqueue(node.right);
            }
        }
    }

2.2 深度优先遍历

我们这里用递归的方式实现，递归出口是node == null。另外，递归都可以转化为非递归，我会单独详细讲述递归与非递归之间的相互转换，这里不再进一步叙述。

核心代码就3行，2行递归调用，一行遍历操作(代码中的doSomethingWithNode)。doSomethingWithNode在最上面，就是先序遍历，在中间就是中序遍历，在最后就是后序遍历。

    // 先序遍历
    private void preOrder(Node node) {
        if (node == null) {
            return;
        }
        doSomethingWithNode(node);
        preOrder(node.left);
        preOrder(node.right);
    }

    // 中序遍历
    private void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        doSomethingWithNode(node);
        inOrder(node.right);
    }

    // 后序遍历
    private void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        doSomethingWithNode(node);
    }

3. 根据遍历结果把树还原

我们可以根据：中序遍历 + 任意一种其他的遍历，来还原一棵树。拿简单点的中序遍历 + 层序遍历举例：

图1-遍历示例

层序遍历：3-1-5-2-4；中序遍历：1-2-3-4-5。接下来的叙述统一用层序x来表示层序遍历x结点，中序也一样。层序3说明根结点为3，层序1和5表示第2层（即根3的左右孩子）分别为1和5；层序2和4说明2和4在第3层，但无法确定位置，我们再看中序，中序1在2之前，表示2为1的父结点（不可能，因为2在1的下面）或2为1的右结点，所以2为1的右结点。同理，得出4为5的左结点。

4. 遍历的应用

• 前序遍历：1. 打印目录树。 // TODO
• 中序遍历：1. 排序数的顺序输出。// TODO
• 后序遍历：1. 计算目录内的文件大小。 // TODO

源码

https://github.com/readyou/algorithm-introduction-code/blob/master/src/main/java/me/wxl/demo/data/struct/BinaryTree.java

作者微信

wx.png

转载声明

如果您需要转载，请注明转载来源。