二叉搜索樹詳解

二叉搜索樹（Binary Search Tree）也叫二叉查找樹，他是具有下列性質的一種二叉樹。

二叉搜索樹有一個重要特性就是他的中序遍歷結果一定是有序的。如上圖，二叉搜索樹的中序遍歷結果是 [1,3,4,6,8,9] 。

二叉搜索樹的查找：

二叉搜索樹的查找可以通過遞歸的方式，也可以通過 while 循環的方式，原理都一樣，如下圖所示，步驟如下：

來看下代碼：

private TreeNode searchBST(TreeNode root, int val) {
    if (root == null) { // 查找不成功。
        return null;
    } else if (val == root.val) { // 查找成功。
        return root;
    } else if (val < root.val) // 左子樹找。
        return searchBST(root.left, val);
    else // 右子樹找
        return searchBST(root.right, val);
}

二叉搜索樹的插入：

二叉搜索樹插入的時候首先要找到他需要插入的位置，然後在插入，如下圖所示，步驟如下：

代碼如下：

 private TreeNode insertBST(TreeNode root, int val) {
     if (root == null)// 如果爲空，創建一個新的節點。
         return new TreeNode(val);
     else if (val < root.val)// 插入左子樹。
         root.left = insertBST(root.left, val);
     else // 插入右子樹。
         root.right = insertBST(root.right, val);
     return root;
 }

這裏使用的是遞歸的方式，遞歸在遞歸章節中有介紹，如果看不明白，還可以使用非遞歸。

private TreeNode insertBST(TreeNode root, int val) {
    TreeNode newNode = new TreeNode(val);// 創建要插入的節點。
    if (root == null)// 如果root爲空，直接返回。
        return newNode;
    TreeNode cur = root;// 當前節點，始終是變動的。
    while (true) {
        if (val < cur.val) {// 在左子樹查找插入位置。
            if (cur.left == null) {
                cur.left = newNode;// 左子樹爲空，就插入到左子樹中。
                break;// 終止循環。
            } else {
                cur = cur.left;// 左子樹不爲空，就在左子樹中查找。
            }
        } else {// 在右子樹查找插入位置，同上。
            if (cur.right == null) {
                cur.right = newNode;
                break;
            } else {
                cur = cur.right;
            }
        }
    }
    return root;
}

二叉搜索樹的刪除：

二叉樹的刪除相對來說要麻煩一些，如果刪除的是葉子節點，可以直接刪除。如果刪除的節點只有一個子節點，讓這個僅有的子節點替代他。如果刪除的節點有兩個子節點，就需要考慮刪除當前節點後子節點該怎麼存放。刪除有兩種實現方式，一種是直接刪除需要刪除的節點，一種是使用移形換位法，直接刪除有個缺點就是會導致樹嚴重不平衡，在後面我們講 AVL 樹和紅黑樹的時候使用的都是移形換位法。這裏我們先來講下直接刪除是怎麼操作的。

在講解二叉搜索樹的刪除之前我們先來了解一下二叉樹的前驅節點和後繼節點。

前驅節點：對一棵二叉樹進行中序遍歷，遍歷後的結果中，當前節點的前一個節點爲該節點的前驅節點；

後繼節點：對一棵二叉樹進行中序遍歷，遍歷後的結果中，當前節點的後一個節點爲該節點的後繼節點；

如上圖所示，二叉樹中節點 4 的前驅節點是 3 ，後繼節點是 5 。假設要刪除節點 4 ，有兩種方式。一種是讓待刪除節點的右子節點成爲他前驅節點的右子節點，這樣待刪除的節點就只有一個子節點了，如下圖所示。

還一種是讓待刪除節點的左子節點成爲他後繼節點的左子節點，如圖下圖所示。

這裏的關鍵是怎麼查找一個節點的前驅節點和後繼節點，有的同學認爲通過打印二叉樹的中序遍歷結果即可找到，確實可以找到，實際上不需要那麼麻煩。一個節點的前驅節點是他左子樹中的最大節點，這個節點就是他左子樹往右一直走下去的節點。同理一個節點的後繼節點就是他右子樹的最小節點，這個節點就是他右子樹往左一直走下去的節點。

 // 查找節點treeNode的前驅節點。
 static TreeNode preNode(TreeNode treeNode) {
     TreeNode leftBig = treeNode.left;
     while (leftBig.right != null)
         leftBig = leftBig.right;
     return leftBig;
 }
 
 // 查找節點treeNode的後繼節點。
 static TreeNode postNode(TreeNode treeNode) {
     TreeNode rightSmall = treeNode.right;
     while (rightSmall.left != null)
         rightSmall = rightSmall.left;
     return rightSmall;
 }

找到前驅節點或者後繼節點，就可以刪除了，刪除的步驟如下，假設刪除的節點是 p ：

public TreeNode deleteNode(TreeNode root, int val) {
    if (root == null)
        return null;
    if (root.val == val) {
        // 這裏把 root 是葉子節點和 root 只有一個子節點合併了。
        if (root.left == null)
            return root.right;
        if (root.right == null)
            return root.left;

        // 這裏 root 有兩個子節點，找到 root 的前驅節點。
        TreeNode leftBig = root.left;
        while (leftBig.right != null)
            leftBig = leftBig.right;
        // 讓root的右子節點成爲他前驅節點的右子節點。
        leftBig.right = root.right;
        // 直接返回要刪除節點的左子樹。
        return root.left;
    } else if (val < root.val) {
        // 要刪除的節點在左子樹上。
        root.left = deleteNode(root.left, val);
        return root;
    } else {
        // 要刪除的節點在右子樹上。
        root.right = deleteNode(root.right, val);
        return root;
    }
}

刪除節點一般有兩種實現方式，一種就是上面講的，但這種有個缺點，就是會嚴重破壞樹的平衡性。還一種就是移形換位，不是把待刪除的節點給刪除，而是用他的前驅或者後繼節點的值來替換他，然後把這個前驅或後繼節點給刪除，後面我們講 AVL 樹和紅黑樹的時候會用這種方式。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/KZAqTgD6i1IgjEN4Ky5rKg

猜你喜歡