一篇总结二叉树的4种遍历方式(含模板)

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

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

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

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

二叉树的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的左右孩子节点;
/**
 * 广度优先遍历(迭代模板). 从根到叶子节点,层次遍历.
 * 
 * @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),请勿用于任何商业用途---

留下评论