資料結構中的樹狀結構（Tree）：深入解析與應用指南

資料結構

資料結構：樹狀結構

樹狀結構（Tree）是資料結構中一種極為重要且常見的非線性資料結構。它由節點（Node）組成，呈現出層級關係，每個節點可擁有多個子節點。樹狀結構廣泛應用於檔案系統、搜尋演算法、資料庫索引及人工智慧領域。

一、樹狀結構的定義

樹狀結構是一種由節點組成的階層式資料結構，具有以下特性：

  1. 有一個根節點（Root），作為樹的起點。
  2. 每個節點可以有零個或多個子節點。
  3. 除了根節點外，每個節點都有唯一的父節點（Parent）。
  4. 節點之間存在由邊（Edge）連接的關係。
  5. 沒有環狀結構，即不存在回到先前節點的路徑。

二、樹的基本術語

術語說明
根節點樹的起始節點，沒有父節點。
子節點某個節點所直接連接的下一層節點。
父節點直接連接到當前節點上一層的節點。
葉節點沒有子節點的節點，位於樹的最底層。
深度根節點到某個節點的邊數。
高度某個節點到其子樹最深葉節點的邊數。
子樹某個節點及其所有後代節點構成的樹。

三、樹的種類

1. 普通樹（General Tree）

每個節點可以有任意數量的子節點。

2. 二元樹（Binary Tree）

每個節點最多只能有兩個子節點，分別為左子節點與右子節點。

3. 完全二元樹（Complete Binary Tree）

除了最後一層節點外，其他層都被填滿，且最後一層的節點從左到右緊密排列。

4. 滿二元樹（Full Binary Tree）

每個節點要麼沒有子節點，要麼有兩個子節點。

5. 二元搜尋樹（Binary Search Tree, BST）

對於每個節點，其左子樹的所有節點值小於該節點值，右子樹的所有節點值大於該節點值。

6. 平衡二元樹（Balanced Binary Tree）

任意節點的左右子樹高度差不超過1，例如 AVL 樹、紅黑樹等。

四、樹的基本操作

1. 建立樹

初始化樹，建立根節點。

2. 插入節點

根據規則新增子節點，例如：二元搜尋樹依大小插入。

3. 刪除節點

移除指定節點並調整子節點位置。

4. 遍歷樹

遍歷樹上所有節點，包括以下三種方式：

  • 先序遍歷（Preorder）：根 -> 左子樹 -> 右子樹
  • 中序遍歷（Inorder）：左子樹 -> 根 -> 右子樹
  • 後序遍歷（Postorder）：左子樹 -> 右子樹 -> 根
5. 搜尋節點

根據條件找到指定節點，例如：在二元搜尋樹中快速找到某個值。

五、樹的程式碼範例

以下為 C++ 二元樹的基本範例：

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

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

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    preorder(root); // 輸出: 1 2 4 5 3
    return 0;
}

六、樹的時間與空間複雜度

操作平均時間複雜度最壞時間複雜度
插入O(log n)O(n)
刪除O(log n)O(n)
搜尋O(log n)O(n)

n 表示樹中節點數量。平衡樹的情況下可保證 O(log n) 時間複雜度。

七、樹的應用場景

  1. 檔案系統：檔案與資料夾的層級結構。
  2. 資料庫索引：B 樹、B+ 樹用於快速檢索。
  3. 網頁 DOM 樹：HTML 文件的階層結構。
  4. 搜尋演算法：最佳路徑搜尋（如 A* 演算法）。
  5. 編譯器語法樹：解析語法並生成程式碼。

八、樹的優缺點

優點：
  • 高效搜尋與插入操作。
  • 適用於具有層級關係的資料表示。
缺點：
  • 若不平衡，搜尋與插入效率下降。
  • 記憶體額外消耗：指標需額外存儲空間。

九、最佳實踐

  1. 優先使用平衡二元樹，如 AVL 樹或紅黑樹，以保證性能。
  2. 若需大量篩選和搜尋，考慮使用二元搜尋樹。
  3. 在程式語言中，STL 提供的 set、map 等容器底層常以紅黑樹實作。

十、結論

樹狀結構是處理分層資料、快速檢索和高效插入的理想選擇。掌握不同樹的種類、特性與操作，能幫助開發者根據需求選擇最佳資料結構，提升程式設計的靈活性與效能。

Related Posts

發佈留言