---
tags: 圖論
title: 基礎樹論
---

:::info
#### 本頁題目整理
1. [樹走訪 練習題](https://zerojudge.tw/ShowProblem?problemid=c463)
2. [BST 模板題](https://zerojudge.tw/ShowProblem?problemid=d526)
3. [Heap 模板題](https://zerojudge.tw/ShowProblem?problemid=a091)
4. [Heap Swap 練習題](https://www.luogu.com.cn/problem/T136291?contestId=38025)
5. [樹直徑 模板題](https://tioj.ck.tp.edu.tw/problems/1213)
:::

# 樹
*以下複雜度的$V$皆為樹的節點數量*
- 樹的名詞

- 樹的儲存：
- 鄰接矩陣(Adjacency matrix)
- 走訪時間：$O(V^2)$
- 空間：$O(V^2)$
- 鄰接串列(Adjacency list)
- 走訪時間：$O(V)$
- 空間：$O(V)$
- 樹走訪：大多使用DFS走訪
- [樹走訪 模板題](https://zerojudge.tw/ShowProblem?problemid=c463)

## 二元樹
- 就是每個母節點有兩個子節點的樹
- 複雜度常常跟$log_{(2)} N$有關

### 二元搜尋樹(BST)
- 左子節點 < 母節點 < 右子節點
- 常見操作：
- 插入
- 時間：$O(logV)$、$T(V)$
- 查詢某數存在與否
- 時間：$O(logV)$、$T(V)$
- 刪除
- 時間：$O(logV)$、$T(V)$
- 空間：$O(V)$
:::success
#### BST struct

struct Node{
    Data key;
    Node *left, *right;
    Node(Data _key) {
        left = right = nullptr;
        key = _key;
    }
};

:::
:::success
#### 插入

Node* insert(struct Node* node, int key) {
    if (node == NULL)
        return new Node(key);
    if (key < node->key)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);
    return node;
}

:::

:::success
### 刪除
- 刪除時我們分為幾種狀況來討論：
1. 刪除的點在樹葉(也就是沒有子樹)。
2. 刪除的點只有一個子樹。
3. 刪除的點有兩個子樹。

**1. 當刪除的點是樹葉時，我們直接刪除即可：**

if(node->leftNode == NULL && node->rightNode == NULL) {
    delete node;
    node = NULL;
}

**2. 當刪除的點只有一個子樹，我們將該子樹替換成自己：**

else if(node->leftNode == NULL) 
    node->rightNode = node;
else if(n->rightNode == NULL)
    node->leftNode = node;

**3. 當刪除的點有兩個子樹的情形最複雜，我們有兩種做法：**

- 將自己刪除後，找左子樹最大來替補自己：

else {
    Data leftMax = FindMax(node->leftNode);
    node->data = leftMax;
    Delete(node->leftNode, leftMax);
}

- 或是找右子樹最小替補：

else {
    Data rightMin = FindMin(node->rightNode);
    node->data = rightMin;
    Delete(node->rightNode, rightMin);
}

### 最後統整一下，整個刪除應為:

void Delete(Data d, Node* node) {
    if(node == NULL) return;
    
    if(node->data == d) {
        if(node->leftNode == NULL && node->rightNode == NULL) {
            delete node;
            node = NULL;
        }
        else if(node->leftNode == NULL) node->rightNode = node;
        else if(node->rightNode == NULL) node->leftNode = node;
        else
        {
            Data leftMax = FindMax(node->leftNode);
            node->data = leftMax;
            Delete(node->leftNode, leftMax);
        }
    }
    else if(node->data < d) Delete(d, node->leftNode);
    else Delete(d, node->rightNode);
}

:::

- [BST 模板題](https://zerojudge.tw/ShowProblem?problemid=d526)

### 堆(Heap)
- 左子節、右子節點 < 母節點
- 常見操作：
- 插入
- 時間：$O(logV)$
- 查詢最大/最小值
- 時間：$O(1)$
- 刪除
- 時間：$O(logV)$
- 空間：$O(V)$
- [Heap 模板題](https://zerojudge.tw/ShowProblem?problemid=a091)
- [Heap Swap 練習題](https://www.luogu.com.cn/problem/T136291?contestId=38025)

## 樹直徑
- 樹上最長鍊ㄅ
- 時間：$O(V)$
- 空間：$O(V)$
- [樹直徑 模板題](https://tioj.ck.tp.edu.tw/problems/1213)

:::info
#### 小提示：題目分類方法
1. 模板題：直接刻一次算法就好的題目，難度為算法本身自帶的難度
2. 練習題：帶上算法概念的題目，難度偏易
4. 變形題：如果不告訴你算法你不容易看出來的，難度中等
5. 挑戰題：需要綜合其他算法來思考題目，難度較高
6. 瘋癲題：如果前面題目都覺得太簡單，不妨試試這個，難度升天
:::