二叉树遍历：先序、中序、后序与层序

"二叉树的遍历方法主要包括先序遍历、中序遍历、后序遍历和层序遍历。这些遍历方式是理解二叉树数据结构的关键，确保每个节点被访问一次且仅被访问一次。在创建二叉树时，通常采用先建左子树再建右子树的方式。以下将详细讨论这四种遍历方法。 首先，二叉树的节点定义如下： ```java public class TreeNode { public int data; public TreeNode leftChild; public TreeNode rightChild; public TreeNode(int data) { this.data = data; } } ``` 创建二叉树的函数如下，它接收一个按顺序排列的整数链表，并从中构建二叉树： ```java public static TreeNode createBinaryTree(LinkedList<Integer> list) { TreeNode node = null; if (list == null || list.isEmpty()) { return null; } Integer data = list.removeFirst(); if (data != null) { node = new TreeNode(data); node.leftChild = createBinaryTree(list); node.rightChild = createBinaryTree(list); } return node; } ``` 接着，我们来分别介绍四种遍历方式： 1. 先序遍历：访问顺序为根 -> 左 -> 右。对于给定的二叉树，先序遍历的结果是：ABDFECGHI。实现代码如下： ```java public static void preOrderTraversal(TreeNode node) { if (node == null) { return; } System.out.print(node.data + ""); preOrderTraversal(node.leftChild); preOrderTraversal(node.rightChild); } ``` 2. 中序遍历：访问顺序为左 -> 根 -> 右。在给定的二叉树中，中序遍历的结果会有所不同。实现代码如下： ```java public static void inOrderTraversal(TreeNode node) { if (node == null) { return; } inOrderTraversal(node.leftChild); System.out.print(node.data + ""); inOrderTraversal(node.rightChild); } ``` 3. 后序遍历：访问顺序为左 -> 右 -> 根。后序遍历的结果同样会根据树的结构而变化。实现代码如下： ```java public static void postOrderTraversal(TreeNode node) { if (node == null) { return; } postOrderTraversal(node.leftChild); postOrderTraversal(node.rightChild); System.out.print(node.data + ""); } ``` 4. 层序遍历：按照从上至下、从左至右的顺序访问每一层的节点。层序遍历通常需要借助队列来实现。例如，如果给定的二叉树是完全平衡的，层序遍历将按照每一层的顺序访问所有节点。实现代码如下： ```java import java.util.LinkedList; import java.util.Queue; public static void levelOrderTraversal(TreeNode node) { Queue<TreeNode> queue = new LinkedList<>(); if (node != null) { queue.offer(node); } while (!queue.isEmpty()) { TreeNode current = queue.poll(); System.out.print(current.data + ""); if (current.leftChild != null) { queue.offer(current.leftChild); } if (current.rightChild != null) { queue.offer(current.rightChild); } } } ``` 通过这四种遍历方法，我们可以对二叉树进行不同的访问，满足不同的需求，如查找、复制或打印特定顺序的节点。了解并掌握这些遍历策略对于理解和操作二叉树至关重要。"