使用一維串列表示的二元搜尋樹進行深度優先搜尋 (DFS) 時,我們可以利用遞迴或堆疊來實現。在這種樹結構中,每個節點的位置由索引計算得出,並依照「左子節點 = 2i + 1」、「右子節點 = 2i + 2」的規則進行訪問。
DFS 的三種方式
在二元樹中,DFS 有三種基本遍歷方式:前序遍歷 (Preorder Traversal)、中序遍歷 (Inorder Traversal) 和 後序遍歷 (Postorder Traversal)。我們可以使用遞迴來實現每種遍歷方法。
一維串列 DFS 前序、中序和後序遍歷
前序遍歷 (Preorder Traversal) - DFS
在前序遍歷中,先訪問根節點,再依次訪問左子樹和右子樹。
def dfs_preorder(tree, i=0):
if i >= len(tree) or tree[i] is None:
return []
return [tree[i]] + dfs_preorder(tree, 2 * i + 1) + dfs_preorder(tree, 2 * i + 2)
# 測試前序遍歷
bst = [5, 3, 7, 2, 4, 6, None, 1]
print("前序遍歷 (DFS):", dfs_preorder(bst)) # 預期 [5, 3, 2, 1, 4, 7, 6]
中序遍歷 (Inorder Traversal) - DFS
在中序遍歷中,先訪問左子樹,再訪問根節點,最後訪問右子樹。
def dfs_inorder(tree, i=0):
if i >= len(tree) or tree[i] is None:
return []
return dfs_inorder(tree, 2 * i + 1) + [tree[i]] + dfs_inorder(tree, 2 * i + 2)
# 測試中序遍歷
print("中序遍歷 (DFS):", dfs_inorder(bst)) # 預期 [1, 2, 3, 4, 5, 6, 7]
後序遍歷 (Postorder Traversal) - DFS
在後序遍歷中,先依次訪問左子樹和右子樹,最後訪問根節點。
def dfs_postorder(tree, i=0): if i >= len(tree) or tree[i] is None: return [] return dfs_postorder(tree, 2 * i + 1) + dfs_postorder(tree, 2 * i + 2) + [tree[i]] # 測試後序遍歷 print("後序遍歷 (DFS):", dfs_postorder(bst)) # 預期 [1, 2, 4, 3, 6, 7, 5]
沒有留言:
張貼留言