python如何遍历树

Python中树结构的遍历方法

Python中遍历树结构通常有多种方法，包括深度优先搜索（DFS）和广度优先搜索（BFS），以下是两种遍历方法的示例代码：

深度优先搜索（DFS）

def dfs(root):
    if root is None:
        return
    print(root.val)
    for child in root.children:
        dfs(child)

在这个示例中，我们首先检查根节点是否为空，如果不为空，我们打印根节点的值，并递归遍历每个子节点。

广度优先搜索（BFS）

from collections import deque
def bfs(root):
    if root is None:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val)
        for child in node.children:
            queue.append(child)

在这个示例中，我们使用Python的collections模块中的deque类来实现队列，我们将根节点加入队列，并在循环中处理队列中的每个节点，对于每个节点，我们打印其值，并将其子节点加入队列中。

无论使用哪种遍历方法，都需要根据具体的树结构和遍历需求进行选择。