今天的程式碼內容有點龐大，感謝大家耐心觀看。

什麼樣的樹算是二元搜尋樹

二元搜尋樹（Binary Search Tree，簡稱BST）是一種用於儲存和組織數據的二元樹結構。
下是二元搜尋樹的特性，幫助你更好地理解它：

• 每個節點都包含一個值。
• 若任意節點的左子樹不為空，則左子樹上所有節點的值都小於它的父節點的值。
• 若任意節點的右子樹不為空，則右子樹上所有節點的值都大於它的父節點的值。
  因此任意節點的左、右子樹也都是二元搜尋樹。

二元搜尋樹的優點

BST具有以下優點：

1. 有序性：BST 中的節點依照中序遍歷的順序排列時，會得到一個有序的資料序列。這使得查找操作非常高效，可以在 O(log n) 的時間複雜度內完成，其中 n 是樹中節點的數量。
2. 快速插入和刪除：在 BST 中插入和刪除節點也是高效率的操作，通常也是在 O(log n) 的時間複雜度內完成。這使得 BST 在需要頻繁插入和刪除資料的場景中表現出色。

基本操作

接下來，我們將討論二元搜尋樹的基本操作：

插入

透過維護二元搜尋樹，新的節點總是插入到葉子中。我們開始從根開始搜尋，直到找到葉節點。一旦找到葉節點，新節點就會加入為葉節點的子節點。由於BST中的左子樹 < 中間節點 < 右子樹，插入操作遵循以下步驟：

1.我們從樹的根節點開始，檢查要插入的值與目前節點的值。

2.如果要插入的值小於目前節點的值，則繼續向左子樹移動，因為在BST中，左子樹的元素都比根節點的值小。

3.如果要插入的值大於目前節點的值，則繼續向右子樹移動，因為右子樹的元素都比根節點的值大。

4.重複上述動作，直到我們抵達葉節點，即沒有左子節點和右子節點的節點。

5.一旦抵達葉子節點，我們將新節點插入為該葉子節點的子節點，根據新節點的值與葉子節點的值的大小關係，將其設置為左子節點或右子節點。

它的時間複雜度通常為O(log n)，其中n是樹中節點的數量。

使用迴圈實作

void BST::insert(int key){
    Node *ptr = data;
    Node *newNode = new Node(key);
    if(ptr == nullptr){ // if tree is empty
        data = newNode;
        return;
    }
    Node *parent = nullptr;
    while(ptr != nullptr){
        parent = ptr;
        if(key < ptr->data)
            ptr = ptr->left;
        else if(key > ptr->data)
            ptr = ptr->right;
        else
            return;
    }
    if(key < parent->data)
        parent->left = newNode;
    else
        parent->right = newNode;
        
}

使用遞迴實作

Node * BST::insert_recursive(Node * root,int key){
    if (root == nullptr){
        Node *newNode = new Node(key);
        return newNode;
    }
    if(key < root->data)
        root -> left = insert_recursive(root->left,key);
    else if(key > root->data)
        root -> right = insert_recursive(root->right,key);
    return root;
}

搜尋

1.開始時，將欲搜尋的元素與樹的根元素進行比較。
2.如果目標元素小於根元素，則移至左子樹繼續搜尋，因為在BST中，左子樹的元素都比根元素小。
3.如果目標元素大於根元素，則移動到右子樹繼續搜尋，因為在BST中，右子樹的元素都比根元素大。
4.重複上述動作，直到找到與目標元素匹配的節點，或者在樹中沒有找到目標元素。
5.如果最終在樹中找不到目標元素，則回傳NULL。

這種搜尋方法利用了BST的特性，使得查找操作非常高效，時間複雜度通常為O(log n)，其中n是樹中節點的數量。

迴圈實作

Node* BST :: search(int key){
    Node *ptr = data;
    while(ptr != nullptr){
        if(key == ptr->data)
            return ptr;
        else if(key < ptr->data)
            ptr = ptr->left;
        else
            ptr = ptr->right;
    }
    return nullptr;
}

使用遞迴方式實作

