二叉排序树从入门到实践：攻克构建与遍历核心逻辑-深圳市維司達科技有限公司

在数据结构的学习中，二叉排序树（Binary Sort Tree，BST）是连接 “树结构” 与 “高效数据操作” 的关键桥梁。它凭借 “左子树节点值小于父节点、右子树节点值大于父节点” 的核心特性，实现了查找、插入操作的高效性，在信息检索、动态集合维护等场景中应用广泛。本文将聚焦二叉排序树的两大核心能力 ——构建（新增节点）与遍历（查找衍生操作），通过清晰的逻辑拆解、代码实现与原理分析，帮助你轻松掌握这一基础数据结构，难度评级为两颗星，适合入门级学习者深入理解。

一、二叉排序树的基础定义

1.1 核心特性

二叉排序树要么是一棵空树，要么是满足以下条件的非空二叉树：

若左子树非空，则左子树上所有节点的关键字值均小于根节点的关键字值；
若右子树非空，则右子树上所有节点的关键字值均大于根节点的关键字值；
左、右子树本身也分别是一棵二叉排序树（递归特性）。

关键结论：对二叉排序树进行中序遍历，会得到一个严格递增的有序序列，这是二叉排序树的核心价值所在。

1.2 节点类设计

在 Java 中，我们通过类来定义二叉排序树的节点，每个节点包含三个核心属性：数据值、左子节点引用、右子节点引用。

