Java簡單幾步實現(xiàn)一個二叉搜索樹

更新時間：2023年02月08日 15:34:40 作者：程序猿教你打籃球

二叉樹包含了根節(jié)點,孩子節(jié)點,葉節(jié)點,每一個二叉樹只有一個根節(jié)點,每一個結(jié)點最多只有兩個節(jié)點,左子樹的鍵值小于根的鍵值,右子樹的鍵值大于根的鍵值,下面這篇文章主要給大家介紹了關(guān)于如何在Java中實現(xiàn)二叉搜索樹的相關(guān)資料,需要的朋友可以參考下

1、認識二叉搜索樹

從字面上來看，它只比二叉樹多了搜索兩個字，我們回想一下，如果要是在二叉樹中查找一個元素的話，需要遍歷這棵樹，效率很慢，而二叉搜索樹，則會效率高很多，為什么呢？

二叉搜索樹，可以是一棵空樹，或者是具有以下的性質(zhì)：

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

通俗來講，左孩子都小于父節(jié)點，右孩子都大于父節(jié)點，以此類推，這里我們畫圖來認識下二叉搜索樹：

當然二叉搜索樹不要求是完全二叉樹或滿二叉樹，甚至?xí)霈F(xiàn)單分支的二叉搜索樹，所以針對這種特殊的情況進行了優(yōu)化也就延申而來的 AVL樹，這個是后續(xù)的話題。

仔細觀察上圖，可以觀察出二叉搜索樹的一個新特性：

中序遍歷二叉搜索樹是有序的，所以二叉搜索樹也被稱為二叉排序樹。

2、實現(xiàn)一個二叉搜索樹

2.1 成員變量

public class BinarySearchTree {
    private TreeNode root; //存放根節(jié)點
    private static class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;
        private TreeNode(int val) {
            this.val = val;
        }
    }
}

這里跟我們的二叉樹成員變量大同小異，主要是去實現(xiàn)插入，查找，刪除的邏輯。

2.2 insert 方法

往二叉搜索樹插入一個節(jié)點的時候，我們要注意兩點，首先如果二叉搜索樹為空，則直接令 root 為當前插入的節(jié)點即可，那如果二叉搜索樹不為空，我們則需要利用二叉搜索樹的性質(zhì)，找到該節(jié)點要插入的位置即可，具體我們來看下圖：

通過動圖我們可以看到，當二叉搜索樹不為空的時候，新的元素會依次節(jié)點比較，如果比根節(jié)點大，則去根的右邊，比根節(jié)點小，則取根的左邊，以此類推。(搜索二叉樹不存在相同的元素)

但是我們用代碼如何實現(xiàn)呢？定義一個 cur 引用，當 cur 等于 null 了，則表示是我要插入的位置，既然找到了要插入的位置，但是還得知道這個位置的父節(jié)點是誰，通過父節(jié)點的指針域給連接起來，于是代碼可以這樣寫：

public boolean insert(int key) {
    // 二叉搜索樹沒有節(jié)點的情況
    if (root == null) {
        root = new TreeNode(key);
        return true;
    }
    // 二叉搜索樹不為空的情況 -> 找到該節(jié)點要插入的位置進行插入
    // 如果已經(jīng)存在該節(jié)點了, 則不用插入 -> 二叉搜索樹中不能出現(xiàn)重復(fù)值
    TreeNode parent = null; // 記錄cur的父節(jié)點
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val < key) {
            parent = cur;
            cur = cur.right;
        } else if (cur.val > key) {
            parent = cur;
            cur = cur.left;
        } else {
            return false; // 插入重復(fù)的節(jié)點
        }
    }
    // 走到這, cur為空了, key 需要插入到 parent 的左節(jié)點或右節(jié)點中
    TreeNode newNode = new TreeNode(key);
    if (parent.val < key) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }
    return true;
}

2.3 search 方法

搜索方法，也就是給一個 key 你，讓你在這顆二叉樹找有沒有這個元素，有的話返回該節(jié)點，沒有的話返回 null，這個就很簡單了，跟上面的步驟一樣無非就是碰到相同的元素返回 cur 嘛，當 cur 根據(jù) key 遍歷完這棵二叉搜索樹的時候，也就是 cur 為 null 了，則表示沒有該元素，直接返回 null即可。

代碼如下：

