Python版二叉树BFS与DFS遍历详细代码
5星
- 浏览量: 0
- 大小:None
- 文件类型：None
简介：
本文章提供了一个详细的教程和完整代码示例，介绍如何使用Python实现二叉树的广度优先搜索（BFS）和深度优先搜索（DFS）两种遍历方法。
本段落将详细介绍二叉树的广度优先遍历（BFS）与深度优先遍历（DFS）在Python中的实现方式。
对于广度优先搜索(Breadth First Search, BFS)而言，我们需要使用队列来存储节点，并逐层访问每个结点。以下是基于此方法的一个简单的Python代码示例：
```python
from collections import deque
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def bfs(root: TreeNode) -> list[int]:
if not root:
return []
queue, result = deque([root]), []
while queue:
node = queue.popleft()
# 添加当前节点的值到结果列表中
result.append(node.val)
# 如果左子树存在，将其加入队列
if node.left:
queue.append(node.left)
# 如果右子树存在，也将其加入队列
if node.right:
queue.append(node.right)
return result
```
对于深度优先搜索(DFS)，我们通常有三种方式来实现：前序遍历、中序遍历和后序遍历。这里以递归的方式给出一个例子：
```python
def dfs_preorder(root: TreeNode) -> list[int]:
def traverse(node):
if not node:
return []
# 访问当前节点
result.append(node.val)
# 递归访问左子树和右子树
traverse(node.left)
traverse(node.right)
result = []
traverse(root)
return result
```
该DFS前序遍历函数通过先处理根结点，再分别对左右子节点进行同样的操作来完成整个二叉树的遍历。另外两种方式（中序和后序）仅需调整访问当前节点的操作位置即可。
以上就是关于Python实现BFS与DFS的基本代码介绍，希望对你有所帮助。
全部评论 (0)
