news 2026/4/23 15:22:48

Java 实现二叉搜索树：遍历、查询、构建

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
Java 实现二叉搜索树：遍历、查询、构建
前言

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

一、二叉搜索树核心概念
  1. 定义：二叉搜索树是一种二叉树，满足以下特性：
    • 任意节点的左子树中，所有节点值均小于该节点值；
    • 任意节点的右子树中，所有节点值均大于该节点值；
    • 左右子树也必须是二叉搜索树。
  2. 优势：基于有序特性，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); } }
三、核心功能详解
3.1 构建二叉搜索树（create 方法）
  • 逻辑：从根节点开始，比较待插入值与当前节点值：
    • 若当前节点为空，直接插入；
    • 若待插入值更大，遍历右子树；
    • 若更小，遍历左子树；
    • 找到空的左 / 右孩子位置，完成插入。
  • 示例构建的树结构：
3.2 四种遍历方式对比

3.3 节点查询（searchNode 方法）
  • 核心：利用 BST 有序特性，减少无效遍历：
    • 目标值 > 当前节点 → 查右子树；
    • 目标值 < 当前节点 → 查左子树；
    • 相等则返回当前节点；
    • 节点为空则返回 null（未找到）。
  • 时间复杂度：平衡树为 O (logn)，最坏（退化为链表）为 O (n)。
四、运行结果

执行 Test 类，控制台输出如下：

六、总结

本文完整实现了二叉搜索树的构建、四种遍历方式和节点查询功能，核心要点：

  1. BST 的核心特性是「左小右大」，决定了插入和查询的逻辑；
  2. 中序遍历是 BST 的标志性遍历方式，结果为升序序列；
  3. 层次遍历依赖队列实现，是广度优先搜索的典型应用；
  4. 递归遍历的关键是「终止条件（节点为空）」和「遍历顺序」。
版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/4/23 13:02:35

Win11共享打印0x0000bc4，三步解决共享难题

一、检查共享设置与网络配置Win11共享打印0x0000bc4可先从基础设置错误&#xff0c;多数情况是网络或权限配置遗漏导致。2.1 启用共享基础功能设置网络配置文件&#xff1a;打开「设置→网络和Internet→高级网络设置」&#xff0c;将当前网络设为「专用」&#xff0c;公用网络…

作者头像 李华
网站建设 2026/4/23 10:58:23

本地部署音乐下载器 PlaylistDL 并实现外部访问

PlaylistDL 是一款开源音乐下载器&#xff0c;这款音乐下载器界面简单友好&#xff0c;它可以实现让用户直接从 Spotify 和 YouTube 上一键下载歌曲、专辑或播放列表&#xff0c;而且还可以将下载的歌曲转换成 MP3 格式。本文将详细的介绍如何利用 Docker 在本地部署 PlaylistD…

作者头像 李华
网站建设 2026/4/23 14:35:30

【探究】C语言-类型转换问题

浮点数的数据储存方式变量的自动转化前言为了探究变量自动转换的问题&#xff0c;我们首先需要知道为什么程序中需要有变量类型的存在&#xff1f;我们知道&#xff0c;人类发明的目的是为了更好得改善生活体验&#xff0c;其创造出的每个东西都有其存在的目的和价值。发明文字…

作者头像 李华
网站建设 2026/4/23 13:08:03

【毕业设计】基于springboot+微信小程序的跑腿小程序的设计与实现(源码+文档+远程调试，全bao定制等)

博主介绍&#xff1a;✌️码农一枚 &#xff0c;专注于大学生项目实战开发、讲解和毕业&#x1f6a2;文撰写修改等。全栈领域优质创作者&#xff0c;博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技术领域和毕业项目实战 ✌️技术范围&#xff1a;&am…

作者头像 李华
网站建设 2026/4/23 12:52:53

小程序毕设选题推荐：基于微信小程序的网红餐饮店订餐预约系统的设计与实现基于springboot+微信小程序的餐厅预约系统设计与实现【附源码、mysql、文档、调试+代码讲解+全bao等】

博主介绍&#xff1a;✌️码农一枚 &#xff0c;专注于大学生项目实战开发、讲解和毕业&#x1f6a2;文撰写修改等。全栈领域优质创作者&#xff0c;博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技术领域和毕业项目实战 ✌️技术范围&#xff1a;&am…

作者头像 李华