二叉排序树的插入、先序/中序/后序/层次遍历、节点查询

一、概念

二叉排序树（也叫二叉搜索树）是一种基于 “左小右大” 规则的有序二叉树

特点：

• 左子节点的值小于父节点的值
• 右子节点的值大于父节点的值
• 每个节点由 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. 新建（插入节点）

插入节点的逻辑遵循 “左小右大” 的规则，步骤如下：

1. 若树为空（root == null），新节点直接作为根节点；
2. 若树非空，循环判断新节点与当前节点的大小：
   • 新节点值大于当前节点：向右子树查找，直到右子节点为空，插入新节点；
   • 新节点值小于 / 等于当前节点：向左子树查找，直到左子节点为空，插入新节点。

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); } }