public TreeNode search(int key) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val < key) {
            cur = cur.right;
        } else if (cur.val > key) {
            cur = cur.left;
        } else {
            return cur;
        }
    }
    return null;
}

2.4 remove 方法(重點)

在二叉搜索樹中，刪除一個節(jié)點是一個比較麻煩的事，但是只要把各種刪除的情況下列舉出來，一一解決它即可，對于二叉搜索樹來說，你刪除了一個節(jié)點，它仍然滿足二叉搜索樹的性質(zhì)。

設(shè) cur 為要刪除的節(jié)點，所以首先我們得判斷這個二叉搜索樹中，是否存在要刪除的節(jié)點，這個邏輯上面已經(jīng)寫過了，找到要刪除的節(jié)點后，我們一共會面臨三種情況：

① 如果 cur 沒有左子樹的情況

如果 cur 是 root 的情況，只需要 root = cur.right
如果 cur 不是 root，cur 是 parent.left 的情況，只需要 parent.left = cur.right
如果 cur 不是 root，cur 是 parent.right 的情況，只需要 parent.right = cur.right

圖解：

② 如果 cur 沒有右子樹的情況

如果 cur 是 root 的情況，只需要 root = cur.left
如果 cur 不是 root，cur 是 parent.left 的情況，只需要 parent.left = cur.left
如果 cur 不是 root，cur 是 parent.right 的情況，只需要 parent.right = cur.left

圖解：

③ 如果 cur 既有左子樹，又有右子樹的情況

使用替換法進行刪除，即在 cur 的右子樹中，一直往左尋找最小的元素，將這個最小值賦值給要刪除節(jié)點的 val 值中，接著把這個最小元素的節(jié)點刪除即可，刪除的邏輯見下圖和完整刪除代碼。

代碼如下：

public boolean remove(int key) {
    TreeNode parent = null;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val < key) {
            parent = cur;
            cur = cur.right;
        } else if (cur.val > key) {
            parent = cur;
            cur = cur.left;
        } else {
            removeNode(parent, cur);
            return true;
        }
    }
    return false;
}
private void removeNode(TreeNode parent, TreeNode cur) {
    if (cur.left == null) {
        if (cur == root) {
            root = cur.right;
        } else if (cur == parent.left) {
            parent.left = cur.right;
        } else {
            parent.right = cur.right;
        }
    } else if (cur.right == null) {
        if (cur == root) {
            root = cur.left;
        } else if (cur == parent.left) {
            parent.left = cur.left;
        } else {
            parent.right = cur.left;
        }
    } else {
        TreeNode target = cur.right;
        TreeNode targetParent = cur;
        while (target.left != null) {
            targetParent = target;
            target = target.left;
        }
        // 走到這, target就是要刪除節(jié)點的右子樹中最小的節(jié)點, 接下來進行覆蓋
        cur.val = target.val;
        // 覆蓋完成, 現(xiàn)在需要刪除 target 節(jié)點
        // 如果 cur.right 沒有左孩子的情況, 此時的target就是cur.right
        // 即直接將 cur.right 覆蓋到 cur 位置, 也就是滿足 target == targetParent.right 條件
        // 所以需要進行特殊處理.
        if (target == targetParent.right) {
            targetParent.right = target.right;
        } else {
            targetParent.left = target.right;
        }
    }
}

3、二叉搜索樹總結(jié)

二叉搜索樹在最好的情況下為完全二叉樹，查找的平均比較次數(shù)為：logn

二叉搜索樹在最差的情況下退化成但分支，查找的平均比較次數(shù)為：n/2

所以二叉搜索樹在最差的情況下效率是不高的，為了解決單分支的情況，于是有了 AVL樹，當發(fā)現(xiàn)二叉搜索樹左右子樹高度差太大，會自動旋轉(zhuǎn)，以致平衡，避免旋轉(zhuǎn)的次數(shù)太多，又引入了紅黑樹，給節(jié)點增加了顏色，細節(jié)部分后期講解，這里有個概念即可，下期將會介紹由紅黑樹作為底層的集合：TreeSet 和 TreeMap

下期預(yù)告：【Java 數(shù)據(jù)結(jié)構(gòu)】TreeSet 和 TreeMap

到此這篇關(guān)于Java簡單幾步實現(xiàn)一個二叉搜索樹的文章就介紹到這了,更多相關(guān)Java二叉搜索樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: