int[] arrs = {5,2,1,4,3,9,7,6,8};

int[] arrs = {1,2,3,4,5,6,7,8,9};

package Algorithm;
public class BinarySearchTree {
    Node root;  //定義根節(jié)點(diǎn)
    //結(jié)點(diǎn)插入方法
    public void insert(int value) {
        if (root == null) {        //1.如果樹(shù)是空樹(shù)，插入節(jié)點(diǎn)就直接放入到根結(jié)點(diǎn)
            root = new Node(value);
        } else {     //如果樹(shù)不是空樹(shù)，則插入的數(shù)字于根結(jié)點(diǎn)的數(shù)字進(jìn)行比較
            //2.如果插入的值小于于結(jié)點(diǎn)的數(shù)字，則往左子樹(shù)插入
            Node node = root;     //聲明一個(gè)游標(biāo)結(jié)點(diǎn)，開(kāi)始指向根節(jié)點(diǎn)
            while (true) {       //并且再次和待插入的執(zhí)行左子結(jié)點(diǎn)進(jìn)行比較，直到找到插入的位置
                if (value < node.value) {      //如果插入的值小于于結(jié)點(diǎn)的數(shù)字，則往左子樹(shù)插入
                    //2.1如果左子結(jié)點(diǎn)沒(méi)有元素就插入到左子結(jié)點(diǎn)中
                    if (node.left == null) {
                        node.left = new Node(value);
                        break;      //如果找到插入的位置，則跳出while循環(huán)
                    } else {         //如果左子結(jié)點(diǎn)有元素，就可以設(shè)計(jì)一個(gè)引用(游標(biāo))指向左子節(jié)點(diǎn)，并且再次和待插入的執(zhí)行左子結(jié)點(diǎn)進(jìn)行比較，直到找到插入的位置
                        //游標(biāo)指向左子節(jié)點(diǎn)
                        node = node.left;
                    }
                } else {      //如果插入的值大于結(jié)點(diǎn)的數(shù)字，則往右子樹(shù)插入
                    //判斷右子結(jié)點(diǎn)是否存在值，如果不存在則直接插入
                    if (node.right == null) {
                        node.right = new Node(value);
                        break;
                    } else {     //判斷右子結(jié)點(diǎn)是否存在值，如果存在則通過(guò)一個(gè)引用指向右子結(jié)點(diǎn)繼續(xù)和待插入的值進(jìn)行比較，直到找到插入的位置
                        //游標(biāo)指向右子節(jié)點(diǎn)
                        node = node.right;
                    }
                }
            }
        }
    }
    //定義左右結(jié)點(diǎn)常量
    public static final int LEFT = 0; //左子節(jié)點(diǎn)
    public static final int RIGHT = 1; //右子節(jié)點(diǎn)
    //結(jié)點(diǎn)查找方法
    public void deleteNode(int value) {
        //定義游標(biāo)從根節(jié)點(diǎn)開(kāi)始查詢(xún)
        Node node = root;
        //定義目標(biāo)結(jié)點(diǎn)
        Node target = null;
        //定義目標(biāo)結(jié)點(diǎn)的父類(lèi)結(jié)點(diǎn)
        Node parent = null;
        //目標(biāo)結(jié)點(diǎn)的類(lèi)型為，左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)
        int nodeType = 0; //0代表左子節(jié)點(diǎn) 1代表右子節(jié)點(diǎn)

        while (node != null) { //游標(biāo)不為空，如果為空則沒(méi)有子節(jié)點(diǎn)，無(wú)法刪除
            if (node.value == value) { //如果目標(biāo)結(jié)點(diǎn)的值和需要?jiǎng)h除結(jié)點(diǎn)的值相同
                //找到結(jié)點(diǎn)
                target = node;
                break;
            } else if (value < node.value) {    //如果值不同，則判斷目標(biāo)結(jié)點(diǎn)值是否小于node結(jié)點(diǎn)
                //保存父類(lèi)結(jié)點(diǎn)
                parent = node;
                //游標(biāo)指向左子節(jié)點(diǎn)
                node = node.left;
                nodeType = LEFT;
            } else { //如果值不同，且目標(biāo)結(jié)點(diǎn)值大于node結(jié)點(diǎn)
                //保存父類(lèi)結(jié)點(diǎn)
                parent = node;
                //游標(biāo)指向右子節(jié)點(diǎn)
                node = node.right;
                nodeType = RIGHT;
            }
        }
        //如果沒(méi)找到需要?jiǎng)h除的目標(biāo)結(jié)點(diǎn)
        if (target==null){
            System.out.println("沒(méi)有找到要?jiǎng)h除的結(jié)點(diǎn)");
            return;
        }
        //刪除結(jié)點(diǎn)的三種情況
        if (target.left == null && target.right == null) {   //情況1：待刪除的結(jié)點(diǎn)沒(méi)有子結(jié)點(diǎn)

            if (parent==null){      //刪除的結(jié)點(diǎn)沒(méi)有子結(jié)點(diǎn)
                //將root設(shè)置為null即可
                root=null;
                return;
            }
            //判斷目標(biāo)的結(jié)點(diǎn)是左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)
            if (nodeType == LEFT) {
                //將父類(lèi)的左子節(jié)點(diǎn)設(shè)置為null
                parent.left = null;
            } else {
                //將父類(lèi)的右子節(jié)點(diǎn)設(shè)置為null
                parent.right = null;
            }
        } else if (target.left != null && target.right != null) {   //情況2：待刪除的結(jié)點(diǎn)有2個(gè)子節(jié)點(diǎn)
            //兩個(gè)子節(jié)點(diǎn)，從target右子樹(shù)查找最小的值
            Node min=target.right;
            //遍歷左子樹(shù)
            while (min.left!=null){
                min = min.left;
            }
            //將最小的結(jié)點(diǎn)進(jìn)行刪除
            deleteNode(min.value);
            //將待刪除的結(jié)點(diǎn)替換成最小的結(jié)點(diǎn)的值
            target.value= min.value;
        }else { //情況3：待刪除的結(jié)點(diǎn)有1個(gè)子節(jié)點(diǎn)
            //刪除結(jié)點(diǎn)是根節(jié)點(diǎn)
            if (parent==null){
                if (target.left!=null){ //判斷是左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)有值
                    root=target.left;   //根節(jié)點(diǎn)=目標(biāo)左子結(jié)點(diǎn)
                }else {
                    root=target.right;  //根節(jié)點(diǎn)=目標(biāo)右子結(jié)點(diǎn)
                }
            }
            //只有一個(gè)子節(jié)點(diǎn)
            if (nodeType==LEFT){    //如果是左子節(jié)點(diǎn)
                if (target.left!=null){
                    //將父類(lèi)的左子節(jié)點(diǎn)，指向待刪除結(jié)點(diǎn)的左子節(jié)點(diǎn)
                    parent.left=target.left;
                }else { //如果是右子節(jié)點(diǎn)
                    //將父類(lèi)的左子節(jié)點(diǎn)，指向待刪除結(jié)點(diǎn)的右子節(jié)點(diǎn)
                    parent.left=target.right;
                }
            }else {
                if (target.right!=null){
                    //將父類(lèi)的右子節(jié)點(diǎn)，指向待刪除結(jié)點(diǎn)的左子節(jié)點(diǎn)
                    parent.right=target.left;
                }else { //如果是右子節(jié)點(diǎn)
                    //將父類(lèi)的右子節(jié)點(diǎn)，指向待刪除結(jié)點(diǎn)的右子節(jié)點(diǎn)
                    parent.right=target.right;
                }
            }
        }
    }
    //實(shí)現(xiàn)中序遍歷
    public void midTraversal(Node node) {
        if (node == null) {  //進(jìn)行判斷結(jié)點(diǎn)不能為空，如果為空則退出
            return;
        } else {     //如果結(jié)點(diǎn)不為null，則執(zhí)行下列遍歷語(yǔ)句
            //首先，遍歷左節(jié)點(diǎn)
            midTraversal(node.left);
            //打印根節(jié)點(diǎn)
            System.out.print(node.value + ",");
            //最后遍歷右子結(jié)點(diǎn)
            midTraversal(node.right);
        }
    }
    //創(chuàng)建一個(gè)結(jié)點(diǎn)類(lèi)
    public static class Node {
        int value;  //存儲(chǔ)值
        Node left;  //左子樹(shù)
        Node right; //右子樹(shù)
        // 帶參構(gòu)造方法，傳入value賦值
        public Node(int value) {
            this.value = value;
        }
    }
}

package Algorithm;
public class TestBST {
    public static void main(String[] args) {
        int[] arrs = {5, 2, 1, 4, 3, 9, 7, 6, 8};
        //創(chuàng)建二叉查詢(xún)樹(shù)
        BinarySearchTree tree = new BinarySearchTree();
        //將數(shù)組中的元素構(gòu)造成二叉查詢(xún)樹(shù)
        for (int i = 0; i < arrs.length; i++) {
            tree.insert(arrs[i]);
        }
        //刪除結(jié)點(diǎn)
        tree.deleteNode(20);
        //中序遍歷根結(jié)點(diǎn)
        tree.midTraversal(tree.root);
    }
}