Java数据结构：二叉排序树（BST）

一、基本介绍

• 二叉排序树 BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。二叉排序树是数据结构中的一类。在一般情况下，查询效率比链表结构要高。
• 比如，下面就是一颗二叉排序树：

二、创建一颗二叉树

• 1.以上面的图的二叉排序树为例，首先创建一个节点类

 //节点类
class Node{
 public int value; 
 public Node left; //左节点
 public Node right; //右节点
 @Override
 public String toString() {
    return "Node [value=" + value + "]";
  }
 public Node(int value) {
    super();
    this.value = value;
 }

//添加方法
public void add(Node node) {
    if(this.value > node.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);
        }
    }
}   
}

• 2.然后创建一个二叉排序树类

  class BinarySortTree{
   public Node root; //根节点
  
   public void addNode(Node node) {
    if(this.root == null) {
        this.root = node;
    }else {
        root.add(node);
    }       
       }        
   }
  }
  

• 3.接下来只需要在main方法中调用BinarySortTree中的addNode方法就可以创建一颗二叉排序树了：

      public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9};
        BinarySortTree tree = new BinarySortTree();
        for(int a : arr) {
            Node node = new Node(a);
            tree.addNode(node);
        }
        tree.deleteNode(7);
   
    }
  

• 4.而仅仅是创建还是不够的，我们还需要遍历树的方法，这里选用的是中序遍历
  节点类中添加中序遍历方法：

 //中序遍历
public void midOrder() {
    if(this.left != null) {
        this.left.midOrder();
    }
    
    System.out.println(this);
    
    if(this.right != null) {
        this.right.midOrder();
    }
}

然后再到BinarySortTree类中添加根节点的遍历：

    public void midOrder() {
        this.root.midOrder();       
  }

再到main方法中调用输出结果：
1 -》3 -》5 -》7 -》9 -》10 -》12

三、删除一个节点

删除需要三种情况来考虑，

• 被删除的节点为叶子节点：先找到当前节点的父节点，然后把指向被删除节点的指针赋为空；
• 被删除的节点有一个子节点：先找到当前节点的父节点，然后把指向被删除节点的指针指向被删除节点的子节点；
• 被删除的节点有两个子节点：这个稍微有点复杂，先找到当前节点的父节点，然后把指向被删除节点的指针指向被删除节点的右子节点，再把被删除节点的左子节点通过addNode方法添加到被删除右子节点的下面。

代码：
节点类中：

    //删除方法
public void delete(int value,Node node1) {
    if(this.value > value && this.left != null) {           
        this.left.delete(value,node1);  
    }else if(this.value < value && this.right != null) {
        this.right.delete(value,node1);
    }else if(this.value == value) {
        Node node = node1;
        
        //1.当节点为叶子节点时
        if(node != null) {
        if(this.right == null && this.left == null) {
            if(node.value > value) {
                node.left = null;
            }else if(node.value <= value){
                node.right = null;
            }
        }
        //2.当节点为带单子节点时
        else if(this.right != null && this.left == null) {              
            if(node.value > value) {
                node.left = this.right;
            }else if(node.value <= value){
                node.right = this.right;
            }               
        }else if(this.left != null && this.right == null) {
            if(node.value > value) {
                node.left = this.left;
            }else if(node.value <= value){
                node.right = this.left;
            }   
        }
        //3.当节点有左右节点时
        else if(this.right != null && this.left != null){
            Node temp = null;
            if(node.value > value) {                    
                node.left = this.right;                     
                this.right.add(this.left);
            }else if(node.value <= value){                  
                node.right = this.right;
                this.right.add(this.left);
            }   
        }
        }
    }
}

//查询父节点
public Node findParent(int value) {
    if(this.value > value && this.left != null) {   
       if(this.left.value == value && this.left != null){
            return this;
        }else {
            return this.left.findParent(value);
        }
    }else if(this.value < value && this.right != null) {
          if(this.right.value == value){
                return this;
            }else {
                return this.right.findParent(value);    
            }
    }else {     
        return null;
    }

}

BinarySortTree中

        public void deleteNode(int value) {
    if(this.root.value == value) {                  
            //1.当节点为叶子节点时               
            if(this.root.right == null && this.root.left == null) {
                this.root = null;
            }
            //2.当节点为带单子节点时
            else if(this.root.right != null && this.root.left == null) {                                    
                this.root = this.root.right;            
            }else if(this.root.left != null && this.root.right == null) {
                this.root = this.root.left;
            }
            //3.当节点有左右节点时
            else if(this.root.right != null && this.root.left != null){                                                             
                    this.root.right.add(this.root.left);    
                    this.root = this.root.right;            
            }
            this.root.midOrder();
            }else {         
              root.delete(value,this.root.findParent(value));
              root.midOrder();
    }
}