/** * 二叉排序树节点类 */ class BSTNode { int val; // 节点存储的数据 BSTNode left; // 左子节点引用 BSTNode right; // 右子节点引用 // 构造方法 public BSTNode(int val) { this.val = val; this.left = null; this.right = null; } }

二、二叉排序树的构建（新增节点）

二叉排序树的构建是一个动态插入的过程，树的结构由依次插入的节点决定。核心逻辑是遵循 “左小右大” 原则，为新节点找到合适的空位置。

2.1 核心插入逻辑

空树判断：如果当前树为空（根节点为null），则新节点直接作为根节点。
循环查找位置：如果树非空，从根节点开始遍历：
- 若新节点值小于当前节点值：向左子树移动，若左子节点为null，则插入此处；
- 若新节点值大于当前节点值：向右子树移动，若右子节点为null，则插入此处；
- 若新节点值等于当前节点值：直接跳过（二叉排序树默认不存储重复值）。
引用更新：插入新节点时，只需修改父节点的左 / 右子节点引用即可，无需移动已有节点。

2.2 非递归实现（推荐入门）

非递归实现通过循环遍历树的分支，避免了递归的栈开销，且更易理解引用的传递过程。

/** * 二叉排序树操作类 */ public class BinarySortTree { private BSTNode root; // 根节点 // 构造方法：初始化空树 public BinarySortTree() { this.root = null; } /** * 插入节点（非递归实现） * @param val 要插入的数据值 */ public void insert(int val) { BSTNode newNode = new BSTNode(val); // 情况1：树为空，新节点作为根节点 if (root == null) { root = newNode; return; } // 情况2：树非空，查找插入位置 BSTNode curr = root; // 当前遍历节点 BSTNode parent = null; // 记录当前节点的父节点 while (curr != null) { parent = curr; if (val < curr.val) { // 新值小，向左子树找 curr = curr.left; } else if (val > curr.val) { // 新值大，向右子树找 curr = curr.right; } else { // 存在重复值，直接返回 return; } } // 找到空位置，插入新节点 if (val < parent.val) { parent.left = newNode; } else { parent.right = newNode; } } }

2.3 递归实现

利用二叉排序树的递归特性，可简化插入代码，逻辑与非递归实现完全一致。

/** * 递归插入节点 * @param node 当前遍历的节点（初始为root） * @param val 要插入的值 * @return 插入后的当前节点 */ private BSTNode insertRecursive(BSTNode node, int val) { // 递归终止条件：找到空位置，返回新节点 if (node == null) { return new BSTNode(val); } // 递归查找左/右子树 if (val < node.val) { node.left = insertRecursive(node.left, val); } else if (val > node.val) { node.right = insertRecursive(node.right, val); } // 重复值直接返回原节点 return node; } // 对外暴露的递归插入方法 public void insertByRecursive(int val) { root = insertRecursive(root, val); }

2.4 完整构建示例

通过向空树中依次插入数组元素，即可构建一棵完整的二叉排序树。

// 测试构建二叉排序树 public static void main(String[] args) { int[] arr = {5, 3, 7, 2, 4, 6, 8}; BinarySortTree bst = new BinarySortTree(); for (int num : arr) { bst.insert(num); // 调用非递归插入 // 或调用递归插入：bst.insertByRecursive(num); } }

三、二叉排序树的遍历（Java 实现）

遍历是访问树中所有节点的过程，二叉排序树的遍历分为深度优先遍历（DFS）和广度优先遍历（BFS）两大类，其中深度优先遍历包含前序、中序、后序三种方式。

我们在BinarySortTree类中添加以下遍历方法。

3.1 深度优先遍历（DFS）

深度优先遍历的核心是优先访问子树的深度，可通过递归或栈（非递归）实现，三种方式的区别在于根节点的访问时机。

3.1.1 前序遍历：根 → 左子树 → 右子树

特点：先访问根节点，再递归遍历左子树，最后递归遍历右子树。应用场景：复制树结构、获取树的拓扑结构。遍历结果（以上文树为例）：5 3 2 4 7 6 8

递归实现

/** * 前序遍历（递归） * @param node 当前节点 */ public void preOrder(BSTNode node) { if (node == null) { return; } System.out.print(node.val + " "); // 1. 访问根节点 preOrder(node.left); // 2. 遍历左子树 preOrder(node.right); // 3. 遍历右子树 }

非递归实现（栈）Java 中可使用java.util.Stack类模拟栈结构，注意右子节点先入栈（栈先进后出）。

import java.util.Stack; /** * 前序遍历（非递归-栈实现） */ public void preOrderNonRecursive() { if (root == null) { return; } Stack<BSTNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { BSTNode curr = stack.pop(); System.out.print(curr.val + " "); // 访问根节点 // 右子节点先入栈，左子节点后入栈 if (curr.right != null) { stack.push(curr.right); } if (curr.left != null) { stack.push(curr.left); } } }

3.1.2 中序遍历：左子树 → 根 → 右子树

特点：先递归遍历左子树，再访问根节点，最后递归遍历右子树。核心优势：遍历结果为严格递增的有序序列（二叉排序树的核心特性）。应用场景：获取有序数据、验证二叉排序树的合法性。遍历结果：2 3 4 5 6 7 8

递归实现

/** * 中序遍历（递归） * @param node 当前节点 */ public void inOrder(BSTNode node) { if (node == null) { return; } inOrder(node.left); // 1. 遍历左子树 System.out.print(node.val + " "); // 2. 访问根节点 inOrder(node.right); // 3. 遍历右子树 }

非递归实现（栈）

/** * 中序遍历（非递归-栈实现） */ public void inOrderNonRecursive() { if (root == null) { return; } Stack<BSTNode> stack = new Stack<>(); BSTNode curr = root; while (curr != null || !stack.isEmpty()) { // 先遍历所有左子节点，压入栈 while (curr != null) { stack.push(curr); curr = curr.left; } // 弹出栈顶节点，访问 curr = stack.pop(); System.out.print(curr.val + " "); // 遍历右子树 curr = curr.right; } }

3.1.3 后序遍历：左子树 → 右子树 → 根

特点：先递归遍历左子树，再递归遍历右子树，最后访问根节点。应用场景：删除树结构、计算子树的节点数或深度。

遍历结果：2 4 3 6 8 7 5

递归实现

/** * 后序遍历（递归） * @param node 当前节点 */ public void postOrder(BSTNode node) { if (node == null) { return; } postOrder(node.left); // 1. 遍历左子树 postOrder(node.right); // 2. 遍历右子树 System.out.print(node.val + " "); // 3. 访问根节点 }

3.2 广度优先遍历（BFS）：层次遍历

层次遍历的核心是按层级访问节点，先访问根节点（第 1 层），再访问第 2 层，以此类推。Java 中使用java.util.Queue队列（先进先出）实现。

应用场景：按层级处理任务、计算树的宽度。

遍历结果：5 3 7 2 4 6 8

import java.util.LinkedList; import java.util.Queue; /** * 层次遍历（队列实现） */ public void levelOrder() { if (root == null) { return; } Queue<BSTNode> queue = new LinkedList<>(); queue.offer(root); // 根节点入队 while (!queue.isEmpty()) { BSTNode curr = queue.poll(); // 出队并访问 System.out.print(curr.val + " "); // 左子节点先入队 if (curr.left != null) { queue.offer(curr.left); } // 右子节点后入队 if (curr.right != null) { queue.offer(curr.right); } } }

四、完整测试代码

将所有方法整合后，编写测试类验证功能：

import java.util.LinkedList; import java.util.Queue; import java.util.Stack; // 节点类 class BSTNode { int val; BSTNode left; BSTNode right; public BSTNode(int val) { this.val = val; } } // 二叉排序树操作类 public class BinarySortTree { private BSTNode root; public BinarySortTree() { this.root = null; } // 非递归插入 public void insert(int val) { BSTNode newNode = new BSTNode(val); if (root == null) { root = newNode; return; } BSTNode curr = root; BSTNode parent = null; while (curr != null) { parent = curr; if (val < curr.val) { curr = curr.left; } else if (val > curr.val) { curr = curr.right; } else { return; } } if (val < parent.val) { parent.left = newNode; } else { parent.right = newNode; } } // 递归插入辅助方法 private BSTNode insertRecursive(BSTNode node, int val) { if (node == null) { return new BSTNode(val); } if (val < node.val) { node.left = insertRecursive(node.left, val); } else if (val > node.val) { node.right = insertRecursive(node.right, val); } return node; } // 递归插入对外方法 public void insertByRecursive(int val) { root = insertRecursive(root, val); } // 前序递归遍历 public void preOrder(BSTNode node) { if (node == null) return; System.out.print(node.val + " "); preOrder(node.left); preOrder(node.right); } // 中序递归遍历 public void inOrder(BSTNode node) { if (node == null) return; inOrder(node.left); System.out.print(node.val + " "); inOrder(node.right); } // 后序递归遍历 public void postOrder(BSTNode node) { if (node == null) return; postOrder(node.left); postOrder(node.right); System.out.print(node.val + " "); } // 前序非递归遍历 public void preOrderNonRecursive() { if (root == null) return; Stack<BSTNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { BSTNode curr = stack.pop(); System.out.print(curr.val + " "); if (curr.right != null) stack.push(curr.right); if (curr.left != null) stack.push(curr.left); } } // 中序非递归遍历 public void inOrderNonRecursive() { if (root == null) return; Stack<BSTNode> stack = new Stack<>(); BSTNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); System.out.print(curr.val + " "); curr = curr.right; } } // 层次遍历 public void levelOrder() { if (root == null) return; Queue<BSTNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { BSTNode curr = queue.poll(); System.out.print(curr.val + " "); if (curr.left != null) queue.offer(curr.left); if (curr.right != null) queue.offer(curr.right); } } // 获取根节点 public BSTNode getRoot() { return root; } // 测试主方法 public static void main(String[] args) { int[] arr = {5, 3, 7, 2, 4, 6, 8}; BinarySortTree bst = new BinarySortTree(); for (int num : arr) { bst.insert(num); } System.out.println("前序递归遍历："); bst.preOrder(bst.getRoot()); // 5 3 2 4 7 6 8 System.out.println("\n中序递归遍历（有序）："); bst.inOrder(bst.getRoot()); // 2 3 4 5 6 7 8 System.out.println("\n层次遍历："); bst.levelOrder(); // 5 3 7 2 4 6 8 } }