📢博客主頁：🏀敲代碼的布萊恩特🏀
📢歡迎點贊 👍 收藏 ?留言 📝 歡迎討論！👏
📢本文由 【敲代碼的布萊恩特】 原創，首發于 CSDN🙉🙉🙉
📢由于博主是在學小白一枚，難免會有錯誤，有任何問題歡迎評論區留言指出，感激不盡！?
📖精品專欄（不定時更新）【JavaSE】 【Java資料結構】【LeetCode】

🛸搜索二叉樹——基本概念

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

1. 若它的左子樹不為空，則左子樹上所有節點的值都小于根節點的值
2. 若它的右子樹不為空，則右子樹上所有節點的值都大于根節點的值
3. 它的 左右子樹也分別為二叉搜索樹

注意：二叉搜索樹中沒有重復的元素

如下圖為一個二叉搜索樹

🛸搜索二叉樹——基本屬性

二叉樹是由一個一個節點組成的，先定義好節點的屬性

代碼實作：

public class Node{
        int key;//節點值
        Node left;//左孩子節點
        Node right;//右孩子節點

        public Node(int key){//重寫一下節點的構造方法
            this.key = key;
        }
    }

    Node root = null;//一開始根節點為空

🛸搜索二叉樹——查找節點

查找程序：

1. 拿著待查元素和根節點比較；
2. 如果比根節點小，繼續在左子樹中查找；
3. 如果比根節點大，繼續在右子樹中查找；
4. 如果當前元素查找到null也沒找到，說明該元素不存在，

代碼實作：

/**
     * 在搜索樹中查找 key，如果找到，回傳 key 所在的結點，否則回傳 null
     * @param key
     * @return
     */
    public Node search(int key){
        Node cur = root;//cur從root開始走
        while(cur != null){
            if(cur.key == key){//如果cur的值與key相等，則回傳cur
                return cur;
            }else if(key > cur.key){//key值比cur的值大，cur往右節點走
                cur = cur.right;
            }else if(key < cur.key){//key值比cur的值小，cur往左節點走
                cur = cur.left;
            }
        }
        return null;//root為空，或者二叉樹里沒有這個節點，回傳空值
    }

🛸搜索二叉樹——插入節點

插入程序：

1. 如果樹是空樹，即根== null，直接插入即可，回傳true
2. 如果樹不是空樹，按照 查找邏輯（大的放左邊，小的放右邊） 確定插入位置，插入新結點
   注意：最后確定的插入位置一定是葉子節點

代碼實作：

/**
     * 插入
     * @param key
     * @return true 表示插入成功, false 表示插入失敗
     */
    public Boolean insert(int key){
        if(root == null){//如果根節點空，則第一個節點就是根節點
            root = new Node(key);
            return true;
        }

        Node cur = root;//用cur從root位置開始往下走
        Node parent = null;//需要用一個parent節點來記錄上一個節點
        //通過while回圈來找插入位置
        while(cur != null){
            if (key == cur.key){
                return false;//如果二叉樹里已經有這個值，就無法插入
            }
            else if (key < cur.key){//key比cur的值小，說明要插到左邊
                parent = cur;//記錄上一個節點
                cur = cur.left;//cur往左走
            }
            else if (key > cur.key){//key比cur的值大，說明要插到右邊
                parent = cur;//記錄上一個節點
                cur = cur.right;//cur往右走
            }
        }
        //while走完了，說明是時候插入節點了，因為我們插入節點的位置一定是葉子節點的位置
        //這就需要用到parent了
        Node node = new Node(key);//創建要插入的新節點
        if (node.key > parent.key){//比parent值大放右邊
            parent.right = node;
        }else {
            parent.left = node;//反之放左邊
        }
        return true;//插入成功
    }

🛸搜索二叉樹——洗掉節點

設待洗掉結點為 cur, 待洗掉結點的雙親結點為 parent，洗掉節點的關鍵在于對多種情況的分析

1. cur.left == null 待洗掉節點只有右子樹
   （這種情況下刪哪個點，就將其右子樹接到這個點的父節點后邊）
   

2. cur.right == null 待洗掉節點 只有左子樹
   （這種情況下刪哪個點，就將其左子樹接到這個點的父節點后邊）
   

3. cur.left != null && cur.right != null 待洗掉節點左右子樹都存在
   （需要使用替換法進行洗掉，即在它的右子樹中尋找最小值結點，用它的值填補到被洗掉節點中，再來處理該結點的洗掉問題，關鍵就在于這個尋找最小值替代這一步）

總而言之，這第三種情況處理方法就是，從待洗掉點的右樹里找最小值來替換待洗掉點，然后將替罪羊節點的右樹接到替罪羊節點的父節點后邊即可，注意點就是替罪羊節點是在父節點左邊還是右邊

代碼實作：

/**
     * 洗掉成功回傳 true，失敗回傳 false
     * @param key
     * @return
     */
    public void removeKey(int key) {
        if(root == null) {
            return;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if(cur.key == key) {
                remove(parent,cur);
                return;
            }else if(cur.key < key){
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
    }

    private void remove(Node parent, Node cur) {
        if (cur.left == null){//洗掉只有右孩子的節點
            if (cur == root){//要洗掉的點是根節點
                root = cur.right;
            }
            else if (cur == parent.left){//要洗掉的點在父親節點左邊
                parent.left = cur.right;
            }
            else if (cur == parent.right){//要洗掉的點在父親節點右邊
                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 if(cur == parent.right){//要洗掉的點在父親節點右邊
                parent.right = cur.left;
            }
        }
        else {
            Node target = cur.right;
            Node targetParent = cur;
            //找替罪羊target，找右樹的最小左子樹
            while(target.left != null){
                targetParent = target;
                target = target.left;
            }
            cur.key = target.key;
            if(target == targetParent.left){//如果當前目標值是父節點的左孩子
                targetParent.left = target.right;//就把目標節點的右孩子接到父節點的左邊
            }
            else if(target == targetParent.right){//如果當前目標值是父節點的右孩子
                targetParent.right = target.right;//就把目標節點的右孩子接到父節點的右邊
            }
        }
    }

🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙
?原創不易，如有錯誤，歡迎評論區留言指出，感激不盡?
? 如果覺得內容不錯，給個三連不過分吧~ ?
? 看到會回訪~ ?
🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