樹是相當重要的資料結構,它的特點便是可表達階層性的資料。 以圖定義 令無向圖 \(G=<V, E>, |V|=n, |E|=m\) ,則以下命題皆等價: 1. 樹為無環連通圖。 2. 樹任兩點間,僅存唯一路徑。 3. 樹任兩點間,增加路徑,即形成環。 4. 樹刪除任一條路即不連通。 5. 樹為無環圖,且 m = n-1。 6. 樹為連通圖,且 m = n-1。 遞迴定義 基礎定義 單點樹,其根為自身。 遞迴定義: 令為單點,若有樹集合 ts={ t1, t2… tn},對所有 t 屬於 ts 建立一個邊連至 r 形成 r’,則 r’ 仍為樹。 r' 稱為 t 的父(parent), 而 t 稱為 r' 為子(child), r 稱為樹 r' 的根。 {t1, t2... tn}的根,稱為兄弟 silbling。 若 t 沒有子節點,稱 t 為葉 leaf。 根為無父節點。 叉(degree) ~~~~~~~~~~ 叉為一函數,若 n 為樹 t 之節點, d(n) 定義為 n 的子節點數目。 序樹(ordered tree)指樹的子節點具有一定的順序。 定義 d(t)=max(d(n)), n 屬於 t,若 d(t)=m, m 為自然數,稱 t 為m-叉樹。 若所有 n 屬於 m-叉樹 t,且 d(n)=0 or m,則 t 為滿樹(full tree)。 1-叉樹為一種退化成鏈結的樹,其每個節點最多只有一個子,又稱為藤蔓 vine 高(height) ~~~~~~~~~~ 高為一函數,若 n 為樹 t 之節點, h(n) 定義為由根 r 至 n 的路徑所連接的節點數。由上可知 h(r)=1。 定義 h(t)=max(h(n)), n 屬於 t,稱 h 為 t 的樹高。 平衡樹(balanced tree)為每個葉子都等高的樹。 完全樹(complete tree) ~~~~~~~~~~~~~~~~~~~~~ 若 t 既是滿樹,也是平衡樹,則稱為完全樹。 先深後廣探訪(Tree DFS) ~~~~~~~~~~~~~~~~~~~~~~ 先深後廣探訪先探訪離起點最遠的節點,在樹的情況中,先深後廣探訪先的實作不用額外記憶尋訪過的節點,由[theorem.tree]得知樹中每不同兩點間僅有唯一的路徑,