Java-二叉排序树

Java实现二叉排序树BST创建、遍历与节点删除一、二叉排序树概述二叉排序树Binary Sort Tree也叫二叉搜索树BST是一种具有以下特性的二叉树若左子树不为空则左子树上所有节点的值均小于它的根节点的值若右子树不为空则右子树上所有节点的值均大于它的根节点的值左、右子树也分别为二叉排序树二叉排序树的中序遍历结果为升序序列这是其核心特性之一。本文通过Java实现二叉排序树的创建、四种遍历方式先序、中序、后序、层序以及节点删除功能拆解核心逻辑。二、代码结构总览整个实现分为3个核心类均放在tree包下类名作用TreeNode定义二叉树节点的结构包含数据域和左右子节点引用BinaryTree实现二叉排序树的创建、遍历、节点查找与删除等核心逻辑Test测试类实例化二叉树并验证各功能的正确性三、核心类详解3.1 节点类TreeNode该类用于描述二叉树的单个节点包含数据域和左右子节点的引用通过构造方法初始化节点值。packagetree;publicclassTreeNode{// 节点存储的数据整型publicIntegerdata;// 左子节点引用publicTreeNodeleftNode;// 右子节点引用publicTreeNoderightNode;// 构造方法创建节点时初始化数据域publicTreeNode(Integerx){this.datax;}}关键说明数据类型使用Integer而非int便于处理空值场景成员变量设为public是为了简化课堂演示中的访问逻辑实际开发中建议封装为private提供get/set方法。3.2 二叉树核心类BinaryTree该类封装了二叉排序树的核心操作包括创建树、遍历、节点查找与删除。3.2.1 成员变量// 根节点引用作为整个二叉树的入口publicTreeNoderoot;3.2.2 创建二叉排序树createBinaryTree核心逻辑从根节点开始根据待插入值与当前节点值的大小关系向左/右子树遍历找到空位置后插入新节点。publicvoidcreateBinaryTree(Integerx){// 1. 创建新节点TreeNodenewNodenewTreeNode(x);// 2. 若根节点为空新节点直接作为根节点if(rootnull){rootnewNode;return;}// 3. 临时指针从根节点开始遍历TreeNodecurroot;while(cur!null){if(xcur.data){// 插入值小于当前节点走左子树if(cur.leftNode!null){curcur.leftNode;// 左子节点非空继续向左遍历}else{cur.leftNodenewNode;// 左子节点为空插入新节点return;}}else{// 插入值大于等于当前节点走右子树if(cur.rightNode!null){curcur.rightNode;// 右子节点非空继续向右遍历}else{cur.rightNodenewNode;// 右子节点为空插入新节点return;}}}}关键说明插入规则左小右大保证二叉排序树的特性循环终止条件找到空的左/右子节点位置插入后直接return避免无效遍历。3.2.3 二叉树遍历四种方式遍历的核心是访问节点的顺序二叉树的遍历分为深度优先先序、中序、后序和广度优先层序两类。1先序遍历根→左→右递归实现先访问当前节点再递归遍历左子树最后递归遍历右子树。publicvoidbeforeOrder(TreeNodetreeNode){if(treeNodenull){// 递归终止条件节点为空return;}System.out.println(treeNode.data);// 访问根节点beforeOrder(treeNode.leftNode);// 遍历左子树beforeOrder(treeNode.rightNode);// 遍历右子树}2中序遍历左→根→右递归实现先递归遍历左子树再访问当前节点最后递归遍历右子树二叉排序树的中序遍历为升序。publicvoidmiddleOrder(TreeNodetreeNode){if(treeNodenull){return;}middleOrder(treeNode.leftNode);// 遍历左子树System.out.println(treeNode.data);// 访问根节点middleOrder(treeNode.rightNode);// 遍历右子树}3后序遍历左→右→根递归实现先递归遍历左子树再递归遍历右子树最后访问当前节点。publicvoidafterOrder(TreeNodetreeNode){if(treeNodenull){return;}afterOrder(treeNode.leftNode);// 遍历左子树afterOrder(treeNode.rightNode);// 遍历右子树System.out.println(treeNode.data);// 访问根节点}4层序遍历广度优先借助Queue队列实现按层级从上到下、从左到右访问节点。publicvoidlevelOrder(){QueueTreeNodequeuenewLinkedList();queue.offer(root);// 根节点入队while(!queue.isEmpty()){rootqueue.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(rootnull){System.out.println(树为空);returnnull;}if(node.datatarget){// 找到目标节点returnnode;}elseif(node.datatarget){// 目标值更小向左子树查找if(node.leftNodenull){returnnull;}returnfind(node.leftNode,target);}else{// 目标值更大向右子树查找if(node.rightNodenull){returnnull;}returnfind(node.rightNode,target);}}辅助方法2查找目标节点的父节点递归查找值为target的节点的父节点返回父节点引用未找到返回null。publicTreeNodefindParent(TreeNodenode,inttarget){if(rootnull){System.out.println(树为空);returnnull;}// 当前节点是目标节点的父节点左/右子节点匹配if((node.leftNode!nullnode.leftNode.datatarget)||(node.rightNode!nullnode.rightNode.datatarget)){returnnode;}else{if(node.leftNode!nullnode.datatarget){// 向左子树找returnfindParent(node.leftNode,target);}elseif(node.rightNode!nullnode.datatarget){// 向右子树找returnfindParent(node.rightNode,target);}else{returnnull;// 无父节点如根节点或未找到}}}辅助方法3查找右子树的最小值节点用于“有左右子树的节点删除”场景用右子树的最小值节点替换待删除节点再删除该最小值节点。publicintfindRightTreeMin(TreeNodenode){TreeNodecurnode;// 二叉排序树的最小值在左子树最深处while(cur.leftNode!null){curcur.leftNode;}delete(node,cur.data);// 删除找到的最小值节点returncur.data;}核心删除方法delete分三种场景处理待删除节点是叶子节点无左右子树待删除节点有一个子树左子树或右子树待删除节点有两个子树用右子树最小值节点替换。publicvoiddelete(TreeNodenode,inttarget){// 场景0树为空if(nodenull){System.out.println(树为null);return;}// 场景0.1树只有一个节点根节点if(node.leftNodenullnode.rightNodenull){nodenull;return;}// 1. 查找待删除节点TreeNodetargetNodefind(node,target);if(targetNodenull){System.out.println(没有找到该节点);return;}// 2. 查找待删除节点的父节点TreeNodeparentNodefindParent(node,target);// 场景1待删除节点是叶子节点if(targetNode.leftNodenulltargetNode.rightNodenull){// 判断是父节点的左/右子节点置空对应引用if(parentNode.leftNode!nullparentNode.leftNode.datatarget){parentNode.leftNodenull;}elseif(parentNode.rightNode!nullparentNode.rightNode.datatarget){parentNode.rightNodenull;}}// 场景2待删除节点有左右两个子树elseif(targetNode.leftNode!nulltargetNode.rightNode!null){// 用右子树最小值替换当前节点值targetNode.datafindRightTreeMin(targetNode.rightNode);}// 场景3待删除节点只有一个子树左或右else{if(targetNode.leftNode!null){// 有左子树if(parentNode.leftNode.datatarget){// 是父节点的左子节点parentNode.leftNodetargetNode.leftNode;}else{// 是父节点的右子节点parentNode.rightNodetargetNode.leftNode;}}else{// 有右子树if(parentNode.leftNode.datatarget){// 是父节点的左子节点parentNode.leftNodetargetNode.rightNode;}else{// 是父节点的右子节点parentNode.rightNodetargetNode.rightNode;}}}}关键说明场景3中需先判断待删除节点是父节点的左/右子节点再将父节点的对应引用指向待删除节点的子节点场景2中替换值后需删除右子树的最小值节点避免重复。3.3 测试类Test实例化二叉树插入节点并验证遍历、删除等功能。packagetree;publicclassTest{publicstaticvoidmain(String[]args){BinaryTreebinaryTreenewBinaryTree();// 插入节点构建二叉排序树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五、注意事项本文代码为课堂演示版本成员变量使用public简化访问实际开发中需遵循封装原则privateget/set二叉排序树的删除逻辑是核心难点需重点理解“双子女节点”的替换策略也可选择左子树最大值替换若插入的节点值重复当前代码会将其放入右子树x cur.data走左否则走右可根据需求调整重复值的处理逻辑递归遍历的终止条件是node null需避免空指针异常层序遍历修改了root变量的引用root queue.poll()实际开发中建议使用临时变量避免破坏原根节点引用。