package com.test.tree;

public class BinarySearchTree<T extends Comparable<? super T>> {
    /*定义二叉树的节点*/
    private class BinaryNode<T>{
        public T data;
        public BinaryNode<T> lt;
        public BinaryNode<T> rt;
        
        public BinaryNode(T data) {
            this(data, null, null);
        }
        public BinaryNode(T data, BinaryNode<T> lt, BinaryNode<T> rt) {
            this.data =http://www.mamicode.com/ data;
            this.lt = lt;
            this.rt = rt;
        }
    }
    
    private BinaryNode<T> root; //定义二叉查找树的根节点
    
    public BinarySearchTree(){ //初始化二叉查找树
        root = null;
    }
    
    public void makeEmpty(){ //树清空
        root = null;
    }
    
    public boolean isEmpty(){ //树判空
        return root == null;
    }
    
    public boolean contains(T x){ //判断是否包含某个值
        return contains(root, x);
    }
    public boolean contains(BinaryNode<T> root, T x){
        if(root == null){
            return false;
        }
        int compare = x.compareTo(root.data);
        if(compare == 0){
            return true;
        }else if(compare < 0){
            contains(root.lt, x);
        }else {
            contains(root.rt, x);
        }
        return false;
    }
    
    public T findMin(){ //获得树中最小值
        if(!isEmpty()){
            return findMin(root).data;
        }
        return null;
    }
    public T findMax(){ //获得树中最大值
        if(!isEmpty()){
            return findMax(root).data;
        }
        return null;
    }
    
    public void insert(T data){ //插入数据
        root = insert(data, root);
    }
    
    public void remove(T data){
        root = remove(data, root);
    }
    
    public void printTree(){
        if(root == null){
            System.out.println("empty tree");
        }else{
            printTree(root);
        }
    }
    /*中序遍历*/
    public void printTree(BinaryNode<T> t){
        if(t != null){
            printTree(t.lt);
            System.out.print(t.data+"、");
            printTree(t.rt);
        }
    }
    /**
     * 删除查找树的某个节点，首先用要删除节点的右子树中最小值替换节点值，
     * 再从右子树中删除此节点，递归调用
     * */
    public BinaryNode<T> remove(T data, BinaryNode<T> t){
        if(t == null){
            return t;
        }
        int compare = data.compareTo(t.data);
        
        if(compare < 0){
            //插入值比根节点的值小，插入到左字数
            t.lt = remove(data, t.lt);
        }else if(compare > 0){
            //插入值比根节点的值小，插入到左字数
            t.rt = remove(data, t.rt);
        }else if(t.lt != null && t.rt != null){
            t.data = findMin(t.rt).data; //将右子树中的最小值赋给要删除的节点
            t.rt = remove(t.data, t.rt);
        }else{
            t = t.lt == null? t.rt:t.lt;
        }
        return t;
    }
    public BinaryNode<T> insert(T data, BinaryNode<T> t){
        if(t == null){
            return new BinaryNode<T>(data, null, null);
        }
        int compare = data.compareTo(t.data);
        if(compare < 0){
            //插入值比根节点的值小，插入到左字数
            t.lt = insert(data, t.lt);
        }else if(compare > 0){
            //插入值比根节点的值小，插入到左字数
            t.rt = insert(data, t.rt);
        }else{
        }
        return t;
    }
    public BinaryNode<T> findMin(BinaryNode<T> t){
        if(t == null){
            return t;
        }else if(t.lt == null){ //查找树的左边比节点值小，找到最左边的节点即可
            return t;
        }else{
            return findMin(t.lt);
        }
    }
    
    public BinaryNode<T> findMax(BinaryNode<T> t){
        if(t == null){
            return null;
        }else if(t.rt == null){ //查找树的右边比节点值大，找到最右边的节点即可
            return t;
        }
        return findMax(t.rt);
    }
    
    public static void main(String[] args) {
        BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<Integer>();
        binarySearchTree.insert(8);
        binarySearchTree.insert(4);
        binarySearchTree.insert(6);
        binarySearchTree.insert(3);
        binarySearchTree.insert(14);
        binarySearchTree.insert(10);
        System.out.println("最小值： "+binarySearchTree.findMin());
        System.out.println("最大值： "+binarySearchTree.findMax());
        binarySearchTree.printTree();
        binarySearchTree.remove(8);
        System.out.println();
        binarySearchTree.printTree();
    }
}