### 使用Python实现树和图数据结构 #### 实现树的数据结构 在Python中，可以通过类（class）来构建树形数据结构。以下是基于二叉树的一个简单实现： ```python class TreeNode: def __init__(self, value=0, left=None, right=None): self.value = value # 节点值 self.left = left # 左子节点 self.right = right # 右子节点 def insert_into_tree(root, value): """ 插入新节点到二叉搜索树 """ if root is None: return TreeNode(value) if value < root.value: root.left = insert_into_tree(root.left, value) # 向左子树插入 elif value > root.value: root.right = insert_into_tree(root.right, value) # 向右子树插入 return root def inorder_traversal(root): """ 中序遍历二叉树 """ result = [] if root: result += inorder_traversal(root.left) # 遍历左子树 result.append(root.value) # 访问当前节点 result += inorder_traversal(root.right) # 遍历右子树 return result ``` 上述代码展示了如何创建一个简单的二叉树以及对其进行插入和中序遍历的操作[^1]。 --- #### 实现图的数据结构 对于图的表示，可以采用邻接表的方式，在Python中最常用的是字典（dictionary）。以下是一个无向加权图的实现示例： ```python class Graph: def __init__(self): self.graph = {} # 图的邻接表表示法 def add_edge(self, u, v, weight=1): """ 添加边 (u,v)，权重为weight，默认为1 """ if u not in self.graph: self.graph[u] = {} if v not in self.graph: self.graph[v] = {} self.graph[u][v] = weight # 设置权重 self.graph[v][u] = weight # 如果是有向图，则不需要这一句 def get_neighbors(self, node): """ 获取某个节点的所有邻居及其权重 """ return self.graph.get(node, {}).items() def breadth_first_search(self, start_node): """ 广度优先搜索 BFS """ visited = set() queue = [start_node] traversal_order = [] while queue: current = queue.pop(0) if current not in visited: visited.add(current) traversal_order.append(current) for neighbor, _ in self.get_neighbors(current): # 将未访问过的邻居加入队列 if neighbor not in visited: queue.append(neighbor) return traversal_order ``` 这段代码实现了图的基本功能，包括添加边、获取邻居节点以及广度优先搜索（BFS），适用于处理复杂网络关系的问题[^3]。 --- #### 应用场景分析 - **树的应用**：适合于分层结构的数据建模，例如文件系统的目录层次结构或表达式的解析树。 - **图的应用**：广泛应用于社交网络分析、地图导航中的最短路径计算等领域[^2]。 ---