数据结构与算法 / 系统课时

二叉树遍历

二叉树遍历

二叉树遍历解决的是“按照什么顺序访问每个节点”的问题。本课将用同一棵树对比前序、中序、后序和层序遍历,并分别实现递归与迭代版本,使你能够根据任务需要选择合适的访问顺序。

学习目标

  • 准确判断四种遍历的节点访问顺序。
  • 理解递归调用栈与显式栈、队列之间的对应关系。
  • 使用 Java 编写并验证完整的二叉树遍历程序。

深度优先与广度优先的关系

text
二叉树遍历
├── 深度优先遍历
│   ├── 前序:根 → 左 → 右
│   ├── 中序:左 → 根 → 右
│   └── 后序:左 → 右 → 根
└── 广度优先遍历
    └── 层序:按层从左到右

二叉树四种遍历顺序示意

为目录任务选择访问顺序

遍历是多数树算法的基础。复制目录结构常用前序遍历,因为要先处理父节点;计算目录占用空间常用后序遍历,因为要先汇总子节点;二叉搜索树按中序遍历会得到有序序列;按层打印树、计算最短层数或执行广度优先搜索则需要层序遍历。

四种遍历都会访问每个节点一次,差异不在“是否访问”,而在“何时处理根节点”以及使用什么辅助结构。理解这一点后,递归和迭代实现就不再是互不相关的代码模板。

什么时候访问根节点

以前序、中序和后序为代表的深度优先遍历,会沿一条分支尽量向下,再回退处理其他分支。递归版本由 JVM 调用栈保存返回位置;迭代版本则显式使用 Deque<Node> 保存尚未处理的节点。

遍历方式 访问顺序 典型用途 额外空间
前序 根、左、右 复制树结构、序列化 O(h)O(h)
中序 左、根、右 输出二叉搜索树有序结果 O(h)O(h)
后序 左、右、根 删除树、汇总子树结果 递归 O(h)O(h),下方两栈实现 O(n)O(n)
层序 从上到下、每层从左到右 最短层数、按层处理 O(w)O(w)

其中,hh 是树高,ww 是树的最大宽度。非空树的访问时间为 Θ(n)。表中辅助空间不含保存全部节点的返回列表,返回列表另需 Θ(n)。按边数计高度时,n 节点单链树的高度为 n−1,深度优先逻辑栈为 O(h+1)。层序队列可同时含当前层剩余节点和下一层已入队节点,峰值不超过 2w,且处理完上一层时会出现一整层,因此为 Θ(w)。

调用栈如何映射到容器

递归遍历的关键是把“处理根节点”的语句放在不同位置:前序放在递归左子树之前,中序放在左右子树之间,后序放在递归右子树之后。

迭代前序需要先压入右孩子、再压入左孩子,因为栈是后进先出;迭代中序要持续压入左链,栈顶节点弹出后再转向其右子树;迭代后序可以使用两个栈,第一栈产生“根、右、左”顺序,再由第二栈反转成“左、右、根”;层序遍历使用队列,节点出队时将左右孩子依次入队。

空树返回空结果。示例要求输入为有效二叉树,每个非根节点只由一处孩子引用到达,且无环。遍历期间应保持结构不变。

Java 对照实现

将以下代码保存为 BinaryTreeTraversalDemo.java。程序对同一棵树执行递归前序、中序、后序,以及对应的迭代实现和层序遍历。

