/**
 * @author: Mr.Du
 * @description: 二叉搜索樹
 * @date: 2021/05/04 17:00
 */
public class MyBSTree<T extends Comparable<T>> {

    private Node root;//二叉搜索樹根節(jié)點(diǎn)
    private int size;//二叉搜索樹結(jié)點(diǎn)個(gè)數(shù)

    //添加結(jié)點(diǎn)
    public boolean add(T value) {
        // 對(duì)于一個(gè)二叉搜索樹來(lái)講我們不存儲(chǔ)null: null不能比較大小
        if (value == null)
            throw new IllegalArgumentException("The param is null");
        //判斷原本的樹是否為空
        if (root == null) {
            // 如果原本的樹是一個(gè)空樹, 那么這個(gè)添加的元素就是根節(jié)點(diǎn)
            root = new Node(value, null, null);
            size++;
            return true;
        }

        //目前來(lái)看，樹不空，值也不是null
        Node index = root;//比較結(jié)點(diǎn)
        Node indexF = null;//比較結(jié)點(diǎn)的父結(jié)點(diǎn)
        int com = 0;//比較value大小結(jié)果
        while (index != null) {
            // 把要存儲(chǔ)的值, 和遍歷結(jié)點(diǎn)作比較, 進(jìn)一步確定相對(duì)于mid存儲(chǔ)的位置
            com = index.value.compareTo(value);
            indexF = index;
            if (com > 0) {
                index = index.left;
            } else if (com < 0) {
                index = index.right;
            } else {
                // com = 0
                // value 和 index存儲(chǔ)的值一樣
                // 對(duì)于重復(fù)元素的處理方式
                //       理論上:
                //                1, 計(jì)數(shù)法:  對(duì)于每一個(gè)結(jié)點(diǎn)都額外維護(hù)一個(gè)參數(shù), 記錄這個(gè)元素的重復(fù)數(shù)量
                //                2, 拉鏈法: 在某個(gè)結(jié)點(diǎn)位置維護(hù)一個(gè)鏈表, 用一個(gè)鏈表代表一個(gè)結(jié)點(diǎn)
                //                3, 修正的BST: 如果比較的過(guò)程中發(fā)現(xiàn)了重復(fù)元素, 向左存儲(chǔ)
                //       實(shí)際上:
                //             不讓存
                return false;
            }
        }

        if (com > 0) {
            indexF.left = new Node(value, null, null);
        } else {
            indexF.right = new Node(value, null, null);
        }
        size++;
        return true;
    }