Node* BST ::search_recursive(Node *root, int key){
    if(root == nullptr)
        return nullptr;
    if(key == root->data)
        return root;
    else if(key < root->data)
        return search_recursive(root->left,key);
    else
        return search_recursive(root->right,key);
} 

刪除

要從 BST 中刪除節點，可能會發生三種情況

• 刪除的節點是葉子節點： 這是最簡單的情況。如果要刪除的節點沒有任何子節點，那麼可以直接將其刪除，將其父節點中對應的子節點設為 null。

• 刪除的節點只有一個子節點： 當要刪除的節點只有一個子節點時，可以將其子節點取代目標節點，然後刪除目標節點。如果要刪除的節點是其父節點的左子節點，那麼將目標節點的子節點連接到其父節點的左子節點位置，否則連接到右子節點位置。

• 刪除的節點有兩個子節點： 這是較複雜的情況。要刪除具有兩個子節點的節點，需要找到一個替代節點來取代它。常用的方法是在右子樹中找到目標節點的中序後繼節點（或在左子樹中找到中序前驅節點），將中序後繼節點的值複製到目標節點，然後遞歸地刪除中序後繼節點。

刪除節點的操作可以透過遞迴或迭代方式實現，具體實現可能會略有不同

透過迭代來實現

Node* BST:: remove(int key){
    if(data == nullptr)
        return nullptr;
    Node *ptr = data;
    Node *parent = nullptr;
     // search for the key
    while(ptr != nullptr){
        if(key == ptr->data)
            break;
        else if(key < ptr->data){
            parent = ptr;
            ptr = ptr->left;
        }
        else{
            parent = ptr;
            ptr = ptr->right;
        }
    }
    if(ptr == nullptr) // key not found
        return nullptr;
    // case 1: node to be deleted is a leaf node
    if(ptr->left == nullptr && ptr->right == nullptr){
        if(parent->left == ptr)
            parent->left = nullptr;
        else
            parent->right = nullptr;
        delete ptr;
        return ptr;
    }
    // case 2: node to be deleted has one child
    if(ptr->left == nullptr || ptr->right == nullptr){
        Node *child = nullptr; // find the child
        if(ptr->left == nullptr)
            child = ptr->right;
        else
            child = ptr->left;

        if(parent->left == ptr)
            parent->left = child;
        else
            parent->right = child;
        delete ptr;
        return ptr;
    }
    // case 3: node to be deleted has two children 
    // find the inorder successor of the node in the right subtree
    if(ptr->left !=nullptr && ptr->right !=nullptr){
        Node *successor = ptr->right;
        Node *parent_successor = ptr;
        while(successor->left != nullptr){
            parent_successor = successor;
            successor = successor->left;
        }
        ptr->data = successor->data;
        if(parent_successor->left == successor)
            parent_successor->left = nullptr;
        else
            parent_successor->right = nullptr;
        delete successor;
        return successor;
    }
    return nullptr;
    
}

透過遞迴來實現

Node* BST:: remove_recursive(Node *root, int key){
    if(root == nullptr)
        return nullptr;
    // search for the key
    if(key < root->data)
        root->left = remove_recursive(root->left,key);
    else if(key > root->data)
        root->right = remove_recursive(root->right,key);
    else{
        // case 1: node to be deleted is a leaf node
        if(root->left == nullptr && root->right == nullptr){
            delete root;
            root = nullptr;
        }
        // case 2: node to be deleted has one child
        else if(root->left == nullptr || root->right == nullptr){
            Node *child = nullptr;
            if(root->left == nullptr)
                child = root->right;
            else
                child = root->left;
            delete root;
            root = child;
        }
        // case 3: node to be deleted has two children
        // find the inorder successor of the node in the right subtree 
        else{
            Node *successor = root->right;
            while(successor->left != nullptr)
                successor = successor->left;
            root->data = successor->data;
            root->right = remove_recursive(root->right,successor->data);
        }
    }
    return root;
}

遍歷

在二元樹的遍歷過程中，有三種常見的方式：

1.前序遍歷（Preorder Traversal）： 從根節點開始，先存取目前節點，然後依序遍歷左子樹和右子樹。前序遍歷的順序是根節點 -> 左子樹 -> 右子樹。

