深度优先搜索树代码 递归实现
时间: 2023-10-14 09:04:57 浏览: 37
以下是深度优先搜索树的递归实现代码,假设每个节点都有一个值和子节点列表:
```python
class TreeNode:
def __init__(self, val=0, children=None):
self.val = val
self.children = children if children is not None else []
def dfs(root):
if not root:
return
print(root.val)
for child in root.children:
dfs(child)
```
在这个代码中,我们首先检查根节点是否为空,如果是,我们直接返回。否则,我们打印根节点的值,并且对于每个子节点,递归地调用 `dfs` 函数。这将导致我们首先深入树的左侧分支,直到我们到达该分支的末端。然后,我们返回到父节点并进入下一个子节点,重复此过程,直到我们遍历了整个树。
相关问题
递归实现的深度优先搜索方法
以下是Python中递归实现的深度优先搜索方法的示例代码:
```python
# 定义一个二叉树节点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 定义深度优先搜索函数
def dfs(node):
if not node:
return
print(node.val)
dfs(node.left)
dfs(node.right)
# 创建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 调用深度优先搜索函数
dfs(root)
```
在上述代码中,我们首先定义了一个二叉树节点类,然后定义了深度优先搜索函数`dfs`。在`dfs`函数中,我们首先判断当前节点是否为空,如果为空则直接返回;否则,我们先输出当前节点的值,然后递归调用左子树和右子树的`dfs`函数。
最后,我们创建了一个二叉树,并调用`dfs`函数进行深度优先搜索。
深度优先的算法实现代码
深度优先搜索(Depth First Search,DFS)是一种用于遍历或搜索树或图的算法。下面是深度优先搜索的实现代码:
```python
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=" ")
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
```
这段代码使用递归的方式实现了深度优先搜索。它接受一个图(以邻接表形式表示)和一个起始节点作为输入,并输出遍历的结果。