二叉树的遍历 (25 分)
二叉树是一种常见的数据结构，其应用十分广泛。在二叉树中，每个节点最多只有两个子节点，分别称为左子节点和右子节点。其中，左子节点比右子节点小的称为左子树，右子节点比左子节点小的称为右子树。因此，在对二叉树进行遍历时，需要注意遍历顺序，可以根据遍历顺序将其分为前序遍历、中序遍历和后序遍历。
1. 前序遍历
前序遍历又称为先序遍历，是指先遍历根节点，然后按照左子树、右子树的顺序递归遍历子节点。具体实现方式为：
```
void preOrder(TreeNode root) {
if (root == null) return;
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
```
2. 中序遍历
中序遍历是指先递归遍历左子树，然后遍历根节点，最后递归遍历右子树。具体实现方式为：
```
void inOrder(TreeNode root) {
if (root == null) return;
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
```
3. 后序遍历
后序遍历是指先递归遍历左子树和右子树，最后遍历根节点。具体实现方式为：
```
void postOrder(TreeNode root) {
if (root == null) return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
```
以上三个遍历方式分别适用于不同的场景。例如，在前序遍历中，根节点是第一个被输出的，可以用于构建二叉树；而在中序遍历中，二叉树的所有节点按照从小到大的顺序输出，可以用于寻找某个节点。在实际应用中，可以根据具体需求选择不同的遍历方式。
除了三种遍历方式外，还有一些其他的遍历方法。如层序遍历，是指按照从上到下、从左到右的顺序遍历二叉树的每一个节点，具体实现方式为：
```
void levelOrder(TreeNode root) {
if (root == null) return;
Queue
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);
}
}
```
在实际应用中，可能还涉及到二叉树的构建、查找、删除等操作。这些操作都需要对二叉树进行遍历，因此二叉树遍历是非常重要的基础知识。
