Java 实现二叉搜索树：遍历、查询、构建-程序员充电站

前言

二叉搜索树（Binary Search Tree，BST）是数据结构中最基础且应用广泛的树形结构，其核心特性是「左子树所有节点值 < 根节点值 < 右子树所有节点值」，基于这一特性可实现高效的查找、插入和遍历操作。本文将从底层原理出发，完整实现二叉搜索树的构建、前序 / 中序 / 后序 / 层次遍历、节点查询，并通过实战案例验证功能，帮助初学者彻底掌握 BST 的核心逻辑。

一、二叉搜索树核心概念

定义：二叉搜索树是一种二叉树，满足以下特性：
- 任意节点的左子树中，所有节点值均小于该节点值；
- 任意节点的右子树中，所有节点值均大于该节点值；
- 左右子树也必须是二叉搜索树。
优势：基于有序特性，BST 的查找、插入操作时间复杂度平均为 O (logn)（平衡时），远优于线性结构。

二、完整代码实现

2.1 二叉树节点类（TreeNode）

首先定义二叉树节点结构，包含数据域、左孩子、右孩子指针：

package com.qcby; /** * 二叉树节点类 * 包含左孩子、右孩子、数据域 */ public class TreeNode { // 左孩子节点 public TreeNode lChild; // 右孩子节点 public TreeNode rChild; // 节点数据（Integer类型支持空值） public Integer data; /** * 构造方法：初始化节点数据 * @param data 节点存储的数值 */ public TreeNode(Integer data) { this.data = data; } }

2.2 二叉搜索树核心类（BinaryTree）

实现 BST 的构建、四种遍历方式、节点查询核心功能：

package com.qcby; import java.util.LinkedList; /** * 二叉搜索树核心类 * 包含：创建节点、前序遍历、中序遍历、后序遍历、层次遍历、节点查询 */ public class BinaryTree { // 根节点（头指针） TreeNode root; /** * 插入节点构建二叉搜索树 * 核心逻辑：根据BST特性，小于当前节点则往左子树插，大于则往右子树插 * @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) { // 3.1 新节点值大于当前节点 → 往右子树走 if (curNode.data < newNode.data) { // 右孩子为空，直接插入 if (curNode.rChild == null) { curNode.rChild = newNode; return; } // 右孩子非空，继续遍历右子树 curNode = curNode.rChild; } else { // 3.2 新节点值小于等于当前节点 → 往左子树走 if (curNode.lChild == null) { curNode.lChild = newNode; return; } // 左孩子非空，继续遍历左子树 curNode = curNode.lChild; } } } /** * 前序遍历（根 → 左 → 右） * 递归实现：先访问根节点，再递归左子树，最后递归右子树 * @param root 当前遍历的根节点 */ void beforeOrder(TreeNode root) { // 递归终止条件：节点为空 if (root == null) { return; } // 1. 访问根节点 System.out.print(root.data + " "); // 2. 递归遍历左子树 beforeOrder(root.lChild); // 3. 递归遍历右子树 beforeOrder(root.rChild); } /** * 中序遍历（左 → 根 → 右） * 递归实现：先递归左子树，再访问根节点，最后递归右子树 * 注：BST的中序遍历结果为有序序列（升序） * @param root 当前遍历的根节点 */ void inOrder(TreeNode root) { if (root == null) { return; } // 1. 递归遍历左子树 inOrder(root.lChild); // 2. 访问根节点 System.out.print(root.data + " "); // 3. 递归遍历右子树 inOrder(root.rChild); } /** * 后序遍历（左 → 右 → 根） * 递归实现：先递归左子树，再递归右子树，最后访问根节点 * @param root 当前遍历的根节点 */ void afterOrder(TreeNode root) { if (root == null) { return; } // 1. 递归遍历左子树 afterOrder(root.lChild); // 2. 递归遍历右子树 afterOrder(root.rChild); // 3. 访问根节点 System.out.print(root.data + " "); } /** * 查找指定值的节点 * 基于BST特性：大于当前节点查右子树，小于查左子树，等于则返回 * @param root 遍历的根节点 * @param target 待查找的目标值 * @return 找到的节点（未找到返回null） */ public TreeNode searchNode(TreeNode root, Integer target) { // 递归终止条件：节点为空 或 找到目标节点 if (root == null || root.data.equals(target)) { return root; } // 目标值大于当前节点 → 查右子树 if (target > root.data) { return searchNode(root.rChild, target); } else { // 目标值小于当前节点 → 查左子树 return searchNode(root.lChild, target); } } /** * 层次遍历（广度优先遍历） * 基于队列实现：先入队根节点，出队时访问节点，再入队左右孩子 * @param root 遍历的根节点 */ void levelOrder(TreeNode root) { // 1. 空树直接返回 if (root == null) { return; } // 2. 创建队列存储节点（LinkedList实现Deque接口） LinkedList<TreeNode> queue = new LinkedList<>(); // 3. 根节点入队 queue.add(root); // 4. 队列非空时循环 while (!queue.isEmpty()) { // 4.1 出队并访问节点 TreeNode node = queue.pop(); System.out.print(node.data + " "); // 4.2 左孩子非空则入队 if (node.lChild != null) { queue.add(node.lChild); } // 4.3 右孩子非空则入队 if (node.rChild != null) { queue.add(node.rChild); } } } }

2.3 测试类（Test）

编写测试代码验证 BST 的构建、遍历、查询功能：

package com.qcby; /** * 测试类：验证二叉搜索树的构建、遍历、查询功能 */ public class Test { public static void main(String[] args) { // 1. 创建二叉搜索树实例 BinaryTree bt = new BinaryTree(); // 2. 插入节点构建树：5(根) → 3 → 7 → 0 → 4 → 6 → 9 bt.create(5); bt.create(3); bt.create(7); bt.create(0); bt.create(4); bt.create(6); bt.create(9); // 3. 测试层次遍历（预期输出：5 3 7 0 4 6 9） System.out.println("层次遍历结果："); bt.levelOrder(bt.root); // 4. 测试前序遍历（预期输出：5 3 0 4 7 6 9） System.out.println("\n前序遍历结果："); bt.beforeOrder(bt.root); // 5. 测试中序遍历（预期输出：0 3 4 5 6 7 9 → 升序） System.out.println("\n中序遍历结果："); bt.inOrder(bt.root); // 6. 测试后序遍历（预期输出：0 4 3 6 9 7 5） System.out.println("\n后序遍历结果："); bt.afterOrder(bt.root); // 7. 测试节点查询（查找值为5的节点） TreeNode targetNode = bt.searchNode(bt.root, 5); System.out.println("\n查找目标节点值：" + targetNode.data); } }