二叉树遍历是指按照某种顺序访问二叉树的所有节点。常见的二叉树遍历方式包括前序遍历（Preorder Traversal）、中序遍历（Inorder Traversal）、后序遍历（Postorder Traversal）和层次遍历（Level-order Traversal）。不同的遍历方式有不同的应用场景，下面我们详细介绍这几种遍历方式及其实现。
1. 前序遍历（Preorder Traversal）
在前序遍历中，按照“根节点 -> 左子树 -> 右子树”的顺序遍历二叉树的节点。即：首先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。
前序遍历的顺序：
当前节点 -> 左子节点 -> 右子节点
前序遍历的递归实现：
// 定义二叉树节点
class TreeNode {int val;TreeNode left, right;TreeNode(int val) {this.val = val;this.left = this.right = null;}
}public class BinaryTreeTraversal {// 前序遍历 - 递归实现public void preorder(TreeNode root) {if (root == null) {return;}System.out.print(root.val + " "); // 访问根节点preorder(root.left); // 递归遍历左子树preorder(root.right); // 递归遍历右子树}
}
前序遍历的非递归实现：
可以用栈模拟递归的过程，先访问根节点，然后将右子树和左子树依次压栈，确保左子树先被遍历。
import java.util.Stack;public class BinaryTreeTraversal {// 前序遍历 - 非递归实现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. 中序遍历（Inorder Traversal）
在中序遍历中，按照“左子树 -> 根节点 -> 右子树”的顺序遍历二叉树的节点。即：首先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。
中序遍历的顺序：
左子节点 -> 当前节点 -> 右子节点
中序遍历的递归实现：
public class BinaryTreeTraversal {// 中序遍历 - 递归实现public void inorder(TreeNode root) {if (root == null) {return;}inorder(root.left); // 递归遍历左子树System.out.print(root.val + " "); // 访问根节点inorder(root.right); // 递归遍历右子树}
}
中序遍历的非递归实现：
同样可以使用栈来实现，先遍历到最左边的节点，然后逐步回溯访问根节点，最后遍历右子树。
import java.util.Stack;public class BinaryTreeTraversal {// 中序遍历 - 非递归实现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. 后序遍历（Postorder Traversal）
在后序遍历中，按照“左子树 -> 右子树 -> 根节点”的顺序遍历二叉树的节点。即：首先递归地遍历左子树，然后递归地遍历右子树，最后访问根节点。
后序遍历的顺序：
左子节点 -> 右子节点 -> 当前节点
后序遍历的递归实现：
public class BinaryTreeTraversal {// 后序遍历 - 递归实现public void postorder(TreeNode root) {if (root == null) {return;}postorder(root.left); // 递归遍历左子树postorder(root.right); // 递归遍历右子树System.out.print(root.val + " "); // 访问根节点}
}
后序遍历的非递归实现：
后序遍历较复杂，需要两个栈，一个用于模拟递归，另一个用于输出结果。
import java.util.Stack;public class BinaryTreeTraversal {// 后序遍历 - 非递归实现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 + " "); // 输出结果}}
}
4. 层次遍历（Level-order Traversal）
层次遍历是按照每一层节点的顺序从上到下，从左到右依次遍历二叉树的节点。可以通过队列实现，每次从队列中取出一个节点，然后将其左右子节点依次加入队列。
层次遍历的顺序：
按照从上到下、从左到右的层次顺序遍历节点
层次遍历的实现：
import java.util.LinkedList;
import java.util.Queue;public class BinaryTreeTraversal {// 层次遍历 - 使用队列实现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); // 右子节点入队}}}
}
四种遍历的总结
- 前序遍历（Preorder Traversal）：根 -> 左 -> 右，通常用于复制树。
- 中序遍历（Inorder Traversal）：左 -> 根 -> 右，通常用于输出升序排序（对二叉搜索树）。
- 后序遍历（Postorder Traversal）：左 -> 右 -> 根，通常用于删除树或者计算子树的大小。
- 层次遍历（Level-order Traversal）：按层次顺序遍历，常用于广度优先搜索。
这些遍历方式各有特点，应用于不同的场景。