目錄

1.概念

2.圖解：

3.元素插入操作

1.思路分析：

2.代碼展示：

4.元素查找操作

1.前提根節(jié)點(diǎn)不為空

2.代碼展示：

5.查找BST中的最大最小值

代碼展示：

6.刪除BST中的最大最小值

代碼展示：

7.刪除BST中的任意元素

代碼展示：

?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-408345.html

1.概念

二叉搜索樹(shù)又稱二叉排序樹(shù)，它或者是一棵空樹(shù)，或者是具有以下性質(zhì)的二叉樹(shù):

• 若它的左子樹(shù)不為空，則左子樹(shù)上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值
• 若它的右子樹(shù)不為空，則右子樹(shù)上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值
• 它的左右子樹(shù)也分別為二叉搜索樹(shù)

?

2.圖解：

以下數(shù)組為例 ：int [] arr = [5,3,4,1,7,8,6]

?

?

3.元素插入操作

1.思路分析：

1. 如果樹(shù)為空樹(shù)，即根?== null，直接插入
2. ?如果樹(shù)不是空樹(shù)，按照查找邏輯確定插入位置，插入新結(jié)點(diǎn)

2.代碼展示：

    //在二分搜索樹(shù)中添加元素
    public void add(int val){
        root = add(root,val);
    }

    private Node add(Node root, int val){
        if(root == null){
            Node node = new Node(val);
            userSize++;
            return node;
        }else if(val < root.val){
            root.left = add(root.left, val);
            return root;
        }else{
            root.right = add(root.right,val);
            return root;
        }
    }

4.元素查找操作

1.前提根節(jié)點(diǎn)不為空

• root.val == key 返回true;
• key > root.val ?root= root.right;繼續(xù)查找
• key <?root.val ?root= root.left;繼續(xù)查找

2.代碼展示：

    //判斷某元素是否在二叉搜索樹(shù)中
    public boolean contains(int val){
        return contains(root,val);
    }

    private boolean contains(Node root, int val){
        if(root == null){
            return false;
        }else if (root.val == val){
            return true;
        }else if(val < root.val){
            return contains(root.left,val);
        }else {
            return contains(root.right,val);
        }
    }

5.查找BST中的最大最小值

• 最大值一定在最右邊，且右子樹(shù)為空，順著右子樹(shù)往下尋找即可
• 最小值一定在最左邊，且左子樹(shù)為空，順著左子樹(shù)往下尋找即可

代碼展示：

    public int min(){
        return findMin(root).val;
    }
    public int max(){
        return findMax(root).val;
    }
    private Node findMin(Node root){
        if(root == null){
            throw new NoSuchElementException("沒(méi)有元素哇~~");
        }
        Node x = root;
        while(x.left != null){
            x = x.left;
        }
        return x;
    }

    private Node findMax(Node root){
        if(this.root == null){
            throw new NoSuchElementException("沒(méi)有元素哇~~");
        }
        Node x = this.root;
        while(x.right != null){
            x = x.right;
        }
        return x;
    }

6.刪除BST中的最大最小值

1. 刪除最大值，找到最大值所在的節(jié)點(diǎn)，將其左子樹(shù)記錄下來(lái)，將最大值所在節(jié)點(diǎn)和其左子樹(shù)置空，返回記錄下來(lái)的左子樹(shù)給其父節(jié)點(diǎn)
2. 刪除最小值，找到最小值所在的節(jié)點(diǎn)，將其右子樹(shù)記錄下來(lái)，將最小值所在節(jié)點(diǎn)和其右子樹(shù)置空，返回記錄下來(lái)的右子樹(shù)給其父節(jié)點(diǎn)

代碼展示：

    //刪除最大值
    public void removeMax(){
        removeMax(root);
    }

    private Node removeMax(Node root){
        if(root == null){
            return null;
        }
        if(root.right == null){
            Node left = root.left;
            root.right = root = null;
            userSize--;
            return left;
        }
        root.right = removeMax(root.right);
        return root;
    }

    //刪除最小值
    public void removeMin(){
        removeMin(root);
    }

    private Node removeMin(Node root) {
        if(root == null){
            return null;
        }
        if(root.left == null){
            Node right = root.right;
            root.left = root = null;
            userSize--;
            return right;
        }
        root.left = removeMin(root.left);

        return root;
    }

7.刪除BST中的任意元素

• 先在二叉搜索樹(shù)中尋找需要被刪除的元素，不存在返回null
• 判斷被刪除的元素是否左右子樹(shù)有為空的情況，有則按照刪除最大最小值的操作來(lái)刪除當(dāng)前元素
• 若左右子樹(shù)都不為空，則需要在BST中尋找一個(gè)新節(jié)點(diǎn)，將其右邊連接刪除新節(jié)點(diǎn)后的右子樹(shù)，
• 左邊鏈接左子樹(shù)，最后將root,root.left.root.right全部置空，返回新節(jié)點(diǎn)即可

代碼展示：

    //在二叉搜索樹(shù)中刪除元素
    public void remove(int val){
        root = remove(root,val);
    }

    private Node remove(Node root, int val) {
        if(root == null){
            return root;
        }else if(val < root.val){
            root.left =  remove(root.left,val);
            return root;
        }else if(val > root.val){
            root.right = remove(root.right,val);
            return root;
        }else {
            //當(dāng)前節(jié)點(diǎn)就是被刪除的節(jié)點(diǎn)
            if(root.right == null){
                //刪除最小值的操作一樣
                Node left = root.left;
                root.left = root = null;
                userSize--;
                return left;
            }else if(root.left == null){
                Node right = root.right;
                root.right = root = null;
                userSize--;
                return right;
            }else {
                //左右兩邊都有子樹(shù)
                Node prev = findMin(root.right);
                prev.right = removeMin(root.right);
                prev.left = root.left;
                root.right = root.left = root = null;
                return prev;
            }
        }
    }

?

?

?

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】二叉搜索樹(shù)BST的實(shí)現(xiàn)（遞歸）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！