二叉排序树基本介绍：BST（BinarySort(Search)Tree），对于二叉排序树的任意一个非叶子节点，其左节点为需要的值，小于当前节点的值，右节点的值大于当前节点的值。**特别说明：**如果有相同的值，可以将该节点放在左子节点或右子节点。例如对于数据{7,3,10,12,5,1,9}，对应的二叉排序树为：二叉排序树删除节点二叉排序树的删除比较复杂，如图下面，需要考虑以下三种情况，1、要删除叶子节点（如：2、5、9、12），需要找到需要删除的节点targetNode，找到targetNode的父节点parentNode（考虑是否有父节点）判断targetNode是parentNode的左子节点还是右子节点，根据之前删除，左子节点=>parent.left=null，右子节点=>parent.right=空；2、删除只有一个子树的节点（例如：1），需要先找到要删除的节点targetNode，找到targetNode的父节点parentNode（考虑是否有父节点），确定childtargetNode的节点是左子节点还是右子节点决定targetNode是parentNode的左子节点还是右子节点如果targetNode是parentNode的左子节点：targetNode的子节点是左子节点,那么子节点parentNode.left=targetNode.left子节点,那么,parentNode.left=targetNode.right;如果targetNode是parentNode的右子节点：targetNode的子节点是左子节点，那么parentNode.right=targetNode.lefttargetNode的子节点是右子节点，那么，parentNode.right=targetNode.right3。删除一个有两个子树的节点（比如：7,3,10），需要先找到要删除的节点targetNode，从右孩子中找到targetNode的父节点parentNode（考虑是否有父节点）的targetNode树找到最小节点，用一个临时变量将右子树最小节点的值保存到temp中，删除右子树最小节点，然后，targetNode.value=temp;如果从左子树开始查找，只需替换左子树的最大值代码示例：packagecom.xie.bst；publicclassBinarySortTreeDemo{publicstaticvoidmain(String[]args){int[]arr={7,3,10,12,5,1,9,2};BinarySortTreebinarySortTree=newBinarySortTree();for(inti:arr){binarySortTree.add(newNode(i));}System.out.println("中序遍历二叉排序树~");binarySortTree.infixOrder();System.out.println("测试删除叶子节点");binarySortTree.delNode(10);System.out.println("删除节点后");binarySortTree.infixOrder();}}classBinarySortTree{privateNoderoot;//找到待删除节点的父节点publicNodesearchParent(Nodenode){if(root!=null){returnroot.searchParent(node);}else{returnnull;}}//找到要删除的节点publicNodesearch(intvalue){if(root==null){returnnull;}else{returnroot.search(value);}}/***找到以node为根的二叉排序树的最小值，删除以node为根的二叉排序树的最小节点**@paramnode传入节点（作为二进制的根节点thesortingtree)*@return返回以node为根节点的二叉排序树的最小节点值*/publicintdelRightTreeMin(Nodenode){Nodetarget=node;//循环寻找左节点while(target.left!=null){target=target.left;}//删除最小节点delNode(target.value);returntarget.value;}/***找到以节点为根的二叉排序树的最大值，并删除该节点的根节点二叉排序树的最大节点为该点的值**@paramnode传入节点（作为二叉排序树的根节点）*@return返回以node为根节点的二叉排序树的最大节点值*/publicintdelLeftTreeMax(Nodenode){Nodetarget=node;while(target.right!=null){target=target.right;}//删除最大节点delNode(target.value);returntarget.value;}//删除节点publicvoiddelNode(intvalue){if(root==null){return;}else{NodetargetNode=search(value);if(targetNode==null){return;}if(targetNode==root){root=null;return;}NodeparentNode=searchParent(targetNode);if(targetNode.left==null&&targetNode.right==null){//如果要删除的节点是叶子节点if(parentNode.left!=null&&parentNode.left.value==targetNode.value){parentNode.left=null;}if(parentNode.right!=null&&parentNode.right.value==targetNode.value){parentNode.right=null;}}elseif(targetNode.left!=null&&targetNode.right!=null);{//如果要删除的节点是有两个子树的节点intminValue=ofMinRightTree(targetNode.right);targetNode.value=minValue;//删除上下码的效果是一样的//intmaxValue=delLeftTreeMax(targetNode.left);//targetNode.value=maxValue;}else{//要删除的节点是相同的只有左子节点if(targetNode.left!=null){if(parentNode!=null){if(parentNode.left==targetNode){parentNode.left=targetNode.left;}else{parentNode.right=targetNode.left;}}else{//如果父节点为空，让root转置root=targetNode.left;}}else{//要删除的节点只有右子节点if(parentNode!=null){if(parentNode.left==targetNode){parentNode.left=targetNode.right;}else{parentNode.right=targetNode.right;}}else{//如果父节点为空，让root转置root=targetNode.right;}}}}}//添加节点publicvoidadd(Nodenode){if(root==null){root=node;}else{root.add(node);}}//中序遍历publicvoidinfixOrder(){if(root!=null){root.infixOrder();}else{System.out.println("二进制排序为空，无法遍历");}}}classNode{intvalue;Nodeleft;Noderight;publicNode(intvalue){this.value=value;}/***找到要删除的节点的父节点**@paramnode要删除的节点*@return要删除的节点的父节点*/publicNodesearchParent(Nodenode){//如果当前节点是pare待删除节点的nt节点，返回if((this.left!=null&&this.left.value==node.value)||(this.right!=null&&this.right.value==node.value)){returnthis;}else{if(this.left!=null&&node.value
