万丈高楼平地起，正所谓地基打得好，百年不会倒。

计算机程序如同高楼的建造，也是要先打好地基，再一层层往上盖。

程序是由数据结构和算法组成的，核心是数据结构和算法。

本篇我们要总结的，是二叉树这种数据结构的遍历方式，提供一些基本的模板，以便随时查阅与套用，快速的搭建程序。

二叉树的4种遍历方式，包括3种深度优先搜索（DFS）和1种广度优先搜索（BFS）。

深度优先搜索（DFS）

递归版本

前序遍历

递归思路：先访问根节点，然后递归遍历左子树，最后递归遍历右子树。

终止条件：节点为空。

/**
 * 前序遍历（递归模板）
 * 
 * @param node
 */
public void preOrder(BinaryNode<T> node) {
    if (node == null) {
        return;
    }
    System.out.print(node.element); // 访问节点，主逻辑处理
    preOrder(node.leftChild);
    preOrder(node.rightChild);
}

中序遍历

递归思路：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。

终止条件：节点为空。

/**
 * 中序遍历（递归模板）
 * 
 * @param node
 */
public void inOrder(BinaryNode<T> node) {
    if (node == null) {
        return;
    }
    inOrder(node.leftChild);
    System.out.print(node.element); // 访问节点，主逻辑处理
    inOrder(node.rightChild);
}

后序遍历

递归思路：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。

终止条件：节点为空。

/**
 * 后序遍历（递归模板）
 * 
 * @param node
 */
public void postOrder(BinaryNode<T> node) {
    if (node == null) {
        return;
    }
    postOrder(node.leftChild);
    postOrder(node.rightChild);
    System.out.print(node.element); // 访问节点，主逻辑处理
}

小结

二叉树的3种递归遍历方式，逻辑简单清晰。

在时间和空间复杂度上都是一样的：

1. 时间复杂度：O(N)。其中N为节点的数量，每个节点需要访问1次.
2. 空间复杂度：取决于保存调用栈的深度。最好是O(logN)，平衡树；最坏是O(N)，链表。 实际应用中，一般都会使用稳定的平衡树，如红黑树和AVL树。

迭代版本

对于二叉树的迭代版本，主要是借助一个栈，来模拟递归的函数调用栈，实现节点的入栈和出栈。

前序遍历

/**
 * 前序遍历（迭代模板）.
 * 
 * @param root
 */
public void preOrder(BinaryNode<T> root) {
    if (root == null) {
        return;
    }

    // 创建一个栈，用于存储待遍历的节点
    LinkedList<BinaryNode<T>> nodeStack = new LinkedList<>();
    nodeStack.push(root);

    while (!nodeStack.isEmpty()) {
        // 1.节点出栈，访问节点，主逻辑处理
        BinaryNode<T> current = nodeStack.pop();
        System.out.print(current.element);

        // 2.右孩子节点入栈
        if (current.rightChild != null) {
            nodeStack.push(current.rightChild);
        }

        // 3.左孩子节点入栈
        if (current.leftChild != null) {
            nodeStack.push(current.leftChild);
        }
    }
}

中序遍历

/**
 * 中序遍历（迭代模板）.
 * 
 * @param root
 */
public void inOrder(BinaryNode<T> root) {
    if (root == null) {
        return;
    }

    // 创建一个栈，用于存储待遍历的节点
    LinkedList<BinaryNode<T>> nodeStack = new LinkedList<>();

    while (root != null || !nodeStack.isEmpty()) {
        // 1.先将自己入栈，然后左孩子节点循环入栈. 后进先出，左孩子节点优先访问.
        while (root != null) {
            nodeStack.push(root);
            root = root.leftChild;
        }

        // 2.节点出栈，访问节点，主逻辑处理
        BinaryNode<T> current = nodeStack.pop();
        System.out.print(current.element);

        // 3.右孩子节点作为下一个待遍历的子树根节点
        root = current.rightChild;
    }
}

后序遍历

迭代版本1

借助一个列表，按照前序遍历的方式访问节点后存储结果。最后，再逆序访问节点，完成后序的遍历过程。

