/**
 * @author chenyi
 * @Description 二叉排序樹
 * @date 2022/2/23 10:12
 */
public class BinarySortTreeDemo {

    Node root;

    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySortTreeDemo treeDemo = new BinarySortTreeDemo();
        for (int i : arr) {
            treeDemo.add(i);
        }
        treeDemo.perOrder();
        System.out.println("測試刪除節(jié)點");
        treeDemo.del(1);
        treeDemo.del(2);
        treeDemo.del(3);
        treeDemo.del(5);
        treeDemo.del(0);
        treeDemo.perOrder();
    }

    public void add(int val) {
        if (root == null) {
            root = new Node(val);
            return;
        }
        Node node = new Node(val);
        Node temp = root;
        Node parent;
        do {
            parent = temp;
            temp = temp.value > val ? temp.left : temp.right;
        } while (temp != null);
        if (parent.value > val) {
            parent.left = node;
        } else {
            parent.right = node;
        }
    }

    public void del(int val) {
        Node temp = this.root;
        Node parent = null;
        while (temp != null && temp.value!=val) {
            parent = temp;
            temp = temp.value > val ? temp.left : temp.right;
        }
        if(temp == null) {
            // 沒有找到val匹配的節(jié)點
            return;
        }

        if(temp.left == null && temp.right == null) {
            // 刪除葉子節(jié)點
            if(parent == null) {
                this.root = null;
                return;
            }
            if(parent.left == temp) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        } else if(temp.left != null && temp.right != null) {
            // 刪除有兩個子樹
            // 找到右子樹中最小的節(jié)點侮繁，用最小節(jié)點的值替換當前節(jié)點的值拉宗，刪除最小的節(jié)點
            Node minNode = temp.right;
            Node minNodeParent = temp;
            while (minNode.left!= null){
                minNodeParent = minNode;
                minNode = minNode.left;
            }
            temp.value = minNode.value;
            if(minNodeParent.left == minNode) {
                minNodeParent.left = null;
            } else {
                minNodeParent.right = null;
            }
        } else {
            // 刪除只有一個子樹
            if(parent.left == temp) {
                parent.left = temp.left==null ? temp.right : temp.left;
            } else {
                parent.right = temp.left==null ? temp.right : temp.left;
            }
        }
    }


    public void perOrder() {
        System.out.println();
        perOrder(this.root);
        System.out.println();
    }

    private void perOrder(Node node) {
        if (node == null) {
            return;
        }
        perOrder(node.left);
        System.out.print(node.value+ " ");
        perOrder(node.right);
    }


    class Node {
        int value;
        Node left;
        Node right;
        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" + "value=" + value + '}';
        }

    }

}