Java實現二叉搜索樹的插入、刪除

• 2022 年 1 月 14 日
• 筆記

前置知識

二叉樹的結構

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }
    }

中序遍歷

• 中序遍歷：對於每一個節點，遍歷順序是：左子樹->當前節點->右子樹
• 中序遍歷得到的第一個節點是沒有左子樹的（也許是葉子節點，也許有右子樹）
• 同理，中序遍歷的最後一個節點沒有右子樹

代碼遞歸實現

    public void inorder_traversal(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            inorder_traversal(root.left);
        }
        System.out.println(root.val);
        if (root.right != null) {
            inorder_traversal(root.right);
        }
    }

二叉搜索樹的定義

1. 左子樹的所有節點大於當前節點
2. 右子樹的所有節點小於當前節點
3. 每一個節點的值都不相同
4. 中序遍歷的結果是升序的

這些定義決定了它的優點：查找效率快，因為二叉搜索樹查找一個值時，自帶二分查找的方式

 下圖就是一個標準的二叉搜索樹

 查找節點

 給定一個值，使用循環在二叉搜索樹中查找，找到該節點為止

1. 從根節點開始，進行比較
2. 給定值大於根節點就找右子樹
3. 給定值小於根節點就找左子樹

代碼實現如下

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

 添加節點

 二叉搜索樹的添加是將新的節點作為葉子節點加入到其中，因為葉子節點的增加比較簡單。

1. 跟搜索過程類似，從根節點開始找，如果，如果小，找到一個適合新節點的位置
   1. 新節點的值比當前節點大（小），並且右（左）子樹為空，插入到當前節點的右（左）子樹中
   2. 如果當前節點的子樹不為空，繼續往下尋找
2. 然後使用一個pre節點，由pre節點作為父節點添加新節點

• 有可能要插入節點的二叉樹是一顆空樹，創建一個新的二叉樹
• 如果新節點的值已經存在二叉樹中，不需要進行添加

    public TreeNode insertInto(TreeNode root, int val) {
        
        if (root == null) {
            // 樹為空樹的情況
            return new TreeNode(val);
        }
        // 一個臨時節點指向根節點，用於返回值
        TreeNode tmp = root;
        TreeNode pre = root;
        
        while (root != null && root.val != val) {
            // 保存父節點
            pre = root;
            if (val > root.val) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        // 通過父節點添加
        if (val > pre.val) {
            pre.right = new TreeNode(val);
        } else {
            pre.left = new TreeNode(val);
        }
        return tmp;
    }

刪除節點

二叉搜索樹刪除節點的過程比較複雜，因為被刪除節點可能是以下三種情況

1. 葉子節點
2. 有一個子節點
3. 有兩個子節點

刪除葉子節點

直接搜索到相應的節點，然後刪除，葉子節點的刪除不影響樹的性質

有一個子節點的節點

將節點刪除，讓父節點連接子節點即可，因為子節點與父節點的關係 = 當前節點與父節點的關係，並不改變樹的性質

• 二叉搜索樹的定義決定了：當前節點 大於（小於） 父節點，那麼它的子節點 大於（小於） 父節點

過程像這張圖一樣 

刪除有兩個子節點的節點

我們可以通過交換節點的方式，讓要刪除節點和只有一個子節點的節點交換，刪除節點的操作就變成了上面的情況。

二叉搜索樹中序遍歷的結果是升序的，如果要交換，肯定要找中序遍歷在該節點左右兩邊的節點（值交換之後也滿足二叉搜索樹的定義）

• 中序遍歷的後（前）一個節點是右（左）子樹中序遍歷的第一個（最後一個）節點，而且它們都只有一個子節點

過程跟下面這張圖類似（與中序遍歷的後一個節點交換，並刪除這個節點）

代碼實現

    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode tmp = root;

        TreeNode pre = root;

        // 尋找要刪除的節點
        while (root != null && root.val != key) {
            pre = root;
            if (key > root.val) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        // 找不到符合的節點值
        if (root == null) {
            return tmp;
        }

        // 只有一個子節點或者沒有子節點的情況
        if (root.left == null || root.right == null) {
            if (root.left == null) {
                // 要刪除的是根節點，返回它的子節點
                if (root == tmp) {
                    return root.right;
                }
                // 使用父節點連接子節點，實現刪除當前節點
                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;
        }

        // 第一種方式
        // 尋找中序遍歷的後一個節點，也就是右子樹進行中序遍歷的第一個節點，右子樹的最左節點
        pre = root;
        TreeNode rootRight = root.right;
        while (rootRight.left != null) {
            pre = rootRight;
            rootRight = rootRight.left;
        }

        // 節點的值進行交換
        int tmpVal = rootRight.val;
        rootRight.val = root.val;
        root.val = tmpVal;

        // 中序遍歷的第一個節點肯定是沒有左子樹的，但是可能有右子樹，將右子樹連接到父節點上（相當於刪除有一個子節點的節點）
        if (pre.left == rootRight) {
            pre.left = rootRight.right;
        }else {
            pre.right = rootRight.right;
        }

        // 第二種方式
        // 尋找中序遍歷的前一個節點，也就是左子樹進行中序遍歷的最後一個節點，左子樹的最右節點
//        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;
//
//        // 中序遍歷的最後一個節點肯定是沒有右子樹的，但是可能有左子樹，將左子樹連接到父節點上（相當於刪除有一個子節點的節點）
//        if (pre.left == rootLeft) {
//            pre.left = rootLeft.left;
//        }else {
//            pre.right = rootLeft.left;
//        }

        return tmp;
    }