核心遍历逻辑与上面前序遍历的差异点是，对左右孩子节点的入栈顺序颠倒一下。

/**
 * 后序遍历（迭代模板1）.
 * 
 * @param node
 */
public void postOrder(BinaryNode<T> root) {
    if (root == null) {
        return;
    }

    // 存放遍历的结果，按"前序遍历"的结果进行存储
    List<T> resultList = new ArrayList<>();

    // 创建一个栈，用于存储待遍历的节点
    LinkedList<BinaryNode<T>> nodeStack = new LinkedList<>();
    nodeStack.push(root);

    while (!nodeStack.isEmpty()) {
        // 1.节点出栈，保存节点值
        BinaryNode<T> current = nodeStack.pop();
        resultList.add(current.element);

        // 2.左孩子节点入栈
        if (current.leftChild != null) {
            nodeStack.push(current.leftChild);
        }

        // 1.右孩子节点入栈
        if (current.rightChild != null) {
            nodeStack.push(current.rightChild);
        }
    }

    // 访问节点，主逻辑处理
    for (int i = resultList.size() - 1; i >= 0; i--) {
        System.out.print(resultList.get(i));
    }
}

迭代版本2

这个版本不需要借助列表存储遍历结果，但逻辑显得很复杂。

/**
 * 后序遍历（迭代模板2）.
 * 
 * @param node
 */
public void postOrder2(BinaryNode<T> root) {
    if (root == null) {
        return;
    }

    // 创建一个栈，用于存储待遍历的节点
    LinkedList<BinaryNode<T>> nodeStack = new LinkedList<>();

    BinaryNode<T> lastVisit = null;

    while (root != null || !nodeStack.isEmpty()) {
        // 1.先将自己入栈，然后左孩子节点循环入栈. 后进先出，左孩子节点优先访问.
        while (root != null) {
            nodeStack.push(root);
            root = root.leftChild;
        }

        // 2.检查最左侧的节点，符合条件则访问节点
        // 1）如果无右孩子节点，说明无子节点，则访问节点；
        // 2）如果是上次访问节点的父节点，则访问节点。
        BinaryNode<T> current = nodeStack.peek();
        if (current.rightChild == null || current.rightChild == lastVisit) {
            nodeStack.pop();
            System.out.print(current.element); // 主逻辑处理

            // 保存最后一次访问的节点
            lastVisit = current;
            // 下一次直接处理栈顶节点
            root = null;
        // 3.右孩子节点作为下一个待遍历的子树根节点
        } else {
            root = current.rightChild;
        }
    }
}

广度优先遍历（BFS）

迭代版本

节点的访问过程如下：

1. 访问根节点；
2. 访问根节点的左孩子节点left和右孩子节点right；
3. 访问左孩子节点left的左右孩子节点，再访问右孩子节点right的左右孩子节点；
4. …

/**
 * 广度优先遍历（迭代模板）. 从根到叶子节点，层次遍历.
 * 
 * @param root
 */
public void bfs(BinaryNode<T> root) {
    if (root == null) {
        return;
    }

    // 创建一个队列，用于存储待遍历的节点
    LinkedList<BinaryNode<T>> nodeQueue = new LinkedList<>();
    nodeQueue.add(root);

    while (!nodeQueue.isEmpty()) {
        // 1.节点出列，访问节点，主逻辑处理
        BinaryNode<T> current = nodeQueue.poll();
        System.out.print(current.element);

        // 2.左孩子节点入列
        if (current.leftChild != null) {
            nodeQueue.add(current.leftChild);
        }

        // 3.右孩子节点入列
        if (current.rightChild != null) {
            nodeQueue.add(current.rightChild);
        }
    }
}

小结

二叉树的迭代遍历方式，在实现上显得略微复杂，特别是后序遍历的第2个迭代版本的实现。

时间复杂度上和递归版本一样，都是O(N)。

空间复杂度主要取决于树的形状，可能是O(1)、O(logN)或O(N)。

---

---转载本站文章请注明作者和出处 二进制之路（binarylife.icu），请勿用于任何商业用途---