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);
        }
    }

    /**
     * 尋找適合的沒有子節(jié)點(diǎn)的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;
    }

    /**
     * 中序：左中右 思路：壓入當(dāng)前節(jié)點(diǎn)连锯，判斷左孩子是否為空住拭， 若為空，則彈出該節(jié)點(diǎn)，并打印尸变，并以右孩子為當(dāng)前節(jié)點(diǎn)，重復(fù)操作莉兰；
     * 若不為空，則以左孩子做當(dāng)前節(jié)點(diǎn)秦效，重復(fù)操作
     * 
     * 重復(fù)操作的意思是呢。涎嚼。阱州。就是壓入堆棧，判斷左孩子是否為空法梯。苔货。。
     */
    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();
    }

    /**
     * 移除一個(gè)數(shù)
     * 
     * @param data
     */
    public void remove(int item) {
        Node node = searchNode(item);
        System.out.println("刪除節(jié)點(diǎn)：" + node);
        if (node == null)
            throw new NoSuchElementException();// 沒有當(dāng)前節(jié)點(diǎn)
        Node parent = node.parent;
        if (node.leftChild == null && node.rightChild == null) {// 沒有子節(jié)點(diǎn)立哑，直接刪除就行了
            if (parent == null) {// 沒有父節(jié)點(diǎn),說明是root節(jié)點(diǎn)
                root = null;// 直接將root置空
            } else {
                node.parent = null;
                if (parent.leftChild == node) {// 如果是父節(jié)點(diǎn)的左子節(jié)點(diǎn)夜惭，則設(shè)置父節(jié)點(diǎn)左子節(jié)點(diǎn)為空
                    parent.leftChild = null;
                } else {// 反之，設(shè)置右子節(jié)點(diǎn)為空
                    parent.rightChild = null;
                }
            }
        } else if (node.leftChild != null && node.rightChild == null) {// 有左子節(jié)點(diǎn)铛绰，沒有右子節(jié)點(diǎn)
            if (parent == null) {// root節(jié)點(diǎn)
                root = node.leftChild;// 將root節(jié)點(diǎn)設(shè)置為其左子節(jié)點(diǎn)
            } else {
                node.parent = null;
                if (parent.leftChild == node) {// 如果是父節(jié)點(diǎn)的左子節(jié)點(diǎn)滥嘴，則把自己的左子節(jié)點(diǎn)設(shè)置給父左子節(jié)點(diǎn)
                    parent.leftChild = node.leftChild;
                } else {// 反之，設(shè)置給父右子節(jié)點(diǎn)
                    parent.rightChild = node.leftChild;
                }
                node.leftChild.parent = parent;
            }
        } else if (node.leftChild == null && node.rightChild != null) {// 沒有左子節(jié)點(diǎn)至耻，有右子節(jié)點(diǎn)
            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) {// 有左子節(jié)點(diǎn)若皱，也有右子節(jié)點(diǎn)
            Node mostLeftNode = searchMostLeftNode(node.rightChild);// 搜索右子節(jié)點(diǎn)的最左子節(jié)點(diǎn)
            Node mostLeftNodeP = mostLeftNode.parent;// 最左子節(jié)點(diǎn)的父節(jié)點(diǎn)
            if (parent == null) {// 是root節(jié)點(diǎn)
                root = mostLeftNode;// 將root節(jié)點(diǎn)設(shè)置為右子節(jié)點(diǎn)的最左子節(jié)點(diǎn)
            } else {
                // 最左子節(jié)點(diǎn)替代刪除節(jié)點(diǎn)
                if (parent.leftChild == node) {
                    parent.leftChild = mostLeftNode;
                } else {
                    parent.rightChild = mostLeftNode;
                }
            }
            // 先處理最左子節(jié)點(diǎn)目前的父節(jié)點(diǎn)和右子節(jié)點(diǎn)的賦值
            // 最左子節(jié)點(diǎn)的父節(jié)點(diǎn)的左子節(jié)點(diǎn)，設(shè)置為最左子節(jié)點(diǎn)的右子節(jié)點(diǎn)尘颓，因?yàn)樽钭笞庸?jié)點(diǎn)沒有左子節(jié)點(diǎn)
            mostLeftNodeP.leftChild = mostLeftNode.rightChild;
            if (mostLeftNode.rightChild != null) {
                mostLeftNode.rightChild.parent = mostLeftNodeP;
            }

            // 再給最左子節(jié)點(diǎn)的父節(jié)點(diǎn)和左右子節(jié)點(diǎn)賦上新值
            // 最左子節(jié)點(diǎn)替代了了刪除節(jié)點(diǎn)走触，所以其父節(jié)點(diǎn)，孩子節(jié)點(diǎn)疤苹，都要等于刪除節(jié)點(diǎn)的父節(jié)點(diǎn)互广，孩子節(jié)點(diǎn)
            mostLeftNode.parent = parent;
            mostLeftNode.leftChild = node.leftChild;
            mostLeftNode.rightChild = node.rightChild;
            // 刪除節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)的父節(jié)點(diǎn)，也要相應(yīng)的設(shè)置為最左子節(jié)點(diǎn)
            node.leftChild.parent = mostLeftNode;
            node.rightChild.parent = mostLeftNode;
        }
    }

    /**
     * 搜索該節(jié)點(diǎn)的最左子節(jié)點(diǎn)
     * 
     * @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;
    }

    /**
     * 查詢指定節(jié)點(diǎn)
     * 
     * @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("初始節(jié)點(diǎn)");
        tree.middleOrder();

        Node n = tree.searchNode(54);
        System.out.println("查找節(jié)點(diǎn)：" + 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("插入節(jié)點(diǎn):25");
        tree.put(25);
        tree.middleOrder();
    }

}