一、二叉树的定义与基本概念
二叉树是一种非线性数据结构，每个节点最多包含 2 个子节点（左子节点、右子节点），核心特点：
（1）每个节点的子树数量不超过 2；
（2）左、右子树是有序的（即使只有一个子树，也需明确是左 / 右子树）；
（3）可衍生出多种特殊结构（如二叉搜索树、完全二叉树、满二叉树等）。
二、创建二叉树的常见方法
1. 节点类定义
二叉树的基础是 “节点”，需包含数据域和指针域（指向左 / 右子节点），Java 实现示例：
package com.heima.Tree; public class TreeNode { // 左子节点指针 public TreeNode lChild; // 右子节点指针 public TreeNode rChild; // 数据域（存储节点值） public Integer data; // 构造方法：初始化节点数据 public TreeNode(Integer data) { this.data = data; } }2. 手动创建二叉树（以 “二叉搜索树” 为例）
通过create方法插入节点，遵循二叉搜索树规则（左子树值 < 父节点值 < 右子树值），实现逻辑（1）若树为空，新节点作为根节点；
（2）若树非空，从根节点开始比较：
1）新节点值 > 当前节点值 → 走右子树（直到右子树为空，插入新节点）；
2）新节点值 < 当前节点值 → 走左子树（直到左子树为空，插入新节点）。
Java 实现示例：
public class BinaryTree { // 树的根节点指针 private TreeNode root; // 插入节点的方法 public void create(Integer value) { // 新建节点 TreeNode newNode = new TreeNode(value); // 情况1：树为空 → 新节点作为根 if (root == null) { root = newNode; return; } // 情况2：树非空 → 从根开始遍历插入 TreeNode curNode = root; while (true) { // 新节点值 > 当前节点值 → 走右子树 if (curNode.data < newNode.data) { // 右子树为空 → 插入新节点 if (curNode.rChild == null) { curNode.rChild = newNode; return; } // 右子树非空 → 继续遍历右子树 curNode = curNode.rChild; } // 新节点值 < 当前节点值 → 走左子树 else { // 左子树为空 → 插入新节点 if (curNode.lChild == null) { curNode.lChild = newNode; return; } // 左子树非空 → 继续遍历左子树 curNode = curNode.lChild; } } } }3. 调用方法构建二叉树
创建BinaryTree对象，多次调用create方法插入节点，即可构建二叉树。示例（插入值5、3、7、8、4、6、9）：
public static void main(String[] args) { BinaryTree bt = new BinaryTree(); bt.create(5); // 根节点 bt.create(3); // 5的左子节点 bt.create(7); // 5的右子节点 bt.create(8); // 7的右子节点 bt.create(4); // 3的右子节点 bt.create(6); // 7的左子节点 bt.create(9); // 8的右子节点 }最终构建的二叉搜索树结构：
5 / \ 3 7 \ / \ 4 6 8 \ 9三、二叉树的应用场景
二叉树（含其特殊结构）在多领域有核心作用：
（1）表达式树：表示数学表达式（如a*(b+c)，根节点为*，左子树为a，右子树为(b+c)）；
（2）二叉搜索树：实现高效的 “增删查”（平均时间复杂度 O (logn)）；
（3）堆结构：实现优先队列（大顶堆 / 小顶堆），用于任务调度、TopK 问题等；
（4）哈夫曼编码树：数据压缩（如 ZIP 压缩），通过字符出现频率构建树，生成最短编码；（5）决策树：机器学习中用于分类 / 回归（如 ID3、C4.5、CART 树）；
（6）平衡二叉树（如 AVL 树、红黑树）：解决普通二叉搜索树的 “退化成链表” 问题，用于 JDK 集合（如TreeMap）。
四、创建二叉树的注意事项
（1）避免循环引用（如节点的左 / 右子节点指向自身或祖先节点）；
（2）递归创建大二叉树时，注意栈溢出风险（可改用迭代方式）；
（3）空节点的表示需统一（用null），避免逻辑混乱；
（4）不同的 “插入 / 遍历顺序” 会生成不同结构的二叉树（如同一组值，按不同顺序插入，二叉搜索树的形态会不同）。
五、二叉树的 4 种遍历方式
遍历的核心是 “按规则访问树中所有节点，且每个节点仅访问一次”。不同的遍历顺序对应不同的应用场景，我们逐一解析。
1. 先序遍历（Preorder Traversal）
（1）概念与规则
先序遍历的顺序是：根节点 → 左子树 → 右子树。优先访问当前节点，再递归处理左右子树。
（2）遍历步骤
1）访问当前根节点（如打印节点值）；
2）递归遍历左子树；
3）递归遍历右子树。
（3）示例
以下二叉树的先序遍历结果为：A → B → D → E → C → F
A / \ B C / \ \ D E F// 先序遍历（递归） public void preOrder(TreeNode root) { if (root == null) { return; } // 1. 访问根节点 System.out.println(root.data); // 2. 递归左子树 preOrder(root.lChild); // 3. 递归右子树 preOrder(root.rChild); }（4）应用场景
1）目录结构打印（先输出当前目录，再遍历子目录）；
2）表达式树生成前缀表达式（如+ A * B C）；
3）树的序列化（保存树结构以便重建）。
（5）复杂度
1）时间复杂度：O(n)（每个节点访问一次）；
2）空间复杂度：递归方式为O(h)（h 为树高），非递归方式最坏为O(n)。
2. 中序遍历（In-order Traversal）
（1）概念与规则
中序遍历的顺序是：左子树 → 根节点 → 右子树。对于二叉搜索树（BST），中序遍历会得到升序的节点序列，这是其最核心的特性。
（2）示例
以下二叉树的中序遍历结果为：4 → 2 → 5 → 1 → 3
1 / \ 2 3 / \ 4 5// 中序遍历（递归） public void inOrder(TreeNode root) { if (root == null) { return; } // 1. 递归左子树 inOrder(root.lChild); // 2. 访问根节点 System.out.println(root.data); // 3. 递归右子树 inOrder(root.rChild); }（3）应用场景
1）二叉搜索树的升序遍历；
2）表达式树生成中缀表达式（如4 + 2 * 5）；
3）编译原理中的语法树遍历。
3. 后序遍历（Postorder Traversal）
（1）概念与规则
后序遍历的顺序是：左子树 → 右子树 → 根节点。特点是 “最后访问根节点”，常用于 “先处理子节点，再处理父节点” 的场景。
（2）示例
以下二叉树的后序遍历结果为：D → E → B → F → C → A
A / \ B C / \ \ D E F// 后序遍历（递归） public void postOrder(TreeNode root) { if (root == null) { return; } // 1. 递归左子树 postOrder(root.lChild); // 2. 递归右子树 postOrder(root.rChild); // 3. 访问根节点 System.out.println(root.data); }（3）应用场景
1）表达式树计算结果（如(3+4)*5）；
2）文件系统删除（先删子目录 / 文件，再删父目录）；
3）内存释放（先释放子节点，再释放父节点）。
4. 层次遍历（Level Order Traversal）
（1）概念与规则
层次遍历也叫广度优先遍历（BFS），按 “层级顺序” 访问节点：从根节点开始，依次访问第 1 层、第 2 层…… 同一层从左到右访问。
实现依赖队列：先入队根节点，出队时访问该节点，并将其左右子节点入队，循环直到队列为空。
（2）示例：Java 实现（队列）
// 层次遍历（基于队列） 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.println(node.data); // 左子节点入队 if (node.lChild != null) { queue.offer(node.lChild); } // 右子节点入队 if (node.rChild != null) { queue.offer(node.rChild); } } }（3）应用场景
1）求二叉树的最小深度；
2）展示家族 / 组织的层级关系；
3）网络爬虫按链接层级抓取网页。
六、二叉搜索树的节点查询
对于二叉搜索树（BST），节点查询可以利用其 “左子树值 < 根节点值 < 右子树值” 的特性，实现高效查找（平均时间复杂度O(logn)）。
（1）查询逻辑
1）若当前节点为空，返回null（未找到）；
2）若当前节点值等于目标值，返回该节点；
3）若当前节点值 < 目标值，递归查询右子树；
4）若当前节点值 > 目标值，递归查询左子树。
（2）代码Java 实现
// 二叉搜索树节点查询 public TreeNode findNode(TreeNode root, Integer target) { // 树为空，未找到 if (root == null) { return null; } // 找到目标节点 if (root.data.equals(target)) { return root; } // 目标值更大，查右子树 else if (root.data < target) { return findNode(root.rChild, target); } // 目标值更小，查左子树 else { return findNode(root.lChild, target); } }
