二叉排序树java实现

二叉排序树（Binary Sort Tree），又称二叉查找树，二叉搜索树
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树
1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结
2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
3）左、右子树也分别为二叉排序树；

代码实现：

package tree;

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

/**
 * 二叉排序树
 * @author SUJiannan
 * 定义：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： 
    （1）若左子树不空，则左子树上所有结点的键值均小于或等于它的根结点的键值； 
    （2）若右子树不空，则右子树上所有结点的键值均大于或等于它的根结点的键值； 
    （3）左、右子树也分别为二叉排序树；
 */
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) {
                // 没有左子树
                if(node.left == null) {
                    node.left =  new Node(val); 
                    return true;
                } else {
                    return insert(node.left,val);
                } 
            } else if(node.value.compareTo(val) < 0){
                // 没有右子树
                if(node.right == null) {
                    node.right =  new Node(val); 
                    return true;
                } else {
                    return insert(node.right,val);
                } 
            } else {
                // 重复插入 失败
                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 {
//          // 重复插入 不作操作
//      }
//      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.找到当前node的左子树的最大值
                while(nNode.right != null) {
                    nNode = nNode.right;
                }
                // 2.替换
                node.value = nNode.value;
                // 3.删除左子树最大值的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;
    }
}