Day 13｜從家族系譜認識樹與表示法

家族系譜常用一層一層分支的圖，表示世代之間的關係。資料結構中的**樹（tree）**也用這種方式呈現資料：從一個起點往下分出不同節點。樹適合表示階層關係，是一種非線性資料結構。

以下用 A 作為起點，稍微畫一個英文字母的家族示意圖；A 是這棵樹的根節點：

在這張圖裡，B、C、D 是 A 的子節點；E、F 是 B 的子節點，G 是 C 的子節點，H 是 D 的子節點。字母代表家族中的不同成員，分支則表示上一代與下一代的關係。

樹是由根節點和子樹組成

樹有一個特殊的起點，稱為根節點（root）。把根節點拿開後，其餘節點可以分成零個或多個互不重疊的部分；每一部分本身仍是一棵樹，稱為根節點的子樹（subtree）。

例如，根節點 A 有三棵子樹，根分別是 B、C、D：

       A
     / | \
    B  C  D

每個節點都可以有零個或多個子節點，因此一般的樹不限定每個節點只能有兩個子節點。根節點以外的節點各有一個直接的父節點；而從根節點沿著分支往下，就能找到樹中的其他節點。

用一棵樹理解常見名詞

我們在這裡放一棵簡單的樹，來理解一些常見的名詞。

**森林（forest）**是由零棵或多棵互不相連的樹組成，有些書也簡稱為「林」。把上圖根節點 A 移除後，B、C、D 各自成為一棵樹的根，合起來就是由三棵樹構成的森林。

一般樹如何存進記憶體？

圖可以畫出節點和分支，但程式還需要知道每個節點的連結位置。最直接的做法，是在每個節點準備多個連結欄位，分別指向它的子節點。假設樹中最大的節點分支度是 k，每個節點就要預留 k 個欄位；沒有子節點可連的欄位只能放 NULL。若多數節點的子節點少於 k，就會留下不少未使用的欄位。

以上一節 A 到 M 的樹為例，A 和 D 都有三個子節點，因此 k = 3。13 個節點各預留 3 個欄位，一共 39 個欄位；但除了根節點，每個節點只會被父節點連到一次，所以真正用到的只有 12 個，其餘 27 個都是 NULL。一般來說，n 個節點的樹共有 n × k 個欄位，只用到 n - 1 個。

另一種做法是左子右兄弟表示法（Leftmost-Child-Next-Right-Sibling）。每個節點只需要兩個連結：

• 左子：指向最左邊的子節點，也就是第一個子節點。
• 右兄弟：指向右邊緊鄰的兄弟節點，也就是下一個兄弟。

用 A 有三個子節點 B、C、D，而 C 有一個子節點 E 的小樹為例：

兩個連結欄位會記錄成：

A 的第一個子節點是 B，所以 A 的左子連結指向 B。B、C、D 是兄弟，於是 B 的右兄弟連結指向 C，C 再指向 D。C 的第一個子節點是 E，因此 C 的左子連結指向 E。若沒有子節點或下一個兄弟，對應欄位就放 NULL。

以 C 語言表示節點時，可以用以下結構保存資料和兩個連結欄位：

typedef struct TreeNode {
    char data;
    struct TreeNode *leftChild;
    struct TreeNode *rightSibling;
} TreeNode;

這是節點型態的片段，用來示範欄位配置，不是完整程式。leftChild 指向第一個子節點，rightSibling 指向下一個兄弟節點；兩個指標都可以是 NULL。雖然這種連結方式能畫成二元樹的形狀，但 rightSibling 表示的是「下一個兄弟」，不代表原本的一般樹裡有一個右子節點。這個差別能避免把表示方式誤當成原本的親子關係。

左子右兄弟表示法不必限制一個節點能有幾個子節點，並且每個節點固定只需要兩個連結欄位，因此也能表示不同分支度的一般樹。

小結

樹用一個根節點和零個或多個子樹表示層級關係。理解父子、兄弟、祖先、葉節點、分支度、層次和高度等名詞後，就能讀懂樹圖；而左子右兄弟表示法則用「第一個子節點」和「下一個兄弟」兩個連結欄位，把一般樹的關係存進記憶體。

今日重點：

• 一棵樹只有一個根節點；根節點下方可以有零個或多個互不重疊的子樹。
• 節點的分支度是直接子節點數；樹的分支度是全樹最大的節點分支度。
• 本書從根節點第 1 層開始計算，樹的高度是最大層次。
• 移除樹根後，根原本的各棵子樹會形成一座森林。
• 左子右兄弟表示法用兩個連結欄位表示第一個子節點和下一個兄弟；右兄弟連結不代表原樹中的右子節點。

下一篇將進入二元樹的世界，瞭解二元樹的特性和怎麼建立二元樹。