Java 二叉树实战：构建、遍历与查找的完整实现-程序员充电站

引入：

一、二叉树节点的定义

二、二叉树的构建（插入节点）

三、二叉树的遍历

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 : "未找到")); } }