2024年11月7日 星期四

一維串列二元搜尋樹DFS

 使用一維串列表示的二元搜尋樹進行深度優先搜尋 (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]

沒有留言:

張貼留言