    //是否存在指定值
    public boolean contains(T value) {
        // 對(duì)于一個(gè)二叉搜索樹來(lái)講我們不存儲(chǔ)null: null不能比較大小
        if (value == null)
            throw new IllegalArgumentException("The param is null");

        Node index = root;
        int com = 0;
        while (index != null) {
            com = value.compareTo(index.value);
            if (com > 0) {
                index = index.right;
            } else if (com < 0) {
                index = index.left;
            } else return true;
        }
        //如果代碼走到這個(gè)位置, 意味著上述循環(huán)跳出條件是: index == null 意味著沒(méi)有這個(gè)元素
        return false;
    }
    //遞歸方法刪除二叉搜索樹結(jié)點(diǎn)
    public boolean removeByRecursive(T value){
        int oldSize = size;
        root = removeByRe(root,value);
        return size<oldSize;
    }
    // 實(shí)現(xiàn)以root為根節(jié)點(diǎn)的子樹上刪除值為value的結(jié)點(diǎn)
    private Node removeByRe(Node root,T value){
        if (root == null) return null;
        int com = value.compareTo(root.value);
        if (com>0){
            //如果value存在, 在right子樹上
            root.right = removeByRe(root.right,value);
            return root;
        }else if (com<0){
            //如果value存在, 在left子樹上
            root.left = removeByRe(root.left,value);
            return root;
        }else{
            // 找到了要?jiǎng)h除的結(jié)點(diǎn)
            if (root.left!=null&&root.right!=null){
                // 刪除的結(jié)點(diǎn)是雙分支結(jié)點(diǎn)
                // 獲取right子樹的最小值
                Node rightMin = root.right;
                while (rightMin.left!=null){
                    rightMin = rightMin.left;
                }
                //替換
                root.value = rightMin.value;
                // 接下來(lái), 去right子樹上刪除rightMin(此時(shí)rightMin一定不是雙分支結(jié)點(diǎn))
                // 遞歸調(diào)用刪除方法, 在這個(gè)root的right子樹上刪除這個(gè)替換值
                root.right = removeByRe(root.right,root.value);
                return root;
            }
            // 刪除的是葉子或者單分支
            Node node = root.left != null? root.left : root.right;
            size--;
            return node;
        }
    }
    //非遞歸方法刪除二叉搜索樹結(jié)點(diǎn)
    public boolean removeByNonRecursive(T value) {
        //不存儲(chǔ)null: null不能比較大小
        if (value == null)
            throw new IllegalArgumentException("The param is null");
        /*
        思路:
            先找到要?jiǎng)h除的結(jié)點(diǎn)
            判斷要?jiǎng)h除的結(jié)點(diǎn)是不是雙分支: 如果是雙分支, 先替換
            刪除單分支或者葉子
         */
        Node index = root;
        Node indexF = null;
        int com;
        while (index != null) {
            com = value.compareTo(index.value);
            if (com > 0) {
                indexF = index;
                index = index.right;
            } else if (com < 0) {
                indexF = index;
                index = index.left;
            } else
                break;
        }
        // indexF 是要?jiǎng)h除結(jié)點(diǎn)的父結(jié)點(diǎn)
        // index 是找到的要?jiǎng)h除的結(jié)點(diǎn)

        //如果index是null,沒(méi)有包含刪除的元素，返回false
        if (index == null)
            return false;

        //到這里，說(shuō)明包含需要?jiǎng)h除的元素
        if (index.left != null && index.right != null) {
            //去right子樹找一個(gè)最小值, 替換這個(gè)刪除結(jié)點(diǎn)
            Node rightMin = index.right;
            //替換結(jié)點(diǎn)的父結(jié)點(diǎn)
            Node rightMinF = index;
            //找index.right子樹的最小值, 最left的元素
            while (rightMin.left != null) {
                rightMinF = rightMin;
                rightMin = rightMinF.left;
            }

            //到達(dá)這里：rightMin.left=null
            //用查找的right子樹上的最小值, 替換這個(gè)要?jiǎng)h除的雙分支結(jié)點(diǎn)
            index.value = rightMin.value;
            //將替換結(jié)點(diǎn)設(shè)置為后面需要?jiǎng)h除的單分支結(jié)點(diǎn)
            indexF = rightMinF;
            index = rightMin;
        }

        // 有可能原本就是葉子或者單分支
        // 也有可能雙分支已經(jīng)替換了, 現(xiàn)在要?jiǎng)h除的是哪個(gè)替換了的, 葉子或者單分支

        // 必定是個(gè)葉子或者單分支: index
        // 同時(shí)我們還記錄了index 的 父結(jié)點(diǎn) indexF

        //尋找index的兒子結(jié)點(diǎn)ch:
        // 如果index是葉子 ,那么ch = null
        // 如果index是單分支, ch = 不為null單分支子結(jié)點(diǎn)
        Node ch = index.left != null ? index.left : index.right;

        // 如果刪除的是根節(jié)點(diǎn), 并且根節(jié)點(diǎn)還是個(gè)單分支的結(jié)點(diǎn), 對(duì)于上述代碼會(huì)導(dǎo)致midF = null
        if (indexF == null) {
            root = ch;
            size--;
            return true;
        }

        //刪除結(jié)點(diǎn)
        if (indexF.left == index) {
            indexF.left = ch;
        } else
            indexF.right = ch;
        size--;
        return true;
    }

