public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {
        }
        TreeNode(int val) {
            this.val = val;
        }
    }

中序遍歷

中序遍歷：從根節(jié)點(diǎn)開(kāi)始遍歷，遍歷順序是：左子樹(shù)->當(dāng)前節(jié)點(diǎn)->右子樹(shù)，在中序遍歷中，對(duì)每個(gè)節(jié)點(diǎn)來(lái)說(shuō)：

只有當(dāng)它的左子樹(shù)都被遍歷過(guò)了（或者沒(méi)有左子樹(shù)），它才會(huì)被遍歷到。
在遍歷右子樹(shù)之前，一定會(huì)先遍歷當(dāng)前節(jié)點(diǎn)。

中序遍歷得到的第一個(gè)節(jié)點(diǎn)是沒(méi)有左子樹(shù)的（也許是葉子節(jié)點(diǎn)，也許有右子樹(shù)）
同理，中序遍歷的最后一個(gè)節(jié)點(diǎn)沒(méi)有右子樹(shù)

代碼遞歸實(shí)現(xiàn)

List<TreeNode> list = new ArrayList<>();
    public void inorder_traversal(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            inorder_traversal(root.left);
        }
        list.add(root);
        if (root.right != null) {
            inorder_traversal(root.right);
        }
    }

二叉搜索樹(shù)的定義

對(duì)每一個(gè)節(jié)點(diǎn)而言，左子樹(shù)的所有節(jié)點(diǎn)小于它，右子樹(shù)的所有節(jié)點(diǎn)大于它
二叉樹(shù)中每一個(gè)節(jié)點(diǎn)的值都不相同
中序遍歷的結(jié)果是升序的

這些定義決定了它的優(yōu)點(diǎn)：查找效率快，因?yàn)槎嫠阉鳂?shù)查找一個(gè)值時(shí)，可以通過(guò)二分查找的方式，平均時(shí)間復(fù)雜度為log2(n),n是二叉樹(shù)的層樹(shù)

下圖就是一個(gè)標(biāo)準(zhǔn)的二叉搜索樹(shù)，右子樹(shù)比根節(jié)點(diǎn)大，左子樹(shù)比根節(jié)點(diǎn)小

查找節(jié)點(diǎn)

給定一個(gè)值，使用循環(huán)在二叉搜索樹(shù)中查找，找到該節(jié)點(diǎn)為止

從根節(jié)點(diǎn)開(kāi)始，不斷循環(huán)進(jìn)行比較
給定值大于當(dāng)前節(jié)點(diǎn)，就找右子樹(shù)，小于就找左子樹(shù)，值相等就是找到了節(jié)點(diǎn)

代碼實(shí)現(xiàn)如下

public TreeNode search(TreeNode root, int val) {
        // 節(jié)點(diǎn)不為空，且不等于特定值
        while(root != null && root.val != val){
            if(root.val > val){
                root = root.left;
            }else{
                root = root.right;
            }
        }
        return root;
    }

添加節(jié)點(diǎn)

設(shè)要添加的節(jié)點(diǎn)為b，二叉搜索樹(shù)的添加是將b作為葉子節(jié)點(diǎn)加入到其中，因?yàn)槿~子節(jié)點(diǎn)的增加比較簡(jiǎn)單。

跟搜索過(guò)程類似，從根節(jié)點(diǎn)開(kāi)始，不斷循環(huán)找，找到一個(gè)適合新節(jié)點(diǎn)的位置

b值比當(dāng)前節(jié)點(diǎn)大（?。⑶耶?dāng)前節(jié)點(diǎn)的右（左）子樹(shù)為空，將b插入到當(dāng)前節(jié)點(diǎn)的右（左）子樹(shù)中
如果當(dāng)前節(jié)點(diǎn)的子樹(shù)不為空，繼續(xù)往下尋找

使用一個(gè)隨著搜索過(guò)程，不斷更新的pre節(jié)點(diǎn)作為b的父節(jié)點(diǎn)，由pre節(jié)點(diǎn)添加b
有可能要插入節(jié)點(diǎn)的二叉樹(shù)是一顆空樹(shù)，創(chuàng)建一個(gè)新的二叉樹(shù)
如果二叉搜索樹(shù)中已經(jīng)有跟b相等的值，不需要進(jìn)行添加

 public TreeNode insertInto(TreeNode root, int val) {
        
        if (root == null) {
            // 樹(shù)為空樹(shù)的情況
            return new TreeNode(val);
        }
        // 一個(gè)臨時(shí)節(jié)點(diǎn)指向根節(jié)點(diǎn)，用于返回值
        TreeNode tmp = root;
        TreeNode pre = root;
        
        while (root != null && root.val != val) {
            // 保存父節(jié)點(diǎn)
            pre = root;
            if (val > root.val) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        // 通過(guò)父節(jié)點(diǎn)添加
        if (val > pre.val) {
            pre.right = new TreeNode(val);
        } else {
            pre.left = new TreeNode(val);
        }
        return tmp;
    }

刪除節(jié)點(diǎn)

刪除過(guò)程比較復(fù)雜，先設(shè)二叉搜索樹(shù)要?jiǎng)h除的節(jié)點(diǎn)為a，a有以下三種情況

a為葉子節(jié)點(diǎn)
a有一個(gè)子節(jié)點(diǎn)
a有兩個(gè)子節(jié)點(diǎn)刪除葉子節(jié)點(diǎn)

