import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * 二分搜索树的实现
 * 
 * @author hcc
 *
 * @param <E>
 */
public class BST<E extends Comparable<E>> {
    private Node root;
    private int size;

    public BST() {
        this(null);
    }

    private BST(Node root) {
        this.root = root;
        this.size = 0;
    }

    /**
     * 添加元素
     * @param e
     */
    public void add(E e) {
        if (root == null) {
            root = new Node(e);
            size++;
        } else {
            add(this.root, e);
        }
    }
    
    /**
     * 添加元素的具体操作
     * @param root 树结构的根节点
     * @param e 将要添加的数据
     */
    private void add(Node root, E e) {
        // 也可以使用该表达式判断 e是否存在于树结构中
        // if(e.compareTo(root.data) == 0) {
        // return;
        // }
        if (e.equals(root.data)) {
            return;
        } else if (e.compareTo(root.data) < 0 && root.left == null) {
            Node node = new Node(e);
            root.left = node;
            size++;
        } else if (e.compareTo(root.data) > 0 && root.right == null) {
            Node node = new Node(e);
            root.right = node;
            size++;
        }

        if (e.compareTo(root.data) < 0) {
            add(root.left, e);
        }
        if (e.compareTo(root.data) > 0) {
            add(root.right, e);
        }
    }

    /**
     * 优化后的添加方法（优化了递归结束条件）
     */
    @SuppressWarnings("unused")
    private Node addForOptimize(Node root, E e) {
        if (root == null) {
            Node node = new Node(e);
            size++;
            return node;
        } else if (e.compareTo(root.data) < 0) {
            root.left = addForOptimize(root.left, e);
        } else if (e.compareTo(root.data) > 0) {
            root.right = addForOptimize(root.right, e);
        }
        return root;
    }

    /**
     * 删除操作，删除树中最小的元素、删除树中最大的元素、随意删除
     */
    /**
     * 删除“树”上最小的元素（在左下角，二分搜索树的性质决定的）
     * 
     * @return 返回该节点的值
     */
    public E removeMin() {
        Node node = removeMin(root);
        return node.data;
    }

    /**
     * 当找到左下角节点时，需判断该节点是否有“右孩子”
     * @param node
     * @return
     */
    private Node removeMin(Node node) {
        if (node == null) {
            // 或者通过size判断是否为空也可以
            throw new IllegalArgumentException("BST is Empty!");
        }
        Node sNode = null;
        while (node.left != null) {
            sNode = node;
            node = node.left;
        }
        Node nod = node;
        node = null;
        if (nod.right != null) {
            sNode.left = nod.right;
        } else {
            sNode.left = null;
        }
        size--;
        return nod;
    }

    /**
     * 删除“树”上最大的元素（在右下角，二分搜索树的性质决定的）
     * 
     * @return 返回该节点的值
     */
    public E removeMax() {
        Node node = removeMax(root);
        return node.data;
    }

    /**
     * 当找到右下角节点时，需判断该节点是否有“左孩子”
     * @param node
     * @return
     */
    private Node removeMax(Node node) {
        if (node == null) {
            throw new IllegalArgumentException("BST is Empty!");
        }
        Node sNode = null;
        while (node.right != null) {
            sNode = node;
            node = node.right;
        }
        Node nod = node;
        node = null;
        if (nod.left != null) {
            sNode.right = nod.left;
        } else {
            sNode.right = null;
        }
        size--;
        return nod;
    }

    /**
     * 删除任意位置的值
     * 
     * @param e
     */
    public void remove(E e) {
        root = remove(root, e);
    }

    /**
     * 删除的具体操作
     * 
     * @param node
     *            树结构
     * @param e
     *            将要删除的数据
     * @return 删除指定数据后的树结构
     */
    private Node remove(Node node, E e) {
        if (e == null || node == null) {
            return null;
        }
        if (e.equals(node.data)) {
            if (node.left != null && node.right != null) {
                Node nod = node;
                node = removeMin(node.right);
                size++;
                node.left = nod.left;
                node.right = nod.right;
                nod.left = nod.right = null;
            } else {
                if (node.left == null && node.right != null) {
                    size--;
                    return node.right;
                } else if (node.right == null && node.left != null) {
                    size--;
                    return node.left;
                } else {
                    size--;
                    return null;
                }
            }
            size--;
            return node;
        } else if (e.compareTo(node.data) < 0) {
            node.left = remove(node.left, e);
        } else if (e.compareTo(node.data) > 0) {
            node.right = remove(node.right, e);
        }
        return node;
    }

