好的！以下是用 Python 实现的一个简单示例，展示如何通过深度优先搜索（DFS）遍历一棵树或图结构。 假设我们有一棵由字典表示的树形结构，其中每个节点有一个编号，并指向其子节点的列表： ### 示例代码： ```python # 构建一个简单的树形结构 (也可以看作无环图) graph = { 'A': ['B', 'C'], # A 节点连接 B 和 C 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['G', 'H'], 'F': [], 'G': [], 'H': [] } def dfs(graph, start): """ 使用递归实现 DFS 算法。 参数: graph: 图结构，这里用字典表示 {node: [neighbors]} start: 开始节点 返回: None （仅打印访问顺序） """ visited = set() # 记录已经访问过的节点 def helper(node): # 内部递归函数 if node not in visited: print(node, end=" ") # 打印当前节点 visited.add(node) # 将该节点加入已访问集合 for neighbor in graph[node]: # 遍历所有邻居节点 if neighbor not in visited: helper(neighbor) # 对于未访问的邻居继续深搜 helper(start) if __name__ == "__main__": print("DFS Traversal:") dfs(graph, 'A') # 从节点'A'开始进行深度优先遍历 ``` 运行结果可能是类似这样的输出序列： **DFS Traversal:** A B D E G H C F 这是因为程序按照深度优先的方式依次探索了各个分支路径。 --- #### 如果想改成非递归版本的话，我们可以利用栈数据结构手动模拟递归过程： ```python def iterative_dfs(graph, start): stack, path = [start], [] # 初始化堆栈以及记录走过的路径 visited = set([start]) # 创建一个集合来存储已被访问的位置信息 while stack: vertex = stack.pop() path.append(vertex) # 把当前顶点添加进最终的结果里去 for neighbour in reversed(graph[vertex]): # 先把右边的内容压入再取出来保证左边先得到处理 if neighbour not in visited: visited.add(neighbour) stack.append(neighbour) return path result_path = iterative_dfs(graph,'A') print("\nIterative DFS Result:", result_path) ``` 以上即为使用Python完成基本DFS任务的一种方法及其变体形式。你可以根据不同需要调整输入和内部逻辑！