public class binarySortTree {
    class Node{
        int value;
        Node left;
        Node right;
        public Node(int value){
            this.value = value;
        }
        public void display(){
            System.out.print(this.value + " ");
        }
    }
    Node root;
}

//添加節(jié)點(diǎn)
	//此方法可以類內(nèi)部方法的調(diào)用
    private void add(Node root,int value){
        //添加節(jié)點(diǎn)的值大于根節(jié)點(diǎn)的值，該節(jié)點(diǎn)添加到根節(jié)點(diǎn)的右子樹上
        if(value > root.value){
            //根節(jié)點(diǎn)的右子樹為空，直接添加
            if(root.right == null){
                root.right = new Node(value);
            }
            //根節(jié)點(diǎn)右子樹不為空，遞歸往右子樹插
            else{
                add(root.right,value);
            }
        }
        //添加節(jié)點(diǎn)的值小于或者等于根節(jié)點(diǎn)的值，該節(jié)點(diǎn)應(yīng)該添加到左子樹
        else{
            //左子樹為空，直接添加
            if(root.left == null){
                root.left = new Node(value);
            }
            //左子樹不為空，遞歸往左子樹添加
            else{
                add(root.left, value);
            }
        }
    }
    //此方法在類內(nèi)部和類外部都可以調(diào)用
    public void add(int value){
        //當(dāng)前樹為空樹
        if(root == null){
            root = new Node(value);
            return;
        }
        add(root, value);
    }

//中序遍歷樹
    private  void inPrevOrder(Node root){
        if(root == null) return;
        inPrevOrder(root.left);
        root.display();
        inPrevOrder(root.right);
    }
    public void inPrevOrder(){
        System.out.print("中序遍歷：");
        inPrevOrder(root);
    }

/**
     * 通過value查找二叉樹中的節(jié)點(diǎn)
     * @param root 被查找樹的根節(jié)點(diǎn)
     * @param value 要查找的值
     * @return 返回查找到的節(jié)點(diǎn)
     */
    private Node searchNode(Node root, int value){
        //被查找樹為null，要查找節(jié)點(diǎn)不存在
        if(root == null)
            return null;
        //找到了，返回節(jié)點(diǎn)
        else if(root.value == value){
            return root;
        }
        //該節(jié)點(diǎn)不是要查找節(jié)點(diǎn)，繼續(xù)查找
        else{
            //該節(jié)點(diǎn)的值大于value，往該節(jié)點(diǎn)的左子樹遞歸查找
            if(root.value > value){
                return searchNode(root.left, value);
            }
            //該節(jié)點(diǎn)的值小于value,往該節(jié)點(diǎn)的右子樹遞歸查找
            else{
                return searchNode(root.right, value);
            }
        }
    }

 /**
     * 查找某節(jié)點(diǎn)的父節(jié)點(diǎn)，并返回
     * @param root 被查找樹的根節(jié)點(diǎn)
     * @param node 要查找的節(jié)點(diǎn)
     * @return 返回被查找節(jié)點(diǎn)的父節(jié)點(diǎn)
     */
    private Node searchParentNode(Node root, Node node){
        //被查找樹為null或者根節(jié)點(diǎn)就是要查找的節(jié)點(diǎn)，那么要查找節(jié)點(diǎn)的父節(jié)點(diǎn)不存在
        if(root == null || root == node){
            return null;
        }
        else if(root.left != null && root.left == node || root.right != null && root.right == node){
            return root;
        }
        else{
            if(root.value > node.value){
                return searchParentNode(root.left, node);
            }
            else{
                return searchParentNode(root.right, node);
            }
        }
    }

public void remove(int vlaue){
        //找到要?jiǎng)h除的節(jié)點(diǎn)
        Node targetNode = searchNode(root,vlaue);
        //要?jiǎng)h除節(jié)點(diǎn)不存在
        if(targetNode == null) return;
        //找到要?jiǎng)h除節(jié)點(diǎn)的父節(jié)點(diǎn)
        Node targetNodeParent = searchParentNode(root,targetNode);
        //要?jiǎng)h除節(jié)點(diǎn)為葉子節(jié)點(diǎn)
        if(targetNode.left == null && targetNode.right == null){
            //要?jiǎng)h除的節(jié)點(diǎn)就是根節(jié)點(diǎn)
            if(targetNodeParent == null){
              root = null;
            }
            else{
                //要?jiǎng)h除節(jié)點(diǎn)是其父節(jié)點(diǎn)的左節(jié)點(diǎn)
                if(targetNodeParent.left == targetNode){
                    targetNodeParent.left = null;
                }
                else{
                    targetNodeParent.right = null;
                }
            }
        }
        //要?jiǎng)h除節(jié)點(diǎn)只有一個(gè)左子樹
        else if(targetNode.left != null && targetNode.right == null){
            //要?jiǎng)h除的節(jié)點(diǎn)就是根節(jié)點(diǎn)
            if(targetNodeParent == null) {
                root = root.left;
            }
            //要?jiǎng)h除節(jié)點(diǎn)是其父節(jié)點(diǎn)的左節(jié)點(diǎn)
            else if(targetNodeParent.left != null && targetNodeParent.left.value == targetNode.value){
                targetNodeParent.left = targetNode.left;
            }
            //要?jiǎng)h除節(jié)點(diǎn)是其父節(jié)點(diǎn)的右節(jié)點(diǎn)
            else{
                targetNodeParent.right = targetNode.left;
            }
        }
        //要?jiǎng)h除節(jié)點(diǎn)只有一個(gè)右子樹
        else if(targetNode.right != null && targetNode.left == null){
            //要?jiǎng)h除的節(jié)點(diǎn)就是根節(jié)點(diǎn)
            if(targetNodeParent == null) {
                root = root.right;
                return;
            }
            //要?jiǎng)h除節(jié)點(diǎn)是其父節(jié)點(diǎn)的左節(jié)點(diǎn)
            else if(targetNodeParent.left != null && targetNodeParent.left.value == targetNode.value){
                targetNodeParent.left = targetNode.right;
            }
            //要?jiǎng)h除節(jié)點(diǎn)是其父節(jié)點(diǎn)的右節(jié)點(diǎn)
            else{
                targetNodeParent.right = targetNode.right;
            }
        }
        //要?jiǎng)h除節(jié)點(diǎn)右左右都有節(jié)點(diǎn)
        else{
            //找到右子樹最小的節(jié)點(diǎn)
            Node minNode = targetNode.right;
            while(minNode.left != null){
                minNode = minNode.left;
            }
            int temp = minNode.value;
            //找到右子樹上最小節(jié)點(diǎn)的父節(jié)點(diǎn)
            Node minNodeParent = searchParentNode(targetNode.right,minNode);
            //右子樹根節(jié)點(diǎn)就是最小節(jié)點(diǎn)
            if(minNodeParent == null){
                targetNode.right = minNode.right;
            }
            else{
                //要?jiǎng)h除節(jié)點(diǎn)是其父節(jié)點(diǎn)的左節(jié)點(diǎn)
                minNodeParent.left = minNode.right;
            }
            targetNode.value = temp;
        }
    }