1. 什么是二叉排序树

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

2.代码实现

package com.qin.binarysorttree; //二叉排序树 public class BinarySortTreeDemo { public static void main(String[] args) { int[] arr = {7,3,10,12,5,1,9,2}; BinarySortTree binarySortTree = new BinarySortTree(); //循环的添加节点到这个二叉排序树 for (int i = 0; i < arr.length ; i++) { binarySortTree.add(new Node(arr[i])); } System.out.println("删除前中序遍历"); //中序遍历二叉排序树 binarySortTree.infixOrder(); //1 2 3 5 7 9 10 12 System.out.println("====================="); //测试一下删除叶子结点 binarySortTree.delNode(7); System.out.println("删除后中序遍历"); //中序遍历二叉排序树 binarySortTree.infixOrder(); //1 3 5 7 9 10 12 } } //创建二叉排序树 class BinarySortTree{ private Node root; //添加节点的方法 public void add(Node node){ if (root==null){ root = node; //如果root为空，则直接让root指向node }else { root.add(node); } } //中序遍历 public void infixOrder(){ if (root!=null){ root.infixOrder(); }else { System.out.println("当前二叉排序树是空的，无法遍历"); } } //查找要删除的节点 public Node search(int value){ if (root == null){ return null; }else { return root.search(value); } } //查找父节点 public Node searchParent(int value){ if (root == null){ return null; }else { return root.searchParent(value); } } //删除节点（核心） public void delNode(int value){ if (root == null){ return; }else { //1.找到需要删除的节点targetNode Node targetNode = search(value); //如果没有找到要删除的节点，那就直接gg if (targetNode==null){ return; } //如果我们发现targetNode是root节点 if (root.left==null&&root.right==null){ root = null; return; } //去找到targetNode的父节点 Node parent = searchParent(value); //如果删除的节点是叶子节点 if (targetNode.left==null && targetNode.right==null){ //判断targetNode是父节点的左子树还是右子树 if (parent.left!=null && parent.left.value==value){ //说明是父节点的左子节点 parent.left = null; }else if (parent.right!=null && parent.right.value==value){ 说明是父节点的右子节点 parent.right = null; } }else if(targetNode.left!=null && targetNode.right!=null){ //删除有两颗子树的节点 int minVal = delRightTreeMin(targetNode.right); targetNode.value = minVal; }else { //删除只有一颗子树的节点 //如果被删除的节点有左子节点 if (targetNode.left!=null){ if (parent!=null){ //如果被删除的节点是父节点的的左子节点 if (parent.left.value==targetNode.value){ parent.left = targetNode.left; }else { //说明被删除的节点是父节点的右子节点 parent.right = targetNode.left; } }else { root = targetNode.left; } }else { //如果被删除的节点有右子节点 if (parent!=null){ //如果被删除的节点是父节点的的左子节点 if (parent.left.value==targetNode.value){ parent.left = targetNode.right; }else { //说明被删除的节点是父节点的右子节点 parent.right = targetNode.right; } }else { root = targetNode.right; } } } } } //node 传入的节点（当做二叉排序树的跟节点） // 返回的是以node为跟节点的二叉排序树的最小值 // 删除node为跟节点的最小节点 public int delRightTreeMin(Node node){ Node temp = node; //循环的查找左节点，就会找到最小值 while (temp.left!=null){ temp = temp.left; } //这是temp就指向了最小节点 //删除最小节点 delNode(temp.value); return temp.value; } } //创建node节点 class Node{ int value; Node left; Node right; public Node(int value) { this.value = value; } @Override public String toString() { return "Node{" + "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(); } } //查找要删除的节点 //value 希望删除节点的值 //如果找到就返回该节点，找不到就返回空 public Node search(int value){ if (value==this.value){ //说明就是这个节点 return this; }else if (value < this.value){ //如果查找的值小于当前的值，向左子树递归查找 //如果左子节点为空 if (this.left==null){ return null; } return this.left.search(value); }else { //如果查找的值不小于当前的值，向左子树递归查找 if (this.right==null){ return null; } return this.right.search(value); } } //查找要删除节点的父节点 //value 要找的节点的值 //返回要删除节点的父节点，如果没有就返回null public Node searchParent(int value){ if((this.left != null && this.left.value == value)|| (this.right != null && this.right.value == value)){ return this; //上面的判断说明当前节点就是要删除节点的父节点 }else { //如果查找的值小于当前节点的值,且不为空，那么向左递归 if (this.value>value && this.left!=null){ return this.left.searchParent(value); }else if (this.value<=value && this.right!=null){ return this.right.searchParent(value); }else { return null; //没有找到父节点 } } } } 结果