二叉树算法之二叉树遍历（前序、中序、后序、层次遍历）
二叉树遍历是指按照某种顺序访问二叉树的所有节点。常见的二叉树遍历方式包括前序遍历（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）：按层次顺序遍历，常用于广度优先搜索。
这些遍历方式各有特点，应用于不同的场景。
原文地址：https://blog.csdn.net/m0_61840987/article/details/142986551
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！