import java.util.NoSuchElementException;
import java.util.Stack;

public class BinarySearchTree {

    private Node root;

    public void put(int item) {
        if (root == null) {
            root = new Node(item);
        } else {
            Node node = new Node(item);
            Node parent = searchNoChildNode(item);
            node.parent = parent;
            if (item > parent.item) {
                parent.rightChild = node;
            } else if (item < parent.item) {
                parent.leftChild = node;
            }
            // System.out.println("node=" + node);
            // System.out.println("parent=" + parent);
        }
    }

    /**
     * 寻找适合的没有子节点的node
     * 
     * @param item
     * @return
     */
    private Node searchNoChildNode(int item) {
        Node node = root;
        while (node != null) {
            if (item < node.item) {
                if (node.leftChild == null)
                    return node;
                node = node.leftChild;
            } else {
                if (node.rightChild == null)
                    return node;
                node = node.rightChild;
            }
        }
        return node;
    }

    /**
     * 中序：左中右 思路：压入当前节点，判断左孩子是否为空， 若为空，则弹出该节点，并打印，并以右孩子为当前节点，重复操作；
     * 若不为空，则以左孩子做当前节点，重复操作
     * 
     * 重复操作的意思是呢。。。就是压入堆栈，判断左孩子是否为空。。。
     */
    public void middleOrder() {
        Stack<Node> stack = new Stack<>();
        Node node = root;
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.leftChild;
            } else {
                node = stack.pop();
                System.out.print(node.item + " ");
                node = node.rightChild;
            }
        }
        System.out.println();
    }

    /**
     * 移除一个数
     * 
     * @param data
     */
    public void remove(int item) {
        Node node = searchNode(item);
        System.out.println("删除节点：" + node);
        if (node == null)
            throw new NoSuchElementException();// 没有当前节点
        Node parent = node.parent;
        if (node.leftChild == null && node.rightChild == null) {// 没有子节点，直接删除就行了
            if (parent == null) {// 没有父节点,说明是root节点
                root = null;// 直接将root置空
            } else {
                node.parent = null;
                if (parent.leftChild == node) {// 如果是父节点的左子节点，则设置父节点左子节点为空
                    parent.leftChild = null;
                } else {// 反之，设置右子节点为空
                    parent.rightChild = null;
                }
            }
        } else if (node.leftChild != null && node.rightChild == null) {// 有左子节点，没有右子节点
            if (parent == null) {// root节点
                root = node.leftChild;// 将root节点设置为其左子节点
            } else {
                node.parent = null;
                if (parent.leftChild == node) {// 如果是父节点的左子节点，则把自己的左子节点设置给父左子节点
                    parent.leftChild = node.leftChild;
                } else {// 反之，设置给父右子节点
                    parent.rightChild = node.leftChild;
                }
                node.leftChild.parent = parent;
            }
        } else if (node.leftChild == null && node.rightChild != null) {// 没有左子节点，有右子节点
            if (parent == null) {
                root = node.rightChild;
            } else {
                node.parent = null;
                if (parent.leftChild == node) {
                    parent.leftChild = node.rightChild;
                } else {
                    parent.rightChild = node.rightChild;
                }
                node.rightChild.parent = parent;
            }
        } else if (node.leftChild != null && node.rightChild != null) {// 有左子节点，也有右子节点
            Node mostLeftNode = searchMostLeftNode(node.rightChild);// 搜索右子节点的最左子节点
            Node mostLeftNodeP = mostLeftNode.parent;// 最左子节点的父节点
            if (parent == null) {// 是root节点
                root = mostLeftNode;// 将root节点设置为右子节点的最左子节点
            } else {
                // 最左子节点替代删除节点
                if (parent.leftChild == node) {
                    parent.leftChild = mostLeftNode;
                } else {
                    parent.rightChild = mostLeftNode;
                }
            }
            // 先处理最左子节点目前的父节点和右子节点的赋值
            // 最左子节点的父节点的左子节点，设置为最左子节点的右子节点，因为最左子节点没有左子节点
            mostLeftNodeP.leftChild = mostLeftNode.rightChild;
            if (mostLeftNode.rightChild != null) {
                mostLeftNode.rightChild.parent = mostLeftNodeP;
            }

            // 再给最左子节点的父节点和左右子节点赋上新值
            // 最左子节点替代了了删除节点，所以其父节点，孩子节点，都要等于删除节点的父节点，孩子节点
            mostLeftNode.parent = parent;
            mostLeftNode.leftChild = node.leftChild;
            mostLeftNode.rightChild = node.rightChild;
            // 删除节点的两个子节点的父节点，也要相应的设置为最左子节点
            node.leftChild.parent = mostLeftNode;
            node.rightChild.parent = mostLeftNode;
        }
    }

    /**
     * 搜索该节点的最左子节点
     * 
     * @param node
     * @return
     */
    private Node searchMostLeftNode(Node node) {
        Node leftNode = node;
        while (leftNode != null) {
            if (leftNode.leftChild == null)
                return leftNode;
            leftNode = leftNode.leftChild;
        }
        return leftNode;
    }

    /**
     * 查询指定节点
     * 
     * @param item
     * @return
     */
    public Node searchNode(int item) {
        Node node = root;
        while (node != null) {
            if (item > node.item) {
                node = node.rightChild;
            } else if (item < node.item) {
                node = node.leftChild;
            } else {
                return node;
            }
        }
        return null;
    }

    private class Node {
        private int item;
        private Node parent;
        private Node leftChild;
        private Node rightChild;

        public Node(int item) {
            this.item = item;
        }

        @Override
        public String toString() {
            String p = null;
            if (parent != null) {
                p = String.valueOf(parent.item);
            }
            String l = null;
            if (leftChild != null) {
                l = String.valueOf(leftChild.item);
            }
            String r = null;
            if (rightChild != null) {
                r = String.valueOf(rightChild.item);
            }
            return "Node [item=" + item + ", parent=" + p + ", leftChild=" + l + ", rightChild=" + r + "]";
        }

    }

    public static void main(String[] args) {
        int[] items = { 20, 31, 10, 12, 54, 23, 11, 5, 100, 43, 26 };
        BinarySearchTree tree = new BinarySearchTree();
        for (int i : items) {
            tree.put(i);
        }
        System.out.println("初始节点");
        tree.middleOrder();

        Node n = tree.searchNode(54);
        System.out.println("查找节点：" + n);

        tree.remove(20);
        tree.middleOrder();

        tree.remove(5);
        tree.middleOrder();

        tree.remove(100);
        tree.middleOrder();

        tree.remove(43);
        tree.middleOrder();

        tree.remove(23);
        tree.middleOrder();

        System.out.println("插入节点:25");
        tree.put(25);
        tree.middleOrder();
    }

}