第 5 节 二分搜索树的第 3 个操作：深度优先遍历

• 二分搜索树的遍历，其实就是挨个把二分搜索树中的元素拿出来，只不过二分搜索树不像数组或者链表那样，有明显的“从头到尾”的性质。但其实走完一个二分搜索树也是有规律可循的，其中一种方式就是深度优先遍历。
• 深度优先遍历的顺序是下面这张图展示的样子。首先尝试走到最深，再回退，再走到另一个分支的最深。

那么什么是二分搜索树的前序、中序、后序遍历呢？

• 把握要点：通过对深度优先遍历的遍历路径，我么可以看出，深度优先遍历走完一棵二叉树，每个结点会被访问 3 次，分别对应左边、中间和右边，那么在什么位置进行输出，就对应了深度优先遍历的这三种遍历方式：前序遍历，在访问左边位置的时候，进行操作；中序遍历，在访问中间位置的时候，进行操作；后序遍历，在访问右边位置的时候，进行操作；。
• 使用递归的方式实现的代码编写是异常简单的！下面的图表多看几遍就明白了，千万不要忘记了对 node 是否为 null 的判断。下面用递归的方式编写前、中、后序遍历是十分简单的。它们的结构是完全相同的。

• 后序遍历与空间释放

可以看到，红色标注的部分是结构一致的。

• 记忆要点：左右子树都是递归处理，树根是真正要执行的操作。后序遍历的一个重要特点：前序和后序都访问完以后，才做操作。
• 中序遍历的重要结论：中序遍历可以将数据按照从小到大升序排列。
• 后序遍历的重要结论：后续遍历在空间释放的时候可以先释放左右结点，再释放自身。

// 二分搜索树的前序遍历
public void preOrder() {
    preOrder(root);
}

private void preOrder(Node node) {
    if (node != null) {
        System.out.printf("%s ", node.value);
        preOrder(node.left);
        preOrder(node.right);
    }
}

// 二分搜索树的中序遍历
public void inOrder() {
    inOrder(root);
}

private void inOrder(Node node) {
    if (node != null) {
        inOrder(node.left);
        System.out.printf("%s ", node.value);
        inOrder(node.right);
    }
}

// 二分搜索树的后序遍历
public void postOrder() {
    postOrder(root);
}

private void postOrder(Node node) {
    if (node != null) {
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.value);

    }
}

• 补充知识：使用非递归的方法完成二分搜索树的三种深度优先遍历。

---

作者：liweiwei1419 链接：https://suanfa8.com/binary-search-tree/dfs 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。