過(guò)程類似搜索節(jié)點(diǎn)，找到到a后，通過(guò)它的父節(jié)點(diǎn)刪除，并且葉子節(jié)點(diǎn)的刪除不影響樹(shù)的性質(zhì)

有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)

要將a刪除，并且保留a的子節(jié)點(diǎn)，讓它的父節(jié)點(diǎn)連接它的子節(jié)點(diǎn)即可，因?yàn)閍的子節(jié)點(diǎn) 與 a的父節(jié)點(diǎn) 關(guān)系 == a與 a的父節(jié)點(diǎn) 關(guān)系，所以不改變樹(shù)的性質(zhì)

二叉搜索樹(shù)的定義決定了：對(duì)于每一個(gè)節(jié)點(diǎn)而言，它大于（小于）它的父節(jié)點(diǎn)，那么它的子節(jié)點(diǎn) 大于（小于）它的父節(jié)點(diǎn)

過(guò)程像這張圖一樣

刪除有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)

我們可以通過(guò)交換節(jié)點(diǎn)的方式，讓a 和只有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn) 交換，刪除a的操作就變成了上面第二種情況。

我們知道中序遍歷二叉搜索樹(shù)的結(jié)果是升序的，如果要交換，肯定要找中序遍歷在a左右兩邊的節(jié)點(diǎn)（因?yàn)橹到粨Q之后也滿足二叉搜索樹(shù)的定義）

中序遍歷的后（前）一個(gè)節(jié)點(diǎn)是右（左）子樹(shù)中序遍歷的第一個(gè)（最后一個(gè)）節(jié)點(diǎn)，而且它們都只有一個(gè)子節(jié)點(diǎn)

過(guò)程跟下面這張圖類似（a的值與中序遍歷的后一個(gè)節(jié)點(diǎn)交換，并刪除這個(gè)節(jié)點(diǎn)）

代碼實(shí)現(xiàn)

public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode tmp = root;
        TreeNode pre = root;
        // 尋找要?jiǎng)h除的節(jié)點(diǎn)
        while (root != null && root.val != key) {
            pre = root;
            if (key > root.val) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        // 找不到符合的節(jié)點(diǎn)值
        if (root == null) {
            return tmp;
        }
        // 只有一個(gè)子節(jié)點(diǎn)或者沒(méi)有子節(jié)點(diǎn)的情況
        if (root.left == null || root.right == null) {
            if (root.left == null) {
                // 要?jiǎng)h除的是根節(jié)點(diǎn)，返回它的子節(jié)點(diǎn)
                if (root == tmp) {
                    return root.right;
                }
                // 使用父節(jié)點(diǎn)連接子節(jié)點(diǎn)，實(shí)現(xiàn)刪除當(dāng)前節(jié)點(diǎn)
                if (pre.left == root) {
                    pre.left = root.right;
                } else {
                    pre.right = root.right;
                }
            } else {
                if (root == tmp) {
                    return root.left;
                }
                if (pre.left == root) {
                    pre.left = root.left;
                } else {
                    pre.right = root.left;
                }
            }
            return tmp;
        }
        // 第一種方式
        // 尋找中序遍歷的后一個(gè)節(jié)點(diǎn)，也就是右子樹(shù)進(jìn)行中序遍歷的第一個(gè)節(jié)點(diǎn)，右子樹(shù)的最左節(jié)點(diǎn)
        pre = root;
        TreeNode rootRight = root.right;
        while (rootRight.left != null) {
            pre = rootRight;
            rootRight = rootRight.left;
        }
        // 節(jié)點(diǎn)的值進(jìn)行交換
        int tmpVal = rootRight.val;
        rootRight.val = root.val;
        root.val = tmpVal;
        // 中序遍歷的第一個(gè)節(jié)點(diǎn)肯定是沒(méi)有左子樹(shù)的，但是可能有右子樹(shù)，將右子樹(shù)連接到父節(jié)點(diǎn)上（相當(dāng)于刪除有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)）
        if (pre.left == rootRight) {
            pre.left = rootRight.right;
        }else {
            pre.right = rootRight.right;
        }
        // 第二種方式
        // 尋找中序遍歷的前一個(gè)節(jié)點(diǎn)，也就是左子樹(shù)進(jìn)行中序遍歷的最后一個(gè)節(jié)點(diǎn)，左子樹(shù)的最右節(jié)點(diǎn)
//        pre = root;
//        TreeNode rootLeft = root.left;
//        while (rootLeft.right != null){
//            pre = rootLeft;
//            rootLeft = rootLeft.right;
//        }
//
//        int tmpVal = rootLeft.val;
//        rootLeft.val = root.val;
//        root.val = tmpVal;
//
//        // 中序遍歷的最后一個(gè)節(jié)點(diǎn)肯定是沒(méi)有右子樹(shù)的，但是可能有左子樹(shù)，將左子樹(shù)連接到父節(jié)點(diǎn)上（相當(dāng)于刪除有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)）
//        if (pre.left == rootLeft) {
//            pre.left = rootLeft.left;
//        }else {
//            pre.right = rootLeft.left;
//        }
        return tmp;
    }

到此這篇關(guān)于Java實(shí)現(xiàn)二叉搜索樹(shù)的插入、刪除的文章就介紹到這了,更多相關(guān)Java二叉搜索樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: