什麼是二元樹(Binary Tree)

二元樹(Binary Tree)是一種常見的資料結構，被廣泛應用於電腦科學和程式設計領域。它由節點(node)組成，每個節點最多有兩個子節點，通常稱為左子節點和右子節點。這種樹狀結構具有許多重要的特性，使其成為解決各種問題的強大工具。

結構

首先，讓我們來看一個C++的程式碼示例，展示了二元樹的基本結構：

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
};

上述程式碼中，我們定義了一個二元樹節點結構 TreeNode，每個節點包含一個整數值、左子節點和右子節點的指針。

舉例

         10
        /  \
       5    15
      / \     \
     3   7    20

我們首先定義了一個二元樹節點結構 TreeNode ，每個節點都包含一個整數值、左子節點和右子節點。然後，我們使用這個結構創建了一個簡單的二元樹，並執行了中序遍歷來列印節點的值。

在上面的範例中，我們有一個二元樹，根節點的值是10。它有兩個子節點，左子節點的值是5，右子節點的值是15。再細分下去，左子節點有兩個子節點，值分別為3和7，而右子節點只有一個子節點，值為20。

基本操作

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

插入

當我們要在二元樹中插入一個新的值（例如12），我們從根節點開始進行比較。如果12小於當前節點的值，我們向左子樹移動，否則我們向右子樹移動，直到找到一個空的位置，然後將12插入該位置，以保持二元樹的有序性。

TreeNode* insert(TreeNode* root, int value) {
    if (root == nullptr) {
        return new TreeNode(value);
    }
    
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    
    return root;
}

尋找

當我們要查找特定值（例如7）時，我們從根節點開始進行比較。如果目標值等於當前節點的值，則找到了該節點；否則，我們根據比較的結果向左子樹或右子樹移動，繼續查找，直到找到目標值或確定目標值不存在。

TreeNode* search(TreeNode* root, int value) {
    if (root == nullptr || root->data == value) {
        return root;
    }
    
    if (value < root->data) {
        return search(root->left, value);
    } else {
        return search(root->right, value);
    }
}

刪除

假設我們要刪除值15。首先，我們找到要刪除的節點。然後，有幾種情況：

1. 如果該節點是葉子節點（沒有子節點），我們可以直接刪除它。
2. 如果該節點有一個子節點，我們可以用其子節點取代它。
3. 如果該節點有兩個子節點，我們可以選擇用其右子樹中最小的節點值來取代它，或用左子樹中最大的節點值來取代它。在這種情況下，我們需要遞歸地刪除對應的子節點。

TreeNode* deleteNode(TreeNode* root, int value) {
    if (root == nullptr) {
        return root;
    }
    
    if (value < root->data) {
        root->left = deleteNode(root->left, value);
    } else if (value > root->data) {
        root->right = deleteNode(root->right, value);
    } else {
        if (root->left == nullptr) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }
        
        TreeNode* temp = root->right;
        while (temp->left != nullptr) {
            temp = temp->left;
        }
        
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    
    return root;
}

遍历

接下來，我們將介紹二元樹的遍歷操作，這些操作可用於按照不同的順序訪問樹中的節點，常見的包括前序遍歷、中序遍歷和後序遍歷。

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

void preorderTraversal(TreeNode* root) {
    if (root) {
        std::cout << root->data << " ";
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

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

void inorderTraversal(TreeNode* root) {
    if (root) {
        inorderTraversal(root->left);
        std::cout << root->data << " ";
        inorderTraversal(root->right);
    }
} 

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

void postorderTraversal(TreeNode* root) {
    if (root) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        std::cout << root->data << " ";
    }
}

特性

二元樹的一個重要特性是其高效率的尋找和插入操作。由於二元樹的結構，找出特定值的時間複雜度為O(log n)，其中n是節點的數量。這使得它成為資料庫索引和搜尋演算法的理想選擇。

• 高效率的尋找: 這是因為在每一個節點處，我們只需要比較要查找的值與該節點的值，然後根據比較結果選擇向左子樹或右子樹移動，從而迅速縮小搜索範圍。這種分而治之的策略使得查找操作的效率非常高。
• 高效插入：首先，我們可以使用查找操作找到要插入的位置。然後，只需將新節點插入到樹的合適位置，並調整相關節點的引用。由於查找操作的效率高，所以插入操作的時間複雜度也是O(log n)。

總結來說，二元樹是一個優秀的資料結構，它具有高效的尋找和插入操作，使其成為計算機科學和軟體開發中的重要工具。其能夠在O(log n)的時間內快速查找和插入節點，這是由其結構和二分搜尋的原理所支持的。此外，二元樹的動態性質使其適用於需要頻繁更新數據的應用，並且可以用於實現排序和檢索操作。

然而，需要注意的是，二元樹的性能在最壞情況下可能不如某些其他資料結構，因此在特定情境中，可能需要考慮使用其他資料結構以優化操作。在實際應用中，選擇適當的資料結構取決於問題的特性和需求。

不要害怕去做選擇，也不要擔心選錯，因為與其因此糾結不知道要選擇甚麼，不如勇敢地決定並學會從每個選擇中成長。每一個選擇都是一個機會，它們可以幫助我們了解自己。