目录
引入：
一、二叉树节点的定义
二、二叉树的构建（插入节点）
三、二叉树的遍历
3.1深度优先遍历
3.1.1先序遍历（根 → 左 → 右）
3.1.2中序遍历（左 → 根 → 右）
3.1.3后序遍历（左 → 右 → 根）
3.2广度优先遍历
四、二叉树的查找
五、完整测试代码
六、输出结果
七、总结
引入：
二叉树是数据结构中的基础结构之一，常用于实现排序、查找等功能。本文将基于 Java 实现二叉树的构建、深度优先遍历（先序/中序/后序）、广度优先遍历与查找，并通过代码示例详解核心逻辑。
一、二叉树节点的定义
二叉树的基本单元是“节点”，每个节点包含左子节点、右子节点、数据域三个部分，对应 Java 类的实现如下：
/** * 二叉树节点类 */ public class TreeNode { // 左子节点 public TreeNode lChild; // 右子节点 public TreeNode rChild; // 数据域 public Integer data; // 构造方法 public TreeNode(Integer data) { this.data = data; } }二、二叉树的构建（插入节点）
二叉树的构建逻辑是按“左小右大”的规则插入节点：
- 若树为空，新节点作为根节点；
- 若树非空，从根节点开始比较：( 新节点数据 > 当前节点数据 → 插入到右子树； 新节点数据 ≤ 当前节点数据 → 插入到左子树；)
- 循环查找，直到找到空的子节点位置，插入新节点。
代码实现
/** * 二叉树类 */ public class BinaryTree { // 根节点 public TreeNode root; /** * 插入节点（构建二叉树） * @param value 要插入的数据 */ public void create(Integer value) { // 1. 创建新节点 TreeNode newNode = new TreeNode(value); // 2. 若树为空，新节点作为根节点 if (root == null) { root = newNode; return; } // 3. 从根节点开始遍历，找到插入位置 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; } } } }测试示例
插入数据 `5、7、2、6、0、4、3、1`，构建的二叉树结构如下：
三、二叉树的遍历
二叉树的深度优先遍历分为先序、中序、后序三种（以根节点的访问时机区分），通常采用递归实现。
3.1深度优先遍历
3.1.1先序遍历（根 → 左 → 右）
先访问根节点，再递归遍历左子树，最后递归遍历右子树。
/** * 先序遍历 * @param root 遍历的起始节点 */ public void beforeOrder(TreeNode root) { if (root == null) { return; } // 1. 访问根节点 System.out.print(root.data + " "); // 2. 遍历左子树 beforeOrder(root.lChild); // 3. 遍历右子树 beforeOrder(root.rChild); }- 遍历结果：5 2 0 1 4 3 7 6
3.1.2中序遍历（左 → 根 → 右）
先递归遍历左子树，再访问根节点，最后递归遍历右子树。
/** * 中序遍历 * @param root 遍历的起始节点 */ public void inOrder(TreeNode root) { if (root == null) { return; } // 1. 遍历左子树 inOrder(root.lChild); // 2. 访问根节点 System.out.print(root.data + " "); // 3. 遍历右子树 inOrder(root.rChild); }- 遍历结果：0 1 2 3 4 5 6 7（注：二叉排序树的中序遍历结果是有序的）
3.1.3后序遍历（左 → 右 → 根）
先递归遍历左子树，再递归遍历右子树，最后访问根节点。
/** * 后序遍历 * @param root 遍历的起始节点 */ public void afterOrder(TreeNode root) { if (root == null) { return; } // 1. 遍历左子树 afterOrder(root.lChild); // 2. 遍历右子树 afterOrder(root.rChild); // 3. 访问根节点 System.out.print(root.data + " "); }- 遍历结果：1 0 3 4 2 6 7 5
3.2广度优先遍历
又叫层次优先遍历
- 上图的广度优先遍历结果为：5 2 7 0 4 6 1 3
四、二叉树的查找
查找逻辑与构建逻辑一致：从根节点开始比较，根据“左小右大”的规则遍历，直到找到目标节点或遍历到空节点。
代码实现
/** * 查找节点 * @param root 查找的起始节点 * @param value 要查找的数据 * @return 找到的节点（未找到返回null） */ public TreeNode findNode(TreeNode root, Integer value) { if (root == null) { return null; } TreeNode curNode = root; while (true) { if (curNode.data.equals(value)) { return curNode; } else if (curNode.data < value) { if (curNode.rChild == null) { return null; } curNode = curNode.rChild; } else { if (curNode.lChild == null) { return null; } curNode = curNode.lChild; } } }五、完整测试代码
public class Test { public static void main(String[] args) { BinaryTree bt = new BinaryTree(); // 插入节点构建二叉树 bt.create(5); bt.create(7); bt.create(2); bt.create(6); bt.create(0); bt.create(4); bt.create(3); bt.create(1); // 先序遍历 System.out.print("先序遍历："); bt.beforeOrder(bt.root); System.out.println(); // 中序遍历 System.out.print("中序遍历："); bt.inOrder(bt.root); System.out.println(); // 后序遍历 System.out.print("后序遍历："); bt.afterOrder(bt.root); System.out.println(); // 查找节点 TreeNode findNode = bt.findNode(bt.root, 4); System.out.println("查找值为4的节点：" + (findNode != null ? findNode.data : "未找到")); } }六、输出结果
- 先序遍历：5 2 0 1 4 3 7 6
- 中序遍历：0 1 2 3 4 5 6 7
- 后序遍历：1 0 3 4 2 6 7 5
- 查找值为4的节点：4
七、总结
本文实现了二叉树的核心操作：
- 构建：按“左小右大”规则插入节点，形成二叉排序树；
- 遍历：通过递归实现先序、中序、后序遍历，其中中序遍历结果是有序的；
- 查找：基于“左小右大”规则遍历树，时间复杂度为O(logn)（平衡二叉树）。
二叉树是后续学习平衡二叉树、红黑树等高级结构的基础，掌握其核心操作能帮助你理解更复杂的数据结构逻辑。
