Day 4：树的基础（二叉树遍历）

---

 一、什么是树？

树（Tree）是一种 层次结构 的数据结构，它由节点（Node）组成，每个节点可以有 多个子节点。树的应用非常广泛，如：

• 文件系统
• 数据库索引
• 二叉搜索树（BST）
• 网络路由树

---

 二、二叉树（Binary Tree）基础

 1. 什么是二叉树？

二叉树是一种特殊的树形结构，每个节点最多有两个子节点：

• 左子节点（Left Child）
• 右子节点（Right Child）

 2. 二叉树的基本概念

• 根节点（Root）：二叉树的顶层节点
• 叶子节点（Leaf）：没有子节点的节点
• 父节点（Parent）：拥有子节点的节点
• 子节点（Children）：属于某个父节点的节点
• 高度（Height）：从叶子节点到根节点的最长路径长度
• 深度（Depth）：某个节点到根节点的路径长度

示例二叉树：

       1

      / \

     2   3

    / \   \

   4   5   6

---

 三、二叉树的遍历

二叉树遍历有 两大类：

1. 深度优先遍历（DFS） 
   • 前序遍历（Preorder）：根 → 左 → 右
   • 中序遍历（Inorder）：左 → 根 → 右
   • 后序遍历（Postorder）：左 → 右 → 根
2. 广度优先遍历（BFS） 
   • 层序遍历（Level Order）

 1. 二叉树节点定义

在 Java 中，二叉树的基本节点（TreeNode）可以这样定义：

class TreeNode {

    int value;  // 节点值

    TreeNode left;  // 左子节点

    TreeNode right; // 右子节点

    public TreeNode(int value) {

        this.value = value;

        this.left = null;

        this.right = null;

    }

}

---

 四、递归遍历二叉树

递归（Recursion）是二叉树遍历的常见方式，它利用函数调用栈来实现深度优先搜索。

---

1️⃣ 前序遍历（Preorder Traversal）

 访问顺序： 根 → 左 → 右

public class BinaryTreeTraversal {

    // 前序遍历

    public static void preorder(TreeNode root) {

        if (root == null) return;  // 递归终止条件

        System.out.print(root.value + " ");  // 访问根节点

        preorder(root.left);  // 递归访问左子树

        preorder(root.right); // 递归访问右子树

    }

    public static void main(String[] args) {

        // 创建二叉树

        TreeNode root = new TreeNode(1);

        root.left = new TreeNode(2);

        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);

        root.left.right = new TreeNode(5);

        root.right.right = new TreeNode(6);

        System.out.print("前序遍历：");

        preorder(root);

    }

}

✅ 运行结果：

前序遍历：1 2 4 5 3 6

---

2️⃣ 中序遍历（Inorder Traversal）

访问顺序： 左 → 根 → 右

public class BinaryTreeTraversal {

    // 中序遍历

    public static void inorder(TreeNode root) {

        if (root == null) return;  // 递归终止条件

        inorder(root.left);  // 递归访问左子树

        System.out.print(root.value + " ");  // 访问根节点

        inorder(root.right); // 递归访问右子树

    }

    public static void main(String[] args) {

        TreeNode root = new TreeNode(1);

        root.left = new TreeNode(2);

        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);

        root.left.right = new TreeNode(5);

        root.right.right = new TreeNode(6);

        System.out.print("中序遍历：");

        inorder(root);

    }

}

✅ 运行结果：

中序遍历：4 2 5 1 3 6

---

3️⃣ 后序遍历（Postorder Traversal）

 访问顺序： 左 → 右 → 根

public class BinaryTreeTraversal {

    // 后序遍历

    public static void postorder(TreeNode root) {

        if (root == null) return;  // 递归终止条件

        postorder(root.left);  // 递归访问左子树

        postorder(root.right); // 递归访问右子树

        System.out.print(root.value + " ");  // 访问根节点

    }

    public static void main(String[] args) {

        TreeNode root = new TreeNode(1);

        root.left = new TreeNode(2);

        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);

        root.left.right = new TreeNode(5);

        root.right.right = new TreeNode(6);

        System.out.print("后序遍历：");

        postorder(root);

    }

}

✅ 运行结果：

后序遍历：4 5 2 6 3 1

---

 五、二叉树遍历总结

遍历方式	访问顺序	适用场景
前序遍历	根 → 左 → 右	适合 复制树、表达式计算
中序遍历	左 → 根 → 右	适合 二叉搜索树（BST）遍历
后序遍历	左 → 右 → 根	适合 删除节点、释放内存

---

六、二叉树常考点与易错点

�� 1. 常考点

✅ 递归 vs 迭代遍历
✅ 二叉树的构造与遍历
✅ 二叉搜索树的中序遍历（结果是有序的）

---

�� 2. 易错点

❌ 递归终止条件错误

if (root == null) return;

❌ 错误的访问顺序

System.out.print(root.value + " "); // 误将根节点提前打印

inorder(root.left);

inorder(root.right);

✅ 正确的中序遍历

inorder(root.left);

System.out.print(root.value + " ");

inorder(root.right);

---

�� 七、学习建议

1. 递归终止条件：在递归实现遍历的过程中，要注意递归的终止条件，即当节点为空时要及时返回，否则会导致栈溢出错误。
2. 遍历顺序混淆：前序、中序、后序遍历的顺序容易混淆，在写代码时要仔细区分不同遍历方式的访问顺序。
3. 边界情况处理：对于空树的情况，要确保代码能够正确处理，避免出现空指针异常。

二叉树的遍历：前序、中序、后序遍历的递归实现。

树的构造：根据遍历结果重建二叉树。

树的深度和高度：计算二叉树的深度或高度。

树的遍历应用：如查找特定节点、统计节点数量等。