二叉搜索树(BTS)创建,遍历与删除(java实现)

需求:给定一个数列,需要存储,要求方便查询与添加

数组固定容量,不便添加

链表方便添加,却不便查询

二叉搜索树:

对于每一个非叶子节点,左子节点的数都小于该节点的数,右子节点的数都大于该节点的数

一.添加

有两种方式

递归和循环

每次添加数时进行比较,小的放左边大的放右边

二.删除

删除得考虑三种情况

1.目标节点是叶子节点,找到其父节点直接置空

2.目标节点含一颗子树.还是其父节点直接指向目标节点的下一个节点

3.目标节点含左右两颗子树,得从该节点的右节点出发找到右子树最小的数,记录下来,并删除,将最小值给目标节点

上代码

class BinarySortTree{
    TreeNode root;//根节点
    BinarySortTree(){}

    /**
     * 循环创建二叉树
     * @param val
     */
    public void addNode1(int val){
        if(root == null){
            root = new TreeNode(val);
            return;
        }
        TreeNode cur = root;
        while (cur!=null){
            if(val<=cur.val){
                if(cur.left==null){
                    cur.left = new TreeNode(val);
                    break;
                }else {
                    cur = cur.left;

                }
            }else {
                if(cur.right==null){
                    cur.right = new TreeNode(val);
                    break;
                }else {
                    cur = cur.right;
                }
            }
        }

    }

    /**
     * 递归创建二叉树
     * @param val
     */
    public void addNode2(int val){
        root = add2(root,val);
    }
    private TreeNode add2(TreeNode node,int val){
        if(node == null){
            return new TreeNode(val);
        }
        if(val<=node.val){
            node.left = add2(node.left,val);
        }else {
            node.right = add2(node.right,val);
        }
        return node;
    }

    /**
     * 删除二叉树中的任意节点
     * @param val
     */
    public void deleteNode(int val){
        if(root == null)
            return;
        TreeNode target = search(val);
        if(target == null)
            return ;
        if(root.left == null&&root.right == null){
            root = null;
            return;
        }

        TreeNode parent = searchParent(val);
        if(target.left == null&&target.right == null){
            if(target == parent.left)
                parent.left = null;
            else if(target == parent.right)
                parent.right = null;
        }else if(target.left!=null&&target.right!=null){
            int minVal = deleteRightTreeMin(target.right);//向右寻找最小值
            target.val = minVal;
        }else{
            if(target.left!=null){
                if(parent.left == target)
                    parent.left = target.left;
                else
                    parent.right = target.left;
            }else {
                if(parent.left == target)
                    parent.left = target.right;
                else
                    parent.right = target.right;
            }
        }
    }
    /**
     * 搜索待删除的目标节点
     * @param val
     * @return
     */
    public TreeNode search(int val){
        TreeNode cur = root;
        if(cur.val == val){
            return cur;
        }
        while(cur!=null){
            if(cur.val == val)
                return cur;
            else if(cur.val>val){
                cur = cur.left;
            }else {
                cur = cur.right;
            }
        }
        return null;
    }

    /**
     * 搜索待删除节点的父节点
     * @param val
     * @return
     */
    public TreeNode searchParent(int val){
        TreeNode cur = root;
        if((cur.left!=null&&cur.left.val==val)||(cur.right!=null&&cur.right.val==val)){
            return cur;
        }
        while(cur.left!=null||cur.right!=null){
            if((cur.left!=null&&cur.left.val==val)||(cur.right!=null&&cur.right.val==val)){
                return cur;
            }
            else if(cur.val>val&&cur.left!=null){
                cur = cur.left;
            }else if(cur.val<val&&cur.right!=null){
                cur = cur.right;
            }else
                return null;
        }
        return null;
    }

    /**
     * 从右子树出发寻找最小值并删除
     * @param node
     * @return
     */
    public int deleteRightTreeMin(TreeNode node){
        TreeNode target = node;
        while(target.left!=null){//向左寻找,因为最小值存储在左边
            target = target.left;
        }
        deleteNode(target.val);
        return target.val;
    }

    /**
     * 中序遍历二叉树,获得从小到大的数列
     * @param node
     */
    public void infixOrder(TreeNode node){
        if(node == null)
            return;
        infixOrder(node.left);
        System.out.println(node.val);
        infixOrder(node.right);
    }
}
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(){}
    TreeNode(int val){
        this.val = val;
    }
}