二叉排序樹(shù)（Binary Sort Tree）嬉挡，又稱(chēng)二叉查找樹(shù)，二叉搜索樹(shù)
二叉排序樹(shù)或者是一棵空樹(shù)骆姐，或者是具有下列性質(zhì)的二叉樹(shù)
1）若左子樹(shù)不空滤钱，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于或等于它的根結(jié)
2）若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值
3）左斩萌、右子樹(shù)也分別為二叉排序樹(shù)缝裤；

代碼實(shí)現(xiàn)：

package tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉排序樹(shù)
 * @author SUJiannan
 * 定義：二叉排序樹(shù)或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)： 
    （1）若左子樹(shù)不空颊郎，則左子樹(shù)上所有結(jié)點(diǎn)的鍵值均小于或等于它的根結(jié)點(diǎn)的鍵值倘是； 
    （2）若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的鍵值均大于或等于它的根結(jié)點(diǎn)的鍵值袭艺； 
    （3）左搀崭、右子樹(shù)也分別為二叉排序樹(shù)；
 */
public class BinarySearchTree {

    private Node root; 
    
    // 查找
    public Node get(Value value){
        return get(value,this.root);
    }
    public Node get(Value value, Node node){
        if(value == null) {
            return null;
        }
        int cmp = node.value.compareTo(value);
        if(cmp > 0) {
            return get(value,node.left);
        } else if (cmp < 0) {
            return get(value,node.right);
        } else {
            return node;
        }
    }
    
    
    // 插入
    public boolean insert(Value n){
        boolean bool = insert(this.root,n);
        //this.root = insert2(this.root,n); //方法2
        return bool;
    }
    public boolean insert(Node node, Value val){
        if(this.root== null ) { 
            this.root = new Node(val);
            return true; 
        } else {
            // 小于等于
            if(node.value.compareTo(val) > 0) {
                // 沒(méi)有左子樹(shù)
                if(node.left == null) {
                    node.left =  new Node(val); 
                    return true;
                } else {
                    return insert(node.left,val);
                } 
            } else if(node.value.compareTo(val) < 0){
                // 沒(méi)有右子樹(shù)
                if(node.right == null) {
                    node.right =  new Node(val); 
                    return true;
                } else {
                    return insert(node.right,val);
                } 
            } else {
                // 重復(fù)插入 失敗
                return false;
            }
        }
    }
    
    // 插入方法2
//  public Node insert2(Node node, Value val){
//      if(node == null ) { 
//          node = new Node(val);
//          return node; 
//      }
//      int cmp = val.compareTo(node.value);
//      if(cmp > 0) {
//          node.right = insert2(node.right,val);
//      } else if(cmp < 0) {
//          node.left = insert2(node.left,val);
//      } else {
//          // 重復(fù)插入 不作操作
//      }
//      return node;
//  }
    
    // 刪除
    public boolean delete(Value n){
        delete(this.root,n);
        return true;
    }
    private Node delete(Node node, Value value) {
        //先查找猾编，后刪除
        if(node == null) {
            return null;
        }
        int cmp = value.compareTo(node.value);
        if(cmp > 0) {
            node.right = delete(node.right,value);
        } else if(cmp < 0) {
            node.left = delete(node.left,value);
        } else {
            // 找到value瘤睹，刪除操作
            if(node.left == null && node.right == null) {
                node = null;
            } else if (node.left != null && node.right == null) {
                node = node.left;
            } else if (node.left == null && node.right != null) {
                node = node.right;
            } else {
                Node nNode = node.left;
                // 1.找到當(dāng)前node的左子樹(shù)的最大值
                while(nNode.right != null) {
                    nNode = nNode.right;
                }
                // 2.替換
                node.value = nNode.value;
                // 3.刪除左子樹(shù)最大值的node
                node.left = delete(node.left, nNode.value);
            }
        }
        return node; 
    }
    @Override
    public String toString() {
        List<Value> list = new ArrayList<Value>();
        printInOrderRe(this.root,list);
        return list.toString();
    }
    // 中序遍歷
    private void printInOrderRe(Node node, List list) {
        if(node != null) {
            printInOrderRe(node.left,list);
            list.add(node.value);
            printInOrderRe(node.right,list);
        }
    }
    
    public static void main(String[] args) {
        BinarySearchTree b = new BinarySearchTree();
        b.insert(new Value(1));
        b.insert(new Value(-20));
        b.insert(new Value(18));
        b.insert(new Value(52));
        b.insert(new Value(12));
        b.insert(new Value(-8));
        b.insert(new Value(-11));
        System.out.println(b);
        Node node18 = b.get(new Value(18));
        System.out.println(node18.value);
        Node node1 = b.get(new Value(1));
        System.out.println(node1.value);
        b.delete(new Value(18));
        System.out.println(b);
        b.delete(new Value(1));
        System.out.println(b);
        b.delete(new Value(52));
        System.out.println(b);
        System.out.println(b.root.value);
    }
    public Node getRoot() {
        return root;
    }
    public void setRoot(Node root) {
        this.root = root;
    }
}
class Value implements Comparable<Value>{

    private int value;
    public Value(int value) {
        this.value = value;
    }
    @Override
    public int compareTo(Value o) {
        return (this.value - o.value);
    }
    @Override
    public String toString() {
        return "" + value;
    }
}

class Node {
    public Value value;//值
    public Node left, right;
    public Node(Value value, Node left, Node right) {
        super();
        this.value = value;
        this.left = left;
        this.right = right;
    }
    public Node(Value value) {
        this.value = value;
    }
}