樹 (Tree)

樹 (Tree)

樹是一種「沒有環的連通圖」。也就是說，任兩個節點之間剛好只有一條路徑，不會出現繞一圈回來的情況。

基本性質

有 n 個節點的樹，一定有 n − 1 條邊。
任意兩點之間都有唯一一條路徑。
不含環。

常見的幾種樹

根樹 (rooted tree)：指定一個節點當根 (root)，方便往下分層。
二元樹 (binary tree)：每個節點最多有兩個子節點 (left, right)。
表達式樹 / 語法樹：用樹的結構表示運算式或程式語法。

常用名詞

根節點 (root)：整棵樹的起點。
父節點 / 子節點：層級之間的上下關係。
葉節點 (leaf)：沒有子節點的節點。
樹高 (height)：根到最深葉節點的長度。