# 樹的概念與儲存方式

樹（Tree）是一種非線性的資料結構，主要用以表達擁有不同層級和所屬關係的資料。
例如電腦的檔案系統，磁碟分割區、資料夾和檔案的關係就是一種樹狀的結構；
家族的族譜、組織的上下關係圖、技能樹或天賦樹等，在生活中其實相當常見。
~~或者延長線也能接成一棵 tree~~ ← 有過載的可能，很危險請不要真的這麼做


例：《仙境傳說 Ragnarok Online》巫師技能樹


例：Sega 組織改組前後對照

講義也有不少例子帶有樹的概念，例如 [運算式](https://hackmd.io/BbRsMnLrQFuCeLifVxecJA#%E9%81%8B%E7%AE%97%E5%BC%8F%E6%B1%82%E8%A7%A3) 或者 [DFS 過程](https://hackmd.io/kPw0F65-SG6RD0BjXlSSdg#DFS-%E7%9A%84%E5%9F%BA%E6%9C%AC%E5%8E%9F%E7%90%86)。

## 樹的節點與關係 Node and Relationship

Tree 由節點（Node）以及節點間的關係所構成。
以根節點（Root）為最頂層（第 $0$ 層）開始，隷屬於根節點的為第 $1$ 層，
隷屬於第 $1$ 層節點者為第 $2$ 層，依此類推。
底下沒有任何隷屬節點者，被稱為葉節點（Leaf）；所在的層數稱為深度（height/depth/level）。

繪製成圖時，通常習慣以 Root 在上，Leaf 在下，和植物上的樹正好相反。


其中節點間有直接的從屬關係的節點，會以邊（edge）相連。

依其上下關係，在上稱為父節點（Parent），在下稱為子節點（Child）。
一個節點只被允許擁有至多 $1$ 個父節點，但可以擁有 $0$ 至多個子節點。
一棵 Tree 中，只有 Root 沒有父節點。


以上圖為例，我們稱 $A$ 為 $B$、$C$、$D$ 的 Parent；
稱 $B$、$C$、$D$ 為 $A$ 的 Child。

擁有相同 Parent 的節點們，互為兄弟節點（Sibling），例如上圖的 $B$、$C$、$D$ 互為 Sibling。

父節點再往上的直系父節點們，則稱為祖先（Ancestor）。

## 樹的一些特性

:::info
一棵 $N$ 個節點的樹，會有剛好 $N-1$ 條邊。
:::

考慮每對父子關係會提供一條邊，而 Root 沒有父節點，Root 以外必有恰 $1$ 個父節點，共 $N-1$ 條邊。

:::info
一棵樹上所有節點之間，只會有一種簡單路徑。
:::

簡單路徑是指不重覆走到相同節點的路徑，在此限制下任兩節點之間只存在唯一一種走法。

:::info
以任何節點為 Root 則它和它所有子孫也會形成一棵樹。
:::

這棵樹稱為原樹的子樹（Subtree），這使得樹狀結構具有很漂亮的遞迴特性。

## 二元樹 Binary Tree

二元樹是一種特殊的樹，每個節點只能擁有 $0$ 到 $2$ 個子節點，而且**左、右**子節點是**有分別**的。

也就是說，同樣只擁有 $1$ 個子節點時，擁有左子節點和擁有右子節點被看成是不同的情況。

二元樹在資料結構上有著相當廣泛的應用，基於二分的概念，可以讓許多操作達到僅需 $O(\log n)$ 的時間複雜度。

### 任意樹轉二元樹

任意的樹都可透過 Left-child, Right-sibling 的方式轉成二元樹。
將所有節點改成左子節點為原先的第一個子節點、右子節點為相鄰 sibling 即可。


例：透過 Left-child, Right-sibling 轉為 binary tree 的例子，
以綠色箭頭表示左子節點，藍色箭頭表示右子節點。

## 實作 Implementation

:::info
樹的實作相當程度仰賴於遞迴與鏈結串列的概念，若不熟悉建議先複習一下。
:::

每個節點需要的資訊大致如下：

- 節點上需要保存的資料
- 子節點有哪些
- 父節點是誰

:::warning
通常大多時候會需要從根節點拜訪其他節點，因此父節點通常不重要。
:::

將所有節點存到一維陣列中的話，就能透過陣列的索引來存取特定節點，因此可用 int 儲存彼此的關係。

struct node
{
    int data;
    // 如果要換成二元樹，只需將下一行改為
    // int left, right;
    vector<int> children;
    // 如果只須往下走，大部份時候是不需要記父節點，可視情況省略
    int parent;
};

拜訪時，由於樹的遞迴性質，常會使用 DFS 的方式走訪每一個節點。

:::success
### 樹的建立

輸入正整數 $n$ 代表此樹有多少節點，下一行有 $n$ 個整數，
代表節點上所儲存的資料，接下來 $n-1$ 行每行有兩個整數 $a$、$b$，
代表 $a$ 為 $b$ 的父節點。可以放心假設樹是合法的。

#### 範例輸入

12
1 1 2 3 5 8 13 21 34 55 89 144
8 11
5 10
5 9
3 8
3 7
1 6
1 5
1 4
0 3
0 2
0 1

#### 範例輸出

========
Node 0 (depth: 0):
Parent: -1
Children(3):
   3 2 1
========
Node 3 (depth: 1):
Parent: 0
Children(2):
   8 7
========
Node 8 (depth: 2):
Parent: 3
Children(1):
   11
========
Node 11 (depth: 3):
Parent: 8
Children(0):

========
Node 7 (depth: 2):
Parent: 3
Children(0):

========
Node 2 (depth: 1):
Parent: 0
Children(0):

========
Node 1 (depth: 1):
Parent: 0
Children(3):
   6 5 4
========
Node 6 (depth: 2):
Parent: 1
Children(0):

========
Node 5 (depth: 2):
Parent: 1
Children(2):
   10 9
========
Node 10 (depth: 3):
Parent: 5
Children(0):

========
Node 9 (depth: 3):
Parent: 5
Children(0):

========
Node 4 (depth: 2):
Parent: 1
Children(0):

#### 範例圖解

:::

:::spoiler 參考實作

#include <iostream>
#include <vector>
using namespace std;

const int NOT_EXIST = -1;

struct node
{
    int data;
    vector<int> children;
    int parent;
};

node tree[1048576];

void print(int cur, int depth)
{
    int i;
    cout << "========\n";
    cout << "Node " << cur << " (depth: " << depth << "):\n";
    cout << "Data: " << tree[cur].data << "\n";
    cout << "Parent: " << tree[cur].parent << "\n";
    cout << "Children(" << tree[cur].children.size() << "):\n";
    cout << "  ";
    for (i=0; i<tree[cur].children.size(); i++)
    {
        cout << " " << tree[cur].children[i];
    }
    cout << "\n";
}

void travel(int cur, int depth)
{
    int i;
    print(cur, depth);
    for (i=0; i<tree[cur].children.size(); i++)
    {
        travel(tree[cur].children[i], depth+1);
    }
}

int main()
{
    int n, i, a, b;
    while (cin >> n)
    {
        // 輸入 n 個節點的資料，並初始化子節點、父節點的部份
        for (i=0; i<n; i++)
        {
            cin >> tree[i].data;
            tree[i].children.clear();
            tree[i].parent = NOT_EXIST;
        }
        // 輸入關係建立起樹狀架構
        for (i=1; i<n; i++)
        {
            cin >> a >> b;
            tree[a].children.emplace_back(b);
            tree[b].parent = a;
        }
        // 找到 root
        for (i=0; i<n; i++)
        {
            if (tree[i].parent == NOT_EXIST)
            {
                travel(i, 0);
                break;
            }
        }
    }
    return 0;
}

:::

## 歡樂練習時間

:::success
### Kattis electricaloutlets - Electrical Outlets
https://open.kattis.com/problems/electricaloutlets
:::

:::success
### Kattis kitten - Kitten on a Tree
https://open.kattis.com/problems/kitten
:::

:::success
### UVa 112 - Tree Summing
http://domen111.github.io/UVa-Easy-Viewer/?112
:::

:::success
### UVa 115 - Climbing Trees
http://domen111.github.io/UVa-Easy-Viewer/?115
:::

:::success
### UVa 679 - Dropping Balls
http://domen111.github.io/UVa-Easy-Viewer/?679
:::

:::success
### UVa 10493 - Cats, with or without Hats
http://domen111.github.io/UVa-Easy-Viewer/?10493
:::

:::success
### ZJ c463 - apcs 樹狀圖分析 (Tree Analyses)
https://zerojudge.tw/ShowProblem?problemid=c463

2017/10 APCS p3

:::

:::success
### ZJ h029 - 202001_4 貨物分配
https://zerojudge.tw/ShowProblem?problemid=h029

2020/01 APCS p4

:::

{%hackmd @sa072686/__style %}

###### tags: `競程：三章`, `競程`