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 = 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();

    }

}