新增節點的方式大概可以以兩種方式來概括：

• 非遞迴形式：void BST::insert(int);
  • 相對直觀
  • 使用 while 迴圈
• 遞迴形式：void BST::insert(BSTNode *, int);
  • 子樹的概念

那要怎麼新增節點呢？

先想想二元搜尋樹有什麼特色！
針對每個節點，右子節點的值 > 其值 > 左子節點的值

給你一個 _data, BSTNode root，我們怎麼新增節點到樹上？

if (_data > root.data) 
    insert at root.right
    
if (_data < root.data)
    insert at root.left

定義類別 BST

class BST {
private:
    BSTNode *root;
private:
    BST();
    void insert(int); // Non Recursive
    void insert(BSTNode *, int); // Recursive
};

非遞迴形式

void BST::insert(int _data)

要被新增到樹的資料：int _data

兩種 Case 討論：

1. 樹的 根節點指標 指向 NULL ( 樹為空的 )

if (this -> root == NULL)
{
    this -> root = new BSTNode(_data);
    return ;
}

• 要記得我們現在在寫的是 class BST 的函式，這個 this -> root 代表這棵樹的 根節點
• this -> root == NULL 代表根節點沒有指向任何記憶體（前緣）
• 雖然這是個 void function，不需要回傳值，但是其實我們已經做完所有事情，所以直接終止函式 return ;

2. 樹已經包含至少一個節點

• 先宣告一個代表現在位置的指標變數 BSTNode *cur = this -> root;
• 進入 while loop ，終止條件還不確定，就先給他 true ，讓他變無窮迴圈，我們只要適當條件 break 迴圈就好
• 比較 cur -> data 跟 _data 的大小，決定接下來的路徑 cur = cur -> left 或 cur = cur -> right
• 假設我們接下來要走向 左邊 ，但是cur -> left == NULL，我們將 cur -> left 設為新節點

BSTNode *cur = this -> root;
while (true)
{
    if (cur -> data > _data) // _data <- root -> ~
    {
        if (cur -> left == NULL)
        {
            cur -> left = new BSTNode(_data); // 將 cur -> left 指向新節點
            return ; // 不只終止無窮迴圈，也終止函式
        }
        else
            cur = cur -> left;
    }
    else // ~ <- root -> _data
    {
        if (cur -> right == NULL)
        {
            cur -> right = new BSTNode(_data); // 將 cur -> right 指向新節點
            return ; // 不只終止無窮迴圈，也終止函式
        }
        else
            cur = cur -> right;
    }
}

腦筋急轉彎

以下函式有什麼問題 :

BSTNode *cur = this -> root;
while (true)
{
    if (cur -> data > _data) 
        cur = cur -> left;
    else
        cur = cur -> right;
    if (cur == NULL)
        cur = new BSTNode(_data);
}

這樣不是看起來更簡潔嗎？邏輯「似乎 && 好像」也對 !
『大錯特錯 ！！』

line 8：當 cur 沒有指向記憶體，我們給他一塊記憶體，這個觀念是對的

BUT
這塊記憶體其實沒有與樹上的指標相連接
假設理想中他的父節點叫 par ，
使得 par -> right / left == cur = newBSTNode，
這樣新節點才有跟父節點相連

要怎麼知道父節點有幫你當子節點？（偷吃步檢驗法）
類別屬性中唯二能連結其他的節點者為 right, left
在這個程式碼完全沒有這兩個屬性被使用的痕跡，故得證＃

非遞迴形式 程式碼

void BST::insert(int _data)
{
    if (this -> root == NULL)
    {
        this -> root = new BSTNode(_data);
        return;
    }
    else
    {
        BSTNode *cur = this -> root;
        while (true)
        {
            if (cur -> data > _data) // _data <- root -> ~
            {
                if (cur -> left == NULL)
                {
                    cur -> left = new BSTNode(_data);
                    return;
                }
                else
                    cur = cur -> left;
            }
            else // ~ <- root -> _data
            {
                if (cur -> right == NULL)
                {
                    cur -> right = new BSTNode(_data);
                    return;
                }
                else
                    cur = cur -> right;
            }
        }
    }
}

遞迴形式

void BST::insert(BSTNode *_root, int _data)

要被新增到樹的資料：int _data
根節點（可能是樹或子樹的）：BSTNode *_root

兩種 Case 討論：

1. 樹的 根節點指標 指向 NULL ( 樹為空的 )

if (this -> root == NULL)
{
    this -> root = new BSTNode(_data);
    return ;
}

2. 樹已經包含至少一個節點

• 把 BSTNode *_root 改成子樹的根節點（cur -> right 或 cur -> left）
• 想像我們把迴圈作法的 cur 改成子樹的根節點
• 其餘部分其實差不多，甚至一模一樣

if (_data > _root -> data) // root -> _data
{
    if (_root -> right != NULL)
        insert(_root -> right, _data);
    else
    {
        BSTNode *newBSTNode = new BSTNode(_data);
        _root -> right = (newBSTNode); 
        return;
    }
}
else // _data <- root
{
    if (_root -> left != NULL)
        insert(_root -> left, _data);
    else
    {
        BSTNode *newBSTNode = new BSTNode(_data);
        _root -> left = (newBSTNode); 
        return;
    }
}

遞迴形式 程式碼

void BST::insert(BSTNode **_root, int _data)
{
    if (this -> root == NULL)
    {
        this -> root = new BSTNode(_data);
        return;
    }

    if (_data > _root -> data) // root -> _data
    {
        if (_root -> right != NULL)
            insert(_root -> right, _data);
        else
        {
            BSTNode *newBSTNode = new BSTNode(_data);
            _root -> right = (newBSTNode); 
            return;
        }
    }
    else // _data <- root
    {
        if (_root -> left != NULL)
            insert(_root -> left, _data);
        else
        {
            BSTNode *newBSTNode = new BSTNode(_data);
            _root -> left = (newBSTNode); 
            return;
        }
    }
}

新增節點算是類別方法中簡單的部分，但是有些觀念還是需要釐清，否則會得到錯誤。

下一篇，我們來介紹如何輸出樹的內容。