階層查找與樹
樹是相當重要的資料結構，它的特點便是可表達階層性的資料。
遞迴定義
一個節點為樹。
令 N 為某樹之節點，且存在樹 \(T_1, T_2…T_n\)，則將其連接至 N 後仍為樹，其中 \(T_1, T_2…T_n\) 稱為 N 之子，而 N 為其父。
其他定義
無父節點為根，無子節點為葉，節點的子數稱為度數。由根至 N 路徑上的節點數目為 N 的高。
若一個樹，其節點最大度數為 m 者，稱為m-叉樹；其節點之子均以特定順序組織者，稱為序樹；其所有葉均等高者，稱為平衡樹。
如果一個 m-叉樹，其節點度數非 0 即 m，稱為滿樹；既是滿樹，亦是平衡樹者，稱為完全樹。
1-叉樹又稱為藤蔓，為一種退化成鏈結的樹。
以圖定義
以下陳述互為等價：
- 樹為無環連通圖。
- 樹為無環且邊數為點數減一之圖。
- 樹為連通且邊數為點數減一之圖。
- 樹如於任兩點間增加一邊，即形成環。
- 樹任兩點間，僅存唯一路徑。
- 樹刪除任一路徑即不連通。
如以兩兩論證上述陳述相互等價，則須證明任2個陳述等價，而陳述對共有6取2即15種。每個陳述對論證等價均需雙向推論一次，即須30次證明。如運用循環論證，即由陳述1推論陳述2，再由陳述2推論陳述3，以此類推至陳述5推論陳述6，再由陳述6推論回陳述1完成循環論證後，任二陳述即能以循環論證其等價，但只要證明6次。
其他性質
- 在給定一組節點之無向圖，樹是邊數最多的無環圖，也是邊數最少的連通圖。
宋玉〈登徒子好色賦〉名句「增之一分則太長，減之一分則太短」性質。
- 任何非平凡樹至少有兩葉。
先深後廣探訪
先深後廣探訪先探訪離起點最遠的節點，在樹的情況中，先深後廣探訪先的實作不用額外記憶尋訪過的節點，由[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
留言