2.中序遍歷（Inorder Traversal）： 從根節點開始，先遍歷左子樹，然後訪問目前節點，最後遍歷右子樹。中序遍歷的順序是左子樹 -> 根節點 -> 右子樹。

3.後序遍歷（Postorder Traversal）： 從根節點開始，先遍歷左子樹，再遍歷右子樹，最後造訪目前節點。後序遍歷的順序是左子樹 -> 右子樹 -> 根節點。

我們可以使用不同的方法來實現，包括遞迴、使用堆疊（stack），以及 Morris Traversal。讓我們一一介紹並提供對應的程式碼。

遞迴(recursion)

遞歸是一種常見的樹遍歷方法，以下是每種遍歷方式的遞歸實作範例：

中序遍歷（Inorder Traversal）

void BST::inorder(Node *root){
    if(root == nullptr)
        return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

前序遍歷 (Preorder Traversal)

void BST::preorder(Node *root){
    if(root == nullptr)
        return;
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

後序遍歷 (Postorder Traversal)

void BST::postorder(Node *root){
    if(root == nullptr)
        return;
    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

堆疊(Stack)

使用堆疊資料結構，可以實現非遞歸的二元樹遍歷，以下是前序、中序和後序遍歷的非遞歸實作範例：

前序遍歷（Preorder Traversal）

方法說明: 將當前節點訪問後，將右子節點壓入堆疊，然後移動到左子節點，重複此過程直到堆疊為空。

void BST::preorder_iterative(){
    Node *ptr = data;
    stack<Node*> s;
    while(ptr != nullptr || !s.empty()){
        if(ptr != nullptr){
            cout << ptr->data << " ";
            s.push(ptr);
            ptr = ptr->left;
        }
        else{
            ptr = s.top();
            s.pop();
            ptr = ptr->right;
        }
    }
}

中序遍歷（Inorder Traversal）

方法說明: 盡可能移動到左子節點，途中的父節點壓入堆疊，當無左子節點後，取出堆疊中的父節點訪問，然後移動到其右子節點。

void BST::inorder_iterative(){
    Node *ptr = data;
    stack<Node*> s; // stack to store the nodes
    while(ptr != nullptr || !s.empty()){
        if(ptr != nullptr){
            s.push(ptr);
            ptr = ptr->left;
        }
        else{
            ptr = s.top();
            s.pop();
            cout << ptr->data << " ";
            ptr = ptr->right;
        }
    }
}

後序遍歷（Postorder Traversal）

方法說明: 使用兩個堆疊，將當前節點的右子節點壓入第一個堆疊，然後移動到左子節點。當左右子樹都處理完後，將節點值壓入第二個堆疊。最後，依次輸出第二個堆疊中的節點值即可。

void BST::postorder_iterative(){
    Node *ptr = data;
    stack<Node*> s;
    while(ptr != nullptr || !s.empty()){
        if(ptr != nullptr){
            s.push(ptr);
            ptr = ptr->left;
        }
        else{
            ptr = s.top();
            s.pop();
            cout << ptr->data << " ";
            ptr = ptr->right;
        }
    }
}

Morris Traversal

中序遍歷（Inorder Traversal）

方法說明: 當當前節點的左子樹為空時，訪問當前節點，然後將當前節點設為其右子節點；若左子樹不為空，則找到中序前驅節點，建立線索，然後遍歷左子樹。

 // Morris Traversal for inorder traversal
void BST:: inorder_morris(){
    Node *ptr = data;
    while(ptr != nullptr){
        if(ptr->left == nullptr){
            cout << ptr->data << " ";
            ptr = ptr->right;
        }
        else{
            Node *predecessor = ptr->left;
            // find the inorder predecessor of ptr
            while(predecessor->right != nullptr && predecessor->right != ptr)
                predecessor = predecessor->right;
            if(predecessor->right == nullptr){
                predecessor->right = ptr;
                ptr = ptr->left;
            }
            else{
                predecessor->right = nullptr;
                cout << ptr->data << " ";
                ptr = ptr->right;
            }
        }
    }
}

前序遍歷 (Preorder Traversal)

方法說明: 若當前節點的左孩子為空，則訪問當前節點並移動到其右孩子；若左孩子不為空，則找到中序前驅節點，建立線索，然後輸出當前節點，最後移動到左孩子。

void BST::preorder_morris(){
    Node *ptr = data;
    while(ptr != nullptr){
        if(ptr->left == nullptr){
            cout << ptr->data << " ";
            ptr = ptr->right;
        }
        else{
            Node *predecessor = ptr->left;
            // find the inorder predecessor of ptr
            while(predecessor->right != nullptr && predecessor->right != ptr)
                predecessor = predecessor->right;
            if(predecessor->right == nullptr){
                predecessor->right = ptr;
                cout << ptr->data << " ";
                ptr = ptr->left;
            }
            else{
                predecessor->right = nullptr;
                ptr = ptr->right;
            }
        }
    }
}

後序遍歷 (Postorder Traversal)

方法說明: 在後序遍歷的 Morris Traversal 中，我們使用了兩個指針，一個用於正常遍歷，另一個用於反轉左子樹的節點。我們首先將根節點的左子樹反轉，然後遍歷反轉後的左子樹，接著再次反轉左子樹，使其恢復原狀。整個過程中，我們需要使用兩個堆疊來實現。

void BST::postorder_morris(){
    Node *dummy = new Node();
    dummy->left = data;
    Node *ptr = dummy;
    while(ptr != nullptr){
        if(ptr->left == nullptr){
            ptr = ptr->right;
        }
        else{
            Node *predecessor = ptr->left;
            // find the inorder predecessor of ptr
            while(predecessor->right != nullptr && predecessor->right != ptr)
                predecessor = predecessor->right;
            if(predecessor->right == nullptr){
                predecessor->right = ptr;
                ptr = ptr->left;
            }
            else{
                predecessor->right = nullptr;
                Node *temp = ptr->left;
                Node *prev = nullptr;
                Node *curr = temp;
                Node *next = nullptr;
                while(curr != nullptr){
                    next = curr->right;
                    curr->right = prev;
                    prev = curr;
                    curr = next;
                }
                while(prev != nullptr){
                    cout << prev->data << " ";
                    prev = prev->right;
                }
                ptr = ptr->right;
            }
        }
    }
}

層序遍歷

它按照層級的順序進行遍歷，從上到下，從左到右訪問每個節點。通常使用佇列（queue）數據結構來實現這種遍歷方式。

使用佇列資料結構的層序遍歷的非遞迴實作

void BST::levelorder(Node *root){
    if(empty(root))
        return;
    queue<Node*> q;
    q.push(root);
    while(!q.empty()){
        Node *ptr = q.front();
        q.pop();
        cout << ptr->data << " ";
        if(ptr->left != nullptr)
            q.push(ptr->left);
        if(ptr->right != nullptr)
            q.push(ptr->right);
    }
}

最低共同祖先(Least Common Ancestor)

最低共同祖先是指這兩個節點的最深的共同祖先節點。

程式碼

Node* BST::LCA(Node *root, int key1, int key2){
    if(empty(root))
        return nullptr;
    if(key1 < root->data && key2 < root->data)
        return LCA(root->left,key1,key2);
    else if(key1 > root->data && key2 > root->data)
        return LCA(root->right,key1,key2);
    else
        return root;
}

最短路徑(Distance)

兩個節點之間最短路徑的邊數
1.找到兩個節點的最近共同祖先（Lowest Common Ancestor, LCA）。
2.計算從第一個節點到 LCA 節點的距離（邊數）。
3.計算從第二個節點到 LCA 節點的距離（邊數）。
4.將步驟 2 和步驟 3 的距離相加，即為最短路徑的邊數。

程式碼

int BST::distance(Node *root, int key1, int key2){
    if(empty(root))
        return 0;
    Node *lca = LCA(root,key1,key2);
    int dist1 = depth(lca);
    int dist2 = depth(lca);
    return dist1 + dist2;
}

不要怕徒勞，因為即使努力的過程中看似一無所獲，每一次的嘗試和付出都是一次寶貴的經驗。