数据结构图的遍历代码

数据结构图的遍历是计算机科学中的一个基本概念，它涉及到对数据结构中的元素进行访问和处理。在这篇文章中，我们将探讨几种常见的数据结构图遍历方法，包括树的遍历、图的深度优先搜索（DFS）和广度优先搜索（BFS），并提供一些简单的代码示例。

树的遍历

树是一种特殊的图，其中任意两个节点之间只有一条简单路径。树的遍历通常有三种方式：前序遍历、中序遍历和后序遍历。

前序遍历（Pre-order Traversal）：首先访问根节点，然后递归地对左子树进行前序遍历，最后递归地对右子树进行前序遍历。

def preorderTraversal(root):
    if root is None:
        return
    print(root.value)  # 访问根节点
    preorderTraversal(root.left)  # 遍历左子树
    preorderTraversal(root.right)  # 遍历右子树

中序遍历（In-order Traversal）：首先递归地对左子树进行中序遍历，然后访问根节点，最后递归地对右子树进行中序遍历。

def inorderTraversal(root):
    if root is None:
        return
    inorderTraversal(root.left)  # 遍历左子树
    print(root.value)  # 访问根节点
    inorderTraversal(root.right)  # 遍历右子树

后序遍历（Post-order Traversal）：首先递归地对左子树进行后序遍历，然后递归地对右子树进行后序遍历，最后访问根节点。

def postorderTraversal(root):
    if root is None:
        return
    postorderTraversal(root.left)  # 遍历左子树
    postorderTraversal(root.right)  # 遍历右子树
    print(root.value)  # 访问根节点

图的深度优先搜索（DFS）

深度优先搜索是一种用于遍历或搜索树或图的算法。DFS从根节点开始，尽可能深地搜索树的分支。

def dfs(graph, visited, node):
    visited[node] = True
    print(node)  # 访问节点
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(graph, visited, neighbor)

# 使用示例
visited = {node: False for node in graph}  # 初始化访问标记
dfs(graph, visited, start_node)  # 从起始节点开始DFS

图的广度优先搜索（BFS）

广度优先搜索是另一种遍历图的算法，它从一个节点开始，逐层遍历图中的所有节点。

from collections import deque

def bfs(graph, start_node):
    queue = deque([start_node])
    visited = {node: False for node in graph}
    while queue:
        node = queue.popleft()
        if not visited[node]:
            print(node)  # 访问节点
            visited[node] = True
            queue.extend(neighbor for neighbor in graph[node] if not visited[neighbor])

# 使用示例
bfs(graph, start_node)  # 从起始节点开始BFS