数据结构入门：二叉排序树的构建与相关算法

有序二叉树（二叉排序树）是数据结构中极具实用性的树形结构，其「左小右大」的核心特性让插入、查找、遍历操作具备高效性。

一、二叉排序树的定义

二叉排序树的核心规则：

• 任意节点的左子树中，所有节点值小于该节点值；
• 任意节点的右子树中，所有节点值大于该节点值；
• 左右子树也必须是二叉排序树。

二、节点类的构建

package com.qcby.Tree; /** * 二叉树节点类 * 存储节点数据、左子节点、右子节点引用 */ public class TreeNode { public TreeNode lChild; // 左子节点 public TreeNode rChild; // 右子节点 public Integer data; // 节点存储的数据 // 构造方法：初始化节点数据 public TreeNode(Integer data) { this.data = data; } }

三、二叉排序树的构建

3.1 插入逻辑拆解

1. 若树为空（根节点为 null），新节点直接作为根节点；
2. 若树非空，从根节点开始循环遍历：
   • 新节点值 > 当前节点值：向右子树查找，直到右子节点为 null，插入新节点；
   • 新节点值 ≤ 当前节点值：向左子树查找，直到左子节点为 null，插入新节点。

3.2 构建代码实现

package com.qcby.Tree; import java.util.LinkedList; /** * 有序二叉树核心类 * 包含构建、遍历、查找核心方法 */ public class BinaryTree { // 二叉树根节点，初始为空 TreeNode root; /** * 插入节点，构建有序二叉树 * @param value 要插入的节点值 */ public void insert(Integer value) { // 1. 创建新节点 TreeNode newNode = new TreeNode(value); // 2. 空树直接设为根节点 if (root == null) { root = newNode; return; } // 3. 非空树：从根节点开始找插入位置 TreeNode current = root; while (true) { // 新节点值大于当前节点 → 走右子树 if (newNode.data > current.data) { if (current.rChild == null) { current.rChild = newNode; return; } current = current.rChild; } else { // 新节点值小于等于当前节点 → 走左子树 if (current.lChild == null) { current.lChild = newNode; return; } current = current.lChild; } } } // 后续遍历、查找方法将在此类中补充 }

四、二叉排序树的遍历算法

遍历是访问二叉树所有节点的方式，分为深度优先遍历（先序、中序、后序）和广度优先遍历（层次遍历），两种方式适用于不同场景。

4.1 深度优先遍历（递归实现）

深度优先遍历的核心是「先深入子树，再回溯」，通过递归实现极为简洁，三种遍历的区别仅在于访问根节点的时机。

4.1.1 先序遍历（根 → 左 → 右）

逻辑：先访问当前节点 → 递归遍历左子树 → 递归遍历右子树；

特点：先拿到根节点，适合快速获取树的「根优先」结构。

/** * 先序遍历（深度优先） * @param node 遍历的起始节点（通常传根节点） */ public void preOrder(TreeNode node) { // 递归终止条件：节点为空 if (node == null) { return; } System.out.print(node.data + " "); // 1. 访问当前节点 preOrder(node.lChild); // 2. 遍历左子树 preOrder(node.rChild); // 3. 遍历右子树 }

4.1.2 中序遍历（左 → 根 → 右）

逻辑：递归遍历左子树 → 访问当前节点 → 递归遍历右子树；

特点：有序二叉树的中序遍历结果为升序序列，是有序二叉树最常用的遍历方式。

/** * 中序遍历（深度优先） * @param node 遍历的起始节点（通常传根节点） */ public void inOrder(TreeNode node) { if (node == null) { return; } inOrder(node.lChild); // 1. 遍历左子树 System.out.print(node.data + " "); // 2. 访问当前节点 inOrder(node.rChild); // 3. 遍历右子树 }

4.1.3 后序遍历（左 → 右 → 根）

逻辑：递归遍历左子树 → 递归遍历右子树 → 访问当前节点；

特点：最后访问根节点，适合「先处理子节点，再处理父节点」的场景（如删除节点）。

/** * 后序遍历（深度优先） * @param node 遍历的起始节点（通常传根节点） */ public void postOrder(TreeNode node) { if (node == null) { return; } postOrder(node.lChild); // 1. 遍历左子树 postOrder(node.rChild); // 2. 遍历右子树 System.out.print(node.data + " "); // 3. 访问当前节点 }

4.2 广度优先遍历（层次遍历）

广度优先遍历（层次遍历）的核心是「按层访问」，从根节点开始，依次访问每一层的所有节点，依赖队列实现（先进先出特性）。

4.2.1 层次遍历逻辑

1. 创建队列，将根节点入队；
2. 循环取出队首节点，访问该节点；
3. 将该节点的左、右子节点依次入队（若存在）；
4. 直到队列为空，遍历完成。

4.2.2 层次遍历代码实现

/** * 层次遍历（广度优先） * @param node 遍历的起始节点（通常传根节点） */ public void levelOrder(TreeNode node) { if (node == null) { return; } // 1. 创建队列存储待访问的节点 LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(node); // 2. 循环处理队列中的节点 while (!queue.isEmpty()) { // 取出队首节点并访问 TreeNode current = queue.pop(); System.out.print(current.data + " "); // 左子节点入队（若存在） if (current.lChild != null) { queue.add(current.lChild); } // 右子节点入队（若存在） if (current.rChild != null) { queue.add(current.rChild); } } }

五、二叉排序树的查找算法

基于有序二叉树「左小右大」的特性，查找节点的效率远高于无序二叉树（理想时间复杂度 O (logn)）。

5.1 迭代法查找（循环实现）

5.1.1 查找逻辑拆解

1. 从根节点开始遍历；
2. 若当前节点值等于目标值，返回该节点；
3. 若目标值 < 当前节点值，向左子树继续查找；
4. 若目标值 > 当前节点值，向右子树继续查找；
5. 若遍历到空节点仍未找到，返回 null。

5.1.2 迭代法代码实现

/** * 迭代法查找指定值的节点 * @param root 查找的起始节点（通常传根节点） * @param data 要查找的节点值 * @return 找到的节点（未找到返回null） */ public TreeNode find(TreeNode root, Integer data) { TreeNode current = root; // 循环查找，直到节点为空或找到目标 while (current != null) { if (current.data.equals(data)) { return current; // 找到目标节点，返回 } // 目标值更小 → 走左子树 if (data < current.data) { current = current.lChild; } else { // 目标值更大 → 走右子树 current = current.rChild; } } return null; // 未找到 }

5.2 递归法查找

5.2.1 查找逻辑拆解

1. 递归终止条件：当前节点为 null（未找到）或当前节点值等于目标值（找到）；
2. 若目标值 < 当前节点值，递归查找左子树；
3. 若目标值 > 当前节点值，递归查找右子树。

5.2.2 递归法代码实现

/** * 递归法查找指定值的节点 * @param root 查找的起始节点（通常传根节点） * @param data 要查找的节点值 * @return 找到的节点（未找到返回null） */ public TreeNode find(TreeNode root,Integer data){ TreeNode current = root; // 递归终止条件1：节点为空，未找到 if(current.data==null){ return null; } // 递归终止条件2：找到目标节点 if(current.data==data){ return current; } // 目标值更小 → 递归查找左子树 if(current.data< data){ return find(current.rChild,data); } else{ // 目标值更大 → 递归查找右子树 return find(current.lChild,data); } }

六、完整测试：验证所有功能

编写测试类，验证二叉树的构建、遍历、查找功能是否正常：

package com.qcby.Tree; /** * 有序二叉树测试类 */ public class Test { public static void main(String[] args) { // 1.创建二叉树实例 BinaryTree tree = new BinaryTree(); // 2. 插入节点构建有序二叉树 bt.create(5); bt.create(3); bt.create(7); bt.create(0); bt.create(4); bt.create(6); bt.create(9); // 3. 测试深度优先遍历 System.out.println("=== 深度优先遍历 ==="); System.out.print("先序遍历："); System.out.println(tree.beforeOrder(tree.root)); // 输出：5 3 0 4 7 6 9 System.out.print("中序遍历："); System.out.println(tree.inOrder(tree.root)); // 输出：0 3 4 5 6 7 9（升序） System.out.print("后序遍历："); System.out.println(tree.afterOrder(tree.root)); // 输出：0 4 3 6 9 7 5 // 4. 测试广度优先遍历 System.out.println("\n=== 广度优先遍历 ==="); System.out.print("层次遍历："); System.out.println(tree.levelOrder(tree.root)); // 输出：5 3 7 0 4 6 9 // 5. 测试节点查找 System.out.println("\n=== 节点查找 ==="); TreeNode target = tree.find(tree.root, 9); if (target != null) { System.out.println("找到节点：" + target.data); // 输出：找到节点：9 } else { System.out.println("未找到指定节点"); } TreeNode notFound = tree.find(tree.root, 10); if (notFound == null) { System.out.println("未找到节点：10"); // 输出：未找到节点：10 } } }