    //用棧來(lái)實(shí)現(xiàn)先中后序遍歷：
    //①先序
    public List<T> preOrder() {
        //保存遍歷結(jié)果
        List<T> list = new ArrayList<>();
        //用棧來(lái)臨時(shí)存儲(chǔ)結(jié)點(diǎn)
        MyLinkedStack<Node> stack = new MyLinkedStack<>();
        //根節(jié)點(diǎn)入棧
        stack.push(root);
        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            list.add(pop.value);
            if (pop.right != null)
                stack.push(pop.right);
            if (pop.left != null)
                stack.push(pop.left);
        }
        return list;
    }

    //②中序
    public List<T> inOrder() {
        Stack<Node> stack = new Stack<>();
        List<T> list = new ArrayList<>();
        Node index = root;
        while (index != null || !stack.empty()) {
            while (index != null) {
                stack.push(index);
                index = index.left;
            }
            Node pop = stack.pop();
            list.add(pop.value);
            index = pop.right;
        }
        return list;
    }

    //③后序
    public List<T> postOrder() {
        Stack<Node> stack = new Stack<>();
        List<T> list = new ArrayList<>();
        stack.push(root);
        while (!stack.empty()) {
            Node pop = stack.pop();
            list.add(0, pop.value);
            if (pop.left != null)
                stack.push(pop.left);
            if (pop.right != null)
                stack.push(pop.right);
        }
        return list;
    }

    //用遞歸來(lái)實(shí)現(xiàn)先中后序遍歷
    //①先序
    public List<T> preOrderRecursive() {
        List<T> list = new LinkedList<>();
        preRecursive(list, root);
        return list;
    }

    // 先序：根 左 右
    private void preRecursive(List<T> list, Node node) {
        if (node == null)
            return;
        list.add(node.value);
        preRecursive(list, node.left);
        preRecursive(list, node.right);
    }

    //②中序
    public List<T> inOrderRecursive() {
        List<T> list = new LinkedList<>();
        inRecursive(list, root);
        return list;
    }

    // 中序遍歷： 左 根 右
    private void inRecursive(List<T> list, Node node) {
        if (node == null)
            return;
        inRecursive(list, node.left);
        list.add(node.value);
        inRecursive(list, node.right);
    }

    //③ 后序遍歷
    public List<T> postOrderRecursive() {
        List<T> list = new LinkedList<>();
        postRecursive(list, root);
        return list;
    }

    // 后序： 左 右 根
    private void postRecursive(List<T> list, Node node) {
        if (node == null)
            return;
        preRecursive(list, node.left);
        preRecursive(list, node.right);
        list.add(node.value);
    }

    // 層級(jí)： 廣度優(yōu)先搜索(BFS)
    public List<T> levOrder() {
        List<T> list = new ArrayList<>();
        Queue<Node> queue = new LinkedBlockingQueue<>();

        //根節(jié)點(diǎn)入隊(duì)列
        queue.offer(root);
        while (!queue.isEmpty()) {
            //出隊(duì)列元素
            Node poll = queue.poll();
            //遍歷
            list.add(poll.value);
            //把出隊(duì)列元素的左右子節(jié)點(diǎn)入隊(duì)列
            if (poll.left != null)
                queue.offer(poll.left);
            if (poll.right != null)
                queue.offer(poll.right);
        }
        return list;
    }


    //  建樹: 給定前中序, 或者給定中后序,  構(gòu)建出一棵二叉樹


    //  中序 [-50, -25, -20, -10, -5, 1, 2, 7, 10, 25, 30, 100]
    //  后序 [-20, -25, -50, -10, -5, 7, 2, 25, 30, 100, 10, 1]
    public Node buildTreeByInAndPostOrder(List<T> inOrder, List<T> postOrder) {
        Node treeRoot = buildTreeByInAndPostOrder2(inOrder, postOrder);
        return treeRoot;
    }

    private Node buildTreeByInAndPostOrder2(List<T> inOrder, List<T> postOrder) {
        if (inOrder.size() == 0) return null;
        if (inOrder.size() == 1) return new Node(inOrder.get(0), null, null);
        //找根結(jié)點(diǎn): 后序的最后一個(gè)元素
        T rootValue = postOrder.get(postOrder.size() - 1);
        //獲得根節(jié)點(diǎn)在中序的位置
        int rootAtInOrderIndex = inOrder.indexOf(rootValue);

        // 左子樹的中序(中序中切割): 0 ~ rootAtInOrderIndex-1
        // 左子樹的后序(后序中切割): 0 ~ rootAtInOrderIndex -1

        // 右子樹的中序(中序中切割): rootAtInOrderIndex + 1 ~ size -1
        // 右子樹的后序(后序中切割): rootAtInOrderIndex ~ size - 2

        //左子樹
        //subList()：左閉右開
        List<T> leftInOrder = inOrder.subList(0, rootAtInOrderIndex);
        List<T> leftPostOrder = postOrder.subList(0, rootAtInOrderIndex);

        //右子樹
        //subList()：左閉右開
        List<T> rightInOrder = inOrder.subList(rootAtInOrderIndex + 1, inOrder.size());
        List<T> rightPostOrder = postOrder.subList(rootAtInOrderIndex, postOrder.size() - 1);
        //構(gòu)建這次遞歸的根節(jié)點(diǎn)
        Node node = new Node(rootValue, null, null);
        // 用遞歸方法處理, 獲得左子樹
        node.left = buildTreeByInAndPostOrder2(leftInOrder, leftPostOrder);
        // 用遞歸方法處理, 獲得右子樹
        node.right = buildTreeByInAndPostOrder2(rightInOrder, rightPostOrder);

        return node;
    }

    //  中序 [-50, -25, -20, -10, -5, 1, 2, 7, 10, 25, 30, 100]
    //  前序 1  -5  -10  -50  -25  -20   10  2  7  100  30  25
    public Node buildTreeByInAndPreOrder(List<T> inOrder, List<T> preOrder) {
        Node treeRoot = buildTreeByInAndPreOrder2(inOrder, preOrder);
        return treeRoot;
    }

    private Node buildTreeByInAndPreOrder2(List<T> inOrder, List<T> preOrder) {
        if (inOrder.size() == 0) return null;
        if (inOrder.size() == 1) return new Node(inOrder.get(0), null, null);

        T rootValue = preOrder.get(0);
        int rootAtInOrderIndex = inOrder.indexOf(rootValue);

        //左子樹
        //subList()：左閉右開
        List<T> leftInOrder = inOrder.subList(0, rootAtInOrderIndex);
        List<T> leftPreOrder = preOrder.subList(1, rootAtInOrderIndex + 1);
        //右子樹
        //subList()：左閉右開
        List<T> rightInOrder = inOrder.subList(rootAtInOrderIndex+1,inOrder.size());
        List<T> rightPreOrder = preOrder.subList(rootAtInOrderIndex+1,preOrder.size());

        Node node = new Node(rootValue,null,null);
        node.left = buildTreeByInAndPreOrder2(leftInOrder,leftPreOrder);
        node.right = buildTreeByInAndPreOrder2(rightInOrder,rightPreOrder);
        return node;
    }

    //判空
    public boolean isEmpty() {
        return size == 0;
    }

    //返回結(jié)點(diǎn)個(gè)數(shù)
    public int size() {
        return size;
    }

    class Node {
        T value;
        Node left;
        Node right;

        public Node(T value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}