package demo;

import java.util.LinkedList;

/**
 * 二分查找树
 * 
 * @author Administrator
 *
 * @param <K>
 * @param <V>
 */
public class BST<K extends Comparable<K>, V> {

    private final static Node EmptyNode = null;
    private Node head;
    private int count;

    private static class Node<K extends Comparable<K>, V> {
        K key;
        V value;
        Node<K, V> left;
        Node<K, V> right;

        private Node(K key, V val) {
            this.key = key;
            this.value = val;
            this.left = EmptyNode;
            this.right = EmptyNode;
        }

        
        private Node(Node<K,V> node) {
            this.key = node.key;
            this.value = node.value;
            this.left = node.left;
            this.right = node.right;
        }
        
        
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("{ ").append(key).append(":").append(value).append(" }");
            return sb.toString();

        }

    }

    public BST() {
        head = EmptyNode;
        count = 0;
    }

    public int size() {
        return count;
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public void insert(K key, V val) {
        checkArg(key, "key is null");
        head = insert(head, key, val);

    }

    private Node<K, V> insert(Node<K, V> root, K key, V val) {
        if (root == EmptyNode) {
            count++;
            return new Node<K, V>(key, val);
        }
        if (root.key.compareTo(key) > 0)
            root.left = insert(root.left, key, val);
        else if (root.key.compareTo(key) < 0)
            root.right = insert(root.right, key, val);
        else
            root.value = val;
        return root;
    }

    public V search(K key) {
        return (V) search(head, key);
    }

    private V search(Node<K, V> root, K key) {
        checkArg(key, "key is null");
        if (root == EmptyNode)
            return null;

        if (root.key.compareTo(key) == 0)
            return root.value;

        else if (root.key.compareTo(key) > 0)
            return (V) search(root.left, key);
        else
            return (V) search(root.right, key);
    }

    public void preOrder() {
        preOrder(head);
    }

    private void preOrder(Node root) {
        if (root == EmptyNode)
            return;
        System.out.print(root);
        preOrder(root.left);
        preOrder(root.right);
    }

    public void midOrder() {
        midOrder(head);
    }

    private void midOrder(Node root) {

        if (root == EmptyNode)
            return;
        midOrder(root.left);
        System.out.print(root);
        midOrder(root.right);

    }

    public void postOrder() {
        postOrder(head);
    }

    private void postOrder(Node root) {
        if (root == EmptyNode)
            return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root);
    }

    private void checkArg(Object key, String thrStr) {
        if (key == null)
            throw new IllegalArgumentException(thrStr);
    }

    public void levelOrder() {
        if (head == EmptyNode)
            return;
        LinkedList<Node> ll = new LinkedList();
        ll.addLast(head);
        while (!ll.isEmpty()) {
            Node node = ll.removeFirst();
            System.out.println(node);
            if (node.left != EmptyNode)
                ll.addLast(node.left);
            if (node.right != EmptyNode)
                ll.addLast(node.right);
        }
    }

    public K getMinNode() {
        checkArg(head, "this tree is empty!!");
        return (K) getMinNode(head).key;

    }

    private Node getMinNode(Node root) {
        if (root.left == EmptyNode)
            return root;
        return getMinNode(root.left);
    }

    public K getMaxNode() {
        checkArg(head, "this tree is empty!!");
        return (K) getMaxNode(head).key;
    }

    private Node<K, V> getMaxNode(Node<K, V> root) {
        if (root.right == EmptyNode)
            return root;
        return getMaxNode(root.right);
    }

    public void removeMin() {
        checkArg(head, "the tree is empty");
        head = removeMin(head);
    }

    private Node removeMin(Node root) {
        if (root.left == EmptyNode) {
            Node rightNode = root.right;
            root = EmptyNode;
            count--;
            return rightNode;
        }
        root.left = removeMin(root.left);
        return root;
    }

    public void removeMax() {
        checkArg(head, "the tree is empty");
        head = removeMax(head);
    }

    private Node removeMax(Node root) {
        if (root.right == EmptyNode) {
            Node leftNode = root.left;
            root = null;
            count--;
            return leftNode;
        }
        root.right = removeMax(root.right);
        return root;
    }

    public void remove(K key) {
        head = remove(head, key);
    }

    private Node remove(Node root, K key) {
         if(root ==EmptyNode) return null;
        if (root.key.compareTo(key) < 0) {//
            root.right = remove(root.right, key);
            return root;
        } else if (root.key.compareTo(key) > 0) {
            root.left = remove(root.left, key);
            return root;
        } else {// equal
            if(root.left ==EmptyNode) {//没有左节点
                
                Node rightNode = root.right;
                root=EmptyNode;
                count--;
                return rightNode;
                
            }
            if(root.right == EmptyNode) {//没有右节点
                Node leftNode = root.right;
                root=EmptyNode;
                count--;
                return leftNode;
            }
            //左右节点都存在
            Node min = getMinNode(root.right); 
            Node s = new Node<K, V>(min);
            s.right = removeMin(root.right);
            s.left = root.left;
            return s;
            
        }
    }

    
    public static void main(String[] args) {
        BST<Integer, Object> bst = new BST();
        bst.insert(1, "hello");
        bst.insert(10, "hello");
        bst.insert(9, "hello");
        bst.insert(20, "hello");
        bst.insert(11, "hello");
        bst.insert(14, "hello");
        bst.insert(90, "hello");
        bst.insert(25, "hello");
        bst.midOrder();
        bst.remove(10);
        System.out.println("");
        bst.midOrder();
    }
    
    
}