    /**
     * 查，前序遍历（递归、非递归）中序遍历（递归、非递归）后序遍历（递归、非递归）层序遍历
     */
    /**
     * 前序遍历
     */
    public void preOrder() {
        preOrder(root);
    }

    /**
     * 前序遍历（递归操作）
     * 
     * @param root
     */
    private void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);

    }

    /**
     * 前序遍历（非递归操作）
     * 
     * @param root
     */
    @SuppressWarnings("unused")
    private void preOrderOne(Node node) {
        Stack<Node> stack = new Stack<Node>();
        stack.push(node);
        while (!stack.isEmpty()) {
            Node sNode = stack.pop();
            System.out.print(sNode.data + " ");
            if (sNode.right != null) {
                stack.push(sNode.right);
            }
            if (sNode.left != null) {
                stack.push(sNode.left);
            }
        }
    }

    /**
     * 中序遍历
     */
    public void inOrder() {
        inOrderOne(root);
    }

    /**
     * 中序遍历（递归操作）
     * 
     * @param root
     */
    @SuppressWarnings("unused")
    private void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.print(node.data + " ");
        inOrder(node.right);
    }

    /**
     * 中序遍历（非递归操作）
     * 
     * @param root
     */
    private void inOrderOne(Node node) {
        Stack<Node> stack = new Stack<Node>();
        Node nod = node;
        while (!stack.isEmpty() || nod != null) {
            while (nod != null) {
                stack.push(nod);
                nod = nod.left;
            }
            Node sNode = stack.pop();
            System.out.print(sNode.data + " ");
            nod = sNode.right;
        }
    }

    /**
     * 后序遍历
     */
    public void postOrder() {
        postOrderOne(root);
    }

    /**
     * 后序遍历（递归操作）
     * 
     * @param node
     */
    @SuppressWarnings("unused")
    private void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data + " ");
    }

    /**
     * 后序遍历（非递归操作）
     * 
     * @param node
     */
    private void postOrderOne(Node node) {
        Stack<Node> stack = new Stack<Node>();
        Node nod = node;
        Node pre = null;
        while (!stack.isEmpty() || nod != null) {
            while (nod != null) {
                stack.push(nod);
                nod = nod.left;
            }
            Node sNode = stack.peek();
            if (sNode.right == null || pre == sNode.right) {
                stack.pop();
                pre = sNode;
                System.out.print(sNode.data + " ");
            } else {
                nod = sNode.right;
            }
        }
    }

    /**
     * 层序遍历
     */
    public void levelTraversal() {
        levelTraversal(root);
    }

    /**
     * 层序遍历（非递归操作）
     * 
     * @param node
     */
    private void levelTraversal(Node node) {
        Queue<Node> queue = new ArrayBlockingQueue<Node>(size);
        if (node != null) {
            queue.offer(node);
        }
        while (!queue.isEmpty()) {
            // System.out.println("取出前："+queue.size());
            node = queue.poll();
            // System.out.println("取出后："+queue.size());
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            System.out.print(node.data + " ");
        }
    }

    /**
     * 获取二分搜索树中数据的个数
     * 
     * @return
     */
    public int getSize() {
        return this.size;
    }

    /**
     * 判空操作
     * 
     * @return true表示为空，false表示不为空
     */
    public boolean isEmpty() {
        return this.size == 0;
    }

    /**
     * 判断数据是否在树中存在
     * 
     * @param e
     * @return true表示存在，false表示不存在
     */
    public boolean contains(E e) {
        return contains(root, e);
    }

    private boolean contains(Node root, E e) {
        if (root != null) {
            if (e.compareTo(root.data) == 0) {
                return true;
            } else if (e.compareTo(root.data) < 0) {
                return contains(root.left, e);
            } else if (e.compareTo(root.data) > 0) {
                return contains(root.right, e);
            }
        }
        return false;
    }

    class Node {
        E data;
        Node left;
        Node right;

        public Node() {
            this(null, null, null);
        }

        public Node(E e) {
            this(e, null, null);
        }

        private Node(E e, Node left, Node right) {
            this.data = e;
            this.left = left;
            this.right = right;
        }
    }
}