二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
public class Node { int value; Node left;//左节点 Node right;//右节点 public Node(int value) { this.value = value; } /*添加节点的方法满足二叉排序树*/ public void add(Node node){ if (node==null){ return; } //判断传入节点和当前子树节点的值 if (node.value<this.value){ if (this.left ==null){//左子节点为空直接添加 this.left=node; }else { this.left.add(node);//递归左子树添加 } }else {//添加的节点大于当前节点的值 if (this.right==null){ this.right=node; }else { this.right.add(node);//递归右子树添加 } } } /*中序遍历*/ public void infixOrder(){ if (this.left!=null){ this.left.infixOrder(); } System.out.println(this); if (this.right!=null){ this.right.infixOrder(); } } /*查找要删除的节点*/ public Node search(int va1ue){ if (va1ue == this.value){ return this; }else if (va1ue<this.value){//左节点递归查找 if (this.left==null){ return null; } return this.left.search(va1ue); }else {//右子树递归查找 if (this.right==null){ return null; } return this.right.search(va1ue); } } /*查找删除节点的父节点*/ public Node searchParent(int value){ if ((this.left!=null &&this.left.value==value) ||(this.right!=null&&this.right.value==value)){ return this; }else {//如果查找的值小于当前节点，并且当前节点不为空 if (value <this.value && this.left!=null){ return this.left.searchParent(value);//左递归 }else if (value>=this.value && this.right!= null){ return this.right.searchParent(value); }else { return null; } } } @Override public String toString() { return "Node{" + "value=" + value + ‘}‘; } }
public class BinarySearchTree { private Node root; /*查找要删除的节点*/ public Node search(int va1ue){ if (root==null){ return null; }else { return root.search(va1ue); } } /*查找删除节点的父节点*/ public Node searchParent(int value){ if (root==null){ return null; }else { return root.searchParent(value); } } /** * * @description:TODO * @params:1.节点（当做二叉的根节点） * 1.删除最小节点 * @return: 当前节点作为二叉数根节点的最小节点值 * @author: 苏兴旺 * @time: 2020/3/14 12:38 */ public int delRightTree(Node node){ Node targe = node; //一直往左边找就是最小值 while (targe.left!=null){ targe = targe.left; } delNode(targe.value); //指向最小节点 return targe.value; } /*删除节点 * 1.找待删除的节点taget * 2.找到待删除节点的父节点parent * 3.确定 taget 是父节点 左节点 右节点 * 4.根据实际情况进行删除 * 左节点==null * 右节点==null * * 第二种：删除的节点只有一个子树 * 1.找待删除的节点taget * 2.找到待删除节点的父节点parent * 3.确定taget的子节点是左节点还是右子节点 * 4.taget是parent左子节点还是右子节点 * 5.如果taget有左子节点 * 5.1 如果taget是parent左节点 parent.左 = taget.左 * 5.2如果taget是parent右节点parent.右 = taget.左 * 6.如果taget有右子节点 * 6.1 如果taget是parent左节点 parent.左 = taget.右 * 6.2如果taget是parent右节点parent.右 = taget.右 * * 情况三删除有二个数的节点： *.1找待删除的节点taget * 2.找到待删除节点的父节点parent * 3.从taget 的右节点找到最小的节点 * 4.用临时变量保存保存最小节点temp * 5.删除该节点 * taget.value=temp*/ public void delNode(int value){ if (root == null){ return; }else { Node target = search(value); if (target == null){//找到删除的节点taget return; } //target 树只有一个root接电脑 if (root.left==null && root.right==null){ root=null; return; } //找到删除节点的父节点 Node parent = searchParent(value); if (target.left==null&&target.right==null){//为叶子节点 if (parent.left!=null &&parent.left.value==value){//判断target节点是父节点的左节点还是右节点 parent.left=null; }else if (parent.right!=null&& parent.right.value==value){ parent.right=null; } }else if (target.left!=null && target.right!=null){//情况三删除有二个数的节点： // 情况三删除有二个数的节点： //1.找待删除的节点taget //2.找到待删除节点的父节点parent // 3.从taget 的右节点找到最小的节点 // 4.用临时变量保存保存最小节点temp // 5.删除该节点 int minVal = delRightTree(target.right); target.value=minVal; }else {//删除的节点只有一个子树 if (target.left!=null){//如果要删除的有左子节点 if (parent.left.value==value){//target是父节点的左节点 parent.left=target.left; }else {//target是父节点的右节点 parent.right = target.left; } }else {//如果要删除的有右子节点 if (parent.left.value==value){//target是父节点的左节点 parent.left=target.right; }else {//target是父节点的右节点 parent.right=target.right; } } } } } /*添加方法*/ public void add(Node node){ if (root==null){ root = node; }else { root.add(node); } } /*中序遍历*/ public void infixOrder(){ if (root==null){ System.out.println("二叉排序树为空！！！"); }else { root.infixOrder(); } } }
public class BinarySearchTreeDemo { public static void main(String[] args) { int[] arr = {7,3,10,12,5,1,9,0}; BinarySearchTree binarySearchTree = new BinarySearchTree(); /*循环添加节点到二叉排序树*/ for (int i = 0; i < arr.length; i++) { binarySearchTree.add(new Node(arr[i])); } /*中序遍历*/ binarySearchTree.infixOrder(); /*测试删除叶子节点*/ //binarySearchTree.delNode(2); //binarySearchTree.delNode(5); binarySearchTree.delNode(10); System.out.println("删除后"); binarySearchTree.infixOrder(); } }
原文：https://www.cnblogs.com/sxw123/p/12804410.html