🌳 樹狀結構（Tree）

什麼是樹？

樹是一種很特別的圖。樹的定義是：任兩點之間都相通，而且沒有「環」的圖。 「環」是指繞圈子的循環路線。此外，樹的邊數永遠等於節點數 − 1。

樹狀結構術語

下面這張樹會作為術語解釋的範例。節點 1 是這棵樹的根（已強調）。

節點 (Node)

樹上的每一個點都是節點。圖中共有 7 個節點。

邊 / 枝 (Edge / Branch)

連接兩個節點的線。樹的邊數 = 節點數 − 1，圖中有 6 條邊。

根 (Root)

整棵樹的起點。本圖以節點 1 為根（任一節點都可以作為根）。

葉 / 外部節點 (Leaf)

沒有子節點的節點。圖中 4、5、6、7 都是葉。

父親 / 小孩 (Parent / Child)

相鄰兩點中靠近根者為父親，靠近葉者為小孩。節點 2 是 4、5 的父親。

祖先 / 後代 (Ancestor / Descendant)

父親的父親…皆為祖先；小孩的小孩…皆為後代。1 是 4 的祖先，4 是 1 的後代。

手足 (Sibling)

共享同一個父親的節點。4 與 5 是手足；2 與 3 也是。

分支度 (Degree)

一個節點的小孩數量。節點 1 的 degree = 2。

層級 (Level)

節點離根的距離。根通常是 level 0，其子節點是 level 1，以此類推。

高度 / 深度 (Height / Depth)

整棵樹上最大的層級。本圖的高度 = 2。

二元樹 (Binary Tree)

二元樹中，每個節點最多只有兩個子節點，分別稱為左子樹（left subtree）與右子樹（right subtree）。 依節點分佈可分為三種特殊形態：

樹的遍歷 (Tree Traversal)

遍歷是指「走訪樹上每一個節點」的過程。根據「根節點何時被處理」，可以分為四種方式：

• 前序 (Preorder)：Root → Left → Right
• 中序 (Inorder)：Left → Root → Right
• 後序 (Postorder)：Left → Right → Root
• 層序 (Level Order)：一層一層走完（BFS）

下方動畫可以切換四種遍歷方式，點選播放看節點如何被依序走訪：

建樹模式 (Building Trees from Input)

3
1, 2, 3
2, -, -
3, -, -

from collections import defaultdict

n = int(input())
tree = defaultdict(lambda: (None, None))

for i in range(1, n + 1):
    parts = [p.strip() for p in input().split(',')]
    node = int(parts[0])
    if i == 1:
        root = node  # 樹的根節點
    left = None if parts[1] == '-' else int(parts[1])
    right = None if parts[2] == '-' else int(parts[2])
    tree[node] = (left, right)

def height(node):
    if node is None:
        return -1  # 空節點回傳 -1，葉節點高度為 0
    left_h = height(tree[node][0])
    right_h = height(tree[node][1])
    return max(left_h, right_h) + 1

print(height(root))

1
5
5, 3, 8, 1, 4

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

n = int(input())
for _ in range(n):
    a = int(input())
    nodes = list(map(int, input().split(',')))
    root = Node(nodes[0])
    for v in nodes[1:]:
        current = root
        while True:
            if v < current.value:
                if current.left is None:
                    current.left = Node(v)
                    break
                current = current.left
            else:
                if current.right is None:
                    current.right = Node(v)
                    break
                current = current.right

    def preorder(node):
        if node:
            res.append(node.value)
            preorder(node.left)
            preorder(node.right)

    res = []
    preorder(root)
    print(' '.join(map(str, res)))

5
2, 1
3, 1
4, 2
5, 2
2
4
3

from collections import defaultdict

n = int(input())
parents = [-1] * (n + 1)
children = defaultdict(list)
for i in range(n - 1):
    c, p = map(int, input().split(','))
    parents[c] = p
    children[p].append(c)

m = int(input())
for _ in range(m):
    node = int(input())
    p = parents[node]
    if p == -1:
        print(f'siblings {node} = {{}}')
    else:
        sibs = sorted([c for c in children[p] if c != node])
        print(f'siblings {node} = {{{",".join(map(str, sibs))}}}')

下一步

觀念看完了，現在就來試試實戰題目吧！從經典的「比較兩棵樹是否完全相同」開始：