Java-二叉排序树

Java实现二叉排序树（BST）：创建、遍历与节点删除

一、二叉排序树概述

二叉排序树（Binary Sort Tree，也叫二叉搜索树BST）是一种具有以下特性的二叉树：

• 若左子树不为空，则左子树上所有节点的值均小于它的根节点的值；
• 若右子树不为空，则右子树上所有节点的值均大于它的根节点的值；
• 左、右子树也分别为二叉排序树；
• 二叉排序树的中序遍历结果为升序序列，这是其核心特性之一。

本文通过Java实现二叉排序树的创建、四种遍历方式（先序、中序、后序、层序）以及节点删除功能，拆解核心逻辑。

二、代码结构总览

整个实现分为3个核心类，均放在tree包下：

三、核心类详解

3.1 节点类：TreeNode

该类用于描述二叉树的单个节点，包含数据域和左右子节点的引用，通过构造方法初始化节点值。

packagetree;publicclassTreeNode{// 节点存储的数据（整型）publicIntegerdata;// 左子节点引用publicTreeNodeleftNode;// 右子节点引用publicTreeNoderightNode;// 构造方法：创建节点时初始化数据域publicTreeNode(Integerx){this.data=x;}}

关键说明：

• 数据类型使用Integer而非int，便于处理空值场景；
• 成员变量设为public是为了简化课堂演示中的访问逻辑（实际开发中建议封装为private，提供get/set方法）。

3.2 二叉树核心类：BinaryTree

该类封装了二叉排序树的核心操作，包括创建树、遍历、节点查找与删除。

3.2.1 成员变量

// 根节点引用，作为整个二叉树的入口publicTreeNoderoot;

3.2.2 创建二叉排序树：createBinaryTree

核心逻辑：从根节点开始，根据待插入值与当前节点值的大小关系，向左/右子树遍历，找到空位置后插入新节点。

publicvoidcreateBinaryTree(Integerx){// 1. 创建新节点TreeNodenewNode=newTreeNode(x);// 2. 若根节点为空，新节点直接作为根节点if(root==null){root=newNode;return;}// 3. 临时指针，从根节点开始遍历TreeNodecur=root;while(cur!=null){if(x<cur.data){// 插入值小于当前节点，走左子树if(cur.leftNode!=null){cur=cur.leftNode;// 左子节点非空，继续向左遍历}else{cur.leftNode=newNode;// 左子节点为空，插入新节点return;}}else{// 插入值大于等于当前节点，走右子树if(cur.rightNode!=null){cur=cur.rightNode;// 右子节点非空，继续向右遍历}else{cur.rightNode=newNode;// 右子节点为空，插入新节点return;}}}}

关键说明：

• 插入规则：左小右大，保证二叉排序树的特性；
• 循环终止条件：找到空的左/右子节点位置，插入后直接return，避免无效遍历。

3.2.3 二叉树遍历（四种方式）

遍历的核心是访问节点的顺序，二叉树的遍历分为深度优先（先序、中序、后序）和广度优先（层序）两类。

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

递归实现，先访问当前节点，再递归遍历左子树，最后递归遍历右子树。

publicvoidbeforeOrder(TreeNodetreeNode){if(treeNode==null){// 递归终止条件：节点为空return;}System.out.println(treeNode.data);// 访问根节点beforeOrder(treeNode.leftNode);// 遍历左子树beforeOrder(treeNode.rightNode);// 遍历右子树}

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

递归实现，先递归遍历左子树，再访问当前节点，最后递归遍历右子树（二叉排序树的中序遍历为升序）。

publicvoidmiddleOrder(TreeNodetreeNode){if(treeNode==null){return;}middleOrder(treeNode.leftNode);// 遍历左子树System.out.println(treeNode.data);// 访问根节点middleOrder(treeNode.rightNode);// 遍历右子树}

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

递归实现，先递归遍历左子树，再递归遍历右子树，最后访问当前节点。

publicvoidafterOrder(TreeNodetreeNode){if(treeNode==null){return;}afterOrder(treeNode.leftNode);// 遍历左子树afterOrder(treeNode.rightNode);// 遍历右子树System.out.println(treeNode.data);// 访问根节点}

（4）层序遍历（广度优先）

借助Queue队列实现，按层级从上到下、从左到右访问节点。

publicvoidlevelOrder(){Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);// 根节点入队while(!queue.isEmpty()){root=queue.poll();// 出队并访问当前节点System.out.println(root.data);// 左子节点非空则入队if(root.leftNode!=null){queue.offer(root.leftNode);}// 右子节点非空则入队if(root.rightNode!=null){queue.offer(root.rightNode);}}}

关键说明：

• 层序遍历的核心是“先进先出”的队列特性，保证按层级访问；
• 每次出队一个节点后，立即将其左右子节点入队（若存在），实现层级遍历。

3.2.4 节点删除（核心难点）

删除节点需分三种场景处理，需先实现“查找目标节点”和“查找目标节点的父节点”两个辅助方法。

辅助方法1：查找目标节点

递归查找值为target的节点，返回节点引用（未找到返回null）。

publicTreeNodefind(TreeNodenode,inttarget){if(root==null){System.out.println("树为空");returnnull;}if(node.data==target){// 找到目标节点returnnode;}elseif(node.data>target){// 目标值更小，向左子树查找if(node.leftNode==null){returnnull;}returnfind(node.leftNode,target);}else{// 目标值更大，向右子树查找if(node.rightNode==null){returnnull;}returnfind(node.rightNode,target);}}

辅助方法2：查找目标节点的父节点

递归查找值为target的节点的父节点，返回父节点引用（未找到返回null）。

publicTreeNodefindParent(TreeNodenode,inttarget){if(root==null){System.out.println("树为空");returnnull;}// 当前节点是目标节点的父节点（左/右子节点匹配）if((node.leftNode!=null&&node.leftNode.data==target)||(node.rightNode!=null&&node.rightNode.data==target)){returnnode;}else{if(node.leftNode!=null&&node.data>target){// 向左子树找returnfindParent(node.leftNode,target);}elseif(node.rightNode!=null&&node.data<target){// 向右子树找returnfindParent(node.rightNode,target);}else{returnnull;// 无父节点（如根节点）或未找到}}}

辅助方法3：查找右子树的最小值节点

用于“有左右子树的节点删除”场景：用右子树的最小值节点替换待删除节点，再删除该最小值节点。

publicintfindRightTreeMin(TreeNodenode){TreeNodecur=node;// 二叉排序树的最小值在左子树最深处while(cur.leftNode!=null){cur=cur.leftNode;}delete(node,cur.data);// 删除找到的最小值节点returncur.data;}

核心删除方法：delete

分三种场景处理：

1. 待删除节点是叶子节点（无左右子树）；
2. 待删除节点有一个子树（左子树或右子树）；
3. 待删除节点有两个子树（用右子树最小值节点替换）。

publicvoiddelete(TreeNodenode,inttarget){// 场景0：树为空if(node==null){System.out.println("树为null");return;}// 场景0.1：树只有一个节点（根节点）if(node.leftNode==null&&node.rightNode==null){node=null;return;}// 1. 查找待删除节点TreeNodetargetNode=find(node,target);if(targetNode==null){System.out.println("没有找到该节点");return;}// 2. 查找待删除节点的父节点TreeNodeparentNode=findParent(node,target);// 场景1：待删除节点是叶子节点if(targetNode.leftNode==null&&targetNode.rightNode==null){// 判断是父节点的左/右子节点，置空对应引用if(parentNode.leftNode!=null&&parentNode.leftNode.data==target){parentNode.leftNode=null;}elseif(parentNode.rightNode!=null&&parentNode.rightNode.data==target){parentNode.rightNode=null;}}// 场景2：待删除节点有左右两个子树elseif(targetNode.leftNode!=null&&targetNode.rightNode!=null){// 用右子树最小值替换当前节点值targetNode.data=findRightTreeMin(targetNode.rightNode);}// 场景3：待删除节点只有一个子树（左或右）else{if(targetNode.leftNode!=null){// 有左子树if(parentNode.leftNode.data==target){// 是父节点的左子节点parentNode.leftNode=targetNode.leftNode;}else{// 是父节点的右子节点parentNode.rightNode=targetNode.leftNode;}}else{// 有右子树if(parentNode.leftNode.data==target){// 是父节点的左子节点parentNode.leftNode=targetNode.rightNode;}else{// 是父节点的右子节点parentNode.rightNode=targetNode.rightNode;}}}}

关键说明：

• 场景3中需先判断待删除节点是父节点的左/右子节点，再将父节点的对应引用指向待删除节点的子节点；
• 场景2中替换值后，需删除右子树的最小值节点（避免重复）。

3.3 测试类：Test

实例化二叉树，插入节点并验证遍历、删除等功能。

packagetree;publicclassTest{publicstaticvoidmain(String[]args){BinaryTreebinaryTree=newBinaryTree();// 插入节点，构建二叉排序树binaryTree.createBinaryTree(5);binaryTree.createBinaryTree(3);binaryTree.createBinaryTree(7);binaryTree.createBinaryTree(1);binaryTree.createBinaryTree(4);binaryTree.createBinaryTree(6);binaryTree.createBinaryTree(9);// 先序遍历System.out.println("===== 先序遍历 =====");binaryTree.beforeOrder(binaryTree.root);// 中序遍历（升序）System.out.println("===== 中序遍历 =====");binaryTree.middleOrder(binaryTree.root);// 后序遍历System.out.println("===== 后序遍历 =====");binaryTree.afterOrder(binaryTree.root);// 层序遍历System.out.println("===== 层序遍历 =====");binaryTree.levelOrder();// 可选：测试删除节点// binaryTree.delete(binaryTree.root, 3);// System.out.println("删除节点3后的中序遍历：");// binaryTree.middleOrder(binaryTree.root);}}

四、运行结果示例

插入节点5,3,7,1,4,6,9后，各遍历结果如下：

先序遍历（根→左→右）

5 3 1 4 7 6 9

中序遍历（左→根→右，升序）

1 3 4 5 6 7 9

后序遍历（左→右→根）

1 4 3 6 9 7 5

层序遍历（按层级）

5 3 7 1 4 6 9

五、注意事项

1. 本文代码为课堂演示版本，成员变量使用public简化访问，实际开发中需遵循封装原则（private+get/set）；
2. 二叉排序树的删除逻辑是核心难点，需重点理解“双子女节点”的替换策略（也可选择左子树最大值替换）；
3. 若插入的节点值重复，当前代码会将其放入右子树（x < cur.data走左，否则走右），可根据需求调整重复值的处理逻辑；
4. 递归遍历的终止条件是node == null，需避免空指针异常；
5. 层序遍历修改了root变量的引用（root = queue.poll()），实际开发中建议使用临时变量，避免破坏原根节点引用。