樹
樹是相當重要的資料結構，它的特點便是可表達階層性的資料。
以圖定義
令無向圖\(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]得知樹中每不同兩點間僅有唯一的路徑，故不可能經由不同路徑探訪至探訪過的節點。以上樹的尋訪均是 dfs 的特例，其中反前序最接近一般的先深後廣探訪。
其演算法如下: 1.初始堆疊 unvisited 用來維護將探訪的節點 2.探訪根節點並把與根節點的子節點放入 unvisited 3.若 unvisited 不為空，選出下一節點 node 進行探訪，並把與 node 之子節點放入 unvisited 4.回上一步驟反覆進行至 unvisited 為空
code.tree_dfs.py def dfs(self): ‘先深後廣探訪，演算法見[Tree DFS]’ unvisited = [] # 這是未尋訪堆疊 cursor = self unvisited.extend(cursor.children) yield cursor while len(unvisited) > 0: cursor = unvisited.pop() unvisited.extend(cursor.children) yield cursor ::
陣列表示法 ~~~~~~~~~~ TODO
鏈結表示法 ~~~~~~~~~~ theorem.樹定理以下的陳述相互邏輯等價
1.t 為無環且連通圖 2.t 任兩個點之間，存在唯一的路徑 3.t 為最大連通，且 v=e-1 這同義於若 e in t, 則 t-e 不連通。 4.t 為最小無環，且 v=e-1，這同義於若 e not in t, 則 t+e 為有環圖。
算式樹(expression tree) ~~~~~~~~~~~~~~~~~~~~~~~ TODO
滿足問題(satisfication problem) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ TODO
決策樹(decision tree) ~~~~~~~~~~~~~~~~~~~~~~ TODO
八幣問題(eight coins problem) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ TODO
遊戲樹(game tree) ~~~~~~~~~~~~~~~~~ TODO
<d:.stx> <d:_tree.stx>
留言
張貼留言