一、概念
二叉排序树（也叫二叉搜索树）是一种基于 “左小右大” 规则的有序二叉树
特点：
- 左子节点的值小于父节点的值
- 右子节点的值大于父节点的值
- 每个节点由 3 部分组成（类 / 对象结构）：
lChild：左子节点引用data：节点存储的数据rChild：右子节点引用
二、节点定义
package com.qcby.Tree; public class TreeNode { public TreeNode lChild; // 左子节点 public TreeNode rChild; // 右子节点 public Integer data; // 节点数据 // 构造方法：初始化节点数据 public TreeNode(Integer data) { this.data = data; } }三、二叉排序树的相关操作
包括创建（插入节点）、遍历、查询
1. 新建（插入节点）
插入节点的逻辑遵循 “左小右大” 的规则，步骤如下：
- 若树为空（
root == null），新节点直接作为根节点； - 若树非空，循环判断新节点与当前节点的大小：
- 新节点值大于当前节点：向右子树查找，直到右子节点为空，插入新节点；
- 新节点值小于 / 等于当前节点：向左子树查找，直到左子节点为空，插入新节点。
package com.qcby.Tree; import java.util.LinkedList; public class BinaryTree { 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; } } } }2. 遍历操作
二叉排序树支持 4 种常见遍历方式，分别对应不同的访问顺序：
（1）先序遍历（根→左→右）
// 先序遍历 public void beforeOrder(TreeNode node) { if (node == null) { return; } System.out.print(node.data + " "); // 访问根 beforeOrder(node.lChild); // 遍历左子树 beforeOrder(node.rChild); // 遍历右子树 }（2）中序遍历（左→根→右）
二叉排序树的中序遍历结果是升序序列
// 中序遍历 public void inOrder(TreeNode node) { if (node == null) { return; } inOrder(node.lChild); // 遍历左子树 System.out.print(node.data + " "); // 访问根 inOrder(node.rChild); // 遍历右子树 }（3）后序遍历（左→右→根）
// 后序遍历 public void afterOrder(TreeNode node) { if (node == null) { return; } afterOrder(node.lChild); // 遍历左子树 afterOrder(node.rChild); // 遍历右子树 System.out.print(node.data + " "); // 访问根 }（4）层次遍历（广度优先，按层级访问）
通过队列实现，依次访问每一层的节点：
// 层次遍历 public void levelOrder(TreeNode root) { if (root == null) { return; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); System.out.print(node.data + " "); // 访问当前节点 if (node.lChild != null) { queue.add(node.lChild); // 左子节点入队 } if (node.rChild != null) { queue.add(node.rChild); // 右子节点入队 } } }3. 节点查询
利用 “左小右大” 的特性，递归查找目标节点：
// 递归查询指定节点 public TreeNode find(TreeNode root, Integer data) { if (root == null) { // 节点为空，未找到 return null; } if (root.data.equals(data)) { // 找到目标节点 return root; } if (root.data < data) { // 目标值更大，查右子树 return find(root.rChild, data); } else { // 目标值更小，查左子树 return find(root.lChild, data); } }
)
