Java二叉树遍历全攻略：前序/中序/后序+层序遍历实现

admin 2025-06-29 阅读:3 评论:0

在计算机科学中，二叉树是一种非常重要的数据结构，而遍历算法则是操作二叉树的基础。本文将全面讲解Java中二叉树的各种遍历方法，包括递归与非递归实现，并深入分析它们的性能特点和应用场景。一、二叉树基础概念回顾二叉树是由节点组成的层次结构，每...

在计算机科学中，二叉树是一种非常重要的数据结构，而遍历算法则是操作二叉树的基础。本文将全面讲解Java中二叉树的各种遍历方法，包括递归与非递归实现，并深入分析它们的性能特点和应用场景。

一、二叉树基础概念回顾

二叉树是由节点组成的层次结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。在Java中，我们通常这样定义二叉树节点类：

Java二叉树遍历全攻略：前序/中序/后序+层序遍历实现

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

二、深度优先遍历(DFS)的三种方式

1. 前序遍历(Pre-order Traversal)

前序遍历的顺序是：根节点 → 左子树 → 右子树。递归实现如下：

public void preOrder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preOrder(root.left);
    preOrder(root.right);
}

非递归实现使用栈结构：

public void preOrderIterative(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.val + " ");
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
}

2. 中序遍历(In-order Traversal)

中序遍历的顺序是：左子树 → 根节点 → 右子树。递归实现：

public void inOrder(TreeNode root) {
    if (root == null) return;
    inOrder(root.left);
    System.out.print(root.val + " ");
    inOrder(root.right);
}

非递归实现：

public void inOrderIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        System.out.print(curr.val + " ");
        curr = curr.right;
    }
}

3. 后序遍历(Post-order Traversal)

后序遍历的顺序是：左子树 → 右子树 → 根节点。递归实现：

Java二叉树遍历全攻略：前序/中序/后序+层序遍历实现

public void postOrder(TreeNode root) {
    if (root == null) return;
    postOrder(root.left);
    postOrder(root.right);
    System.out.print(root.val + " ");
}

非递归实现较为复杂，需要使用两个栈或记录访问状态：

public void postOrderIterative(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    Stack<TreeNode> output = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        output.push(node);
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    while (!output.isEmpty()) {
        System.out.print(output.pop().val + " ");
    }
}

三、广度优先遍历(BFS)/层序遍历

层序遍历使用队列实现，按层次从上到下、从左到右访问节点：

public void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.val + " ");
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

四、Morris遍历算法

Morris遍历是一种空间复杂度为O(1)的遍历算法，它通过临时修改树的结构来实现遍历：

public void morrisInOrder(TreeNode root) {
    TreeNode curr = root;
    while (curr != null) {
        if (curr.left == null) {
            System.out.print(curr.val + " ");
            curr = curr.right;
        } else {
            TreeNode predecessor = curr.left;
            while (predecessor.right != null && predecessor.right != curr) {
                predecessor = predecessor.right;
            }
            if (predecessor.right == null) {
                predecessor.right = curr;
                curr = curr.left;
            } else {
                predecessor.right = null;
                System.out.print(curr.val + " ");
                curr = curr.right;
            }
        }
    }
}