java
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class BinaryTreeTraversalDemo {

    static class Node {
        final int value;
        Node left;
        Node right;

        Node(int value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        Node root = buildTree();

        System.out.println("递归前序: " + preorderRecursive(root));
        System.out.println("迭代前序: " + preorderIterative(root));
        System.out.println("递归中序: " + inorderRecursive(root));
        System.out.println("迭代中序: " + inorderIterative(root));
        System.out.println("递归后序: " + postorderRecursive(root));
        System.out.println("迭代后序: " + postorderIterative(root));
        System.out.println("层序遍历: " + levelOrder(root));
    }

    private static Node buildTree() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.right = new Node(6);
        return root;
    }

    static List<Integer> preorderRecursive(Node root) {
        List<Integer> result = new ArrayList<>();
        preorder(root, result);
        return result;
    }

    private static void preorder(Node node, List<Integer> result) {
        if (node == null) {
            return;
        }
        result.add(node.value);
        preorder(node.left, result);
        preorder(node.right, result);
    }

    static List<Integer> inorderRecursive(Node root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }

    private static void inorder(Node node, List<Integer> result) {
        if (node == null) {
            return;
        }
        inorder(node.left, result);
        result.add(node.value);
        inorder(node.right, result);
    }

    static List<Integer> postorderRecursive(Node root) {
        List<Integer> result = new ArrayList<>();
        postorder(root, result);
        return result;
    }

    private static void postorder(Node node, List<Integer> result) {
        if (node == null) {
            return;
        }
        postorder(node.left, result);
        postorder(node.right, result);
        result.add(node.value);
    }

    static List<Integer> preorderIterative(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Deque<Node> stack = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            result.add(node.value);

            // 先压右孩子,保证左孩子先出栈。
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return result;
    }

    static List<Integer> inorderIterative(Node root) {
        List<Integer> result = new ArrayList<>();
        Deque<Node> stack = new ArrayDeque<>();
        Node current = root;

        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            current = stack.pop();
            result.add(current.value);
            current = current.right;
        }
        return result;
    }

    static List<Integer> postorderIterative(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Deque<Node> first = new ArrayDeque<>();
        Deque<Node> second = new ArrayDeque<>();
        first.push(root);

        while (!first.isEmpty()) {
            Node node = first.pop();
            second.push(node);

            // 第二个栈反转访问顺序,最终得到左、右、根。
            if (node.left != null) {
                first.push(node.left);
            }
            if (node.right != null) {
                first.push(node.right);
            }
        }

        while (!second.isEmpty()) {
            result.add(second.pop().value);
        }
        return result;
    }

    static List<Integer> levelOrder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Deque<Node> queue = new ArrayDeque<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            result.add(node.value);

            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return result;
    }
}

运行命令:

bash
javac -encoding UTF-8 BinaryTreeTraversalDemo.java
java BinaryTreeTraversalDemo

比较递归和迭代的输出

text
递归前序: [1, 2, 4, 5, 3, 6]
迭代前序: [1, 2, 4, 5, 3, 6]
递归中序: [4, 2, 5, 1, 3, 6]
迭代中序: [4, 2, 5, 1, 3, 6]
递归后序: [4, 5, 2, 6, 3, 1]
迭代后序: [4, 5, 2, 6, 3, 1]
层序遍历: [1, 2, 3, 4, 5, 6]

递归与迭代版本输出一致,说明两种实现遵守了相同的访问规则。实际执行环境中的 Java 版本提示可能不同,但上述程序输出内容和顺序不变。

两栈后序的空间代价

两栈实现的第二个栈会收集整棵树的节点,即使树高很小,栈仍可能保存 n 个节点。因此该实现的额外空间为 O(n),不含返回列表。递归后序沿当前根到叶路径展开,递归调用栈的空间才是 O(h)。

  • 使用 ArrayDeque 实现显式栈与队列。空节点应在入栈和入队前过滤。
  • 调试遍历顺序时,先画出 5~7 个节点的小树,并在每次处理节点时记录结果列表。
  • 深树可用迭代实现避免递归栈溢出。若结构来自不可信输入,仍需单独检查环、共享节点与资源上限,换成显式栈不会消除这些问题。
  • 只需要消费节点而不需要保存全部结果时,可以把 result.add(...) 替换为业务处理函数,降低额外内存占用。

识别漏访和顺序错误

前序迭代中若先压左孩子再压右孩子,右孩子会先出栈,结果将变成“根、右、左”。修复方法是牢记栈的后进先出特性,按“右后处理、先压入;左先处理、后压入”的顺序操作。

中序迭代常见问题是只判断 current != null,当左链走到末尾后循环会提前结束。正确条件是 current != null || !stack.isEmpty(),这样才能继续弹出祖先节点并访问右子树。

层序遍历若用栈代替队列,会退化成深度优先访问。应使用 offer 入队、poll 出队,并保持左孩子先于右孩子入队。

用空树、链形树和非对称树验证

  1. 修改示例,使层序遍历按二维列表返回每一层,例如 [[1], [2, 3], [4, 5, 6]]。验收条件是层数、每层节点数量和从左到右顺序都正确。
  2. 使用单个栈实现后序遍历,不得使用第二个栈。可以增加 lastVisited 指针,验收条件是输出仍为 [4, 5, 2, 6, 3, 1]。
  3. 为四种遍历补充空树和只有一个节点的测试。验收条件是空树返回空列表,单节点树四种结果都只包含该节点。

按访问时机复核遍历

  • 深度优先遍历的差异取决于根节点在左、右子树处理过程中的位置。
  • 递归调用栈可以被显式栈替代,层序遍历则依赖先进先出的队列。
  • 四种遍历时间均为 Θ(n)。空间要分开记输出与工作容器,两栈后序单独占线性空间。

从遍历过渡到搜索

下一课将学习“二叉搜索树查找”,利用左子树较小、右子树较大的有序不变式,把遍历范围从整棵树缩小到一条搜索路径。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

二叉树遍历

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通