二叉树的深度优先搜索
时间: 2023-11-14 17:25:29 浏览: 70
二叉树的深度优先搜索(Depth-First Search, DFS)是一种用于遍历和搜索二叉树的算法。它沿着树的深度遍历,尽可能远地访问每个节点,直到到达叶子节点,然后回溯到上一个节点继续遍历。DFS有三种常见的遍历方式:前序遍历、中序遍历和后序遍历。
- 前序遍历(Preorder traversal):先访问根节点,然后递归地前序遍历左子树,最后递归地前序遍历右子树。
- 中序遍历(Inorder traversal):先递归地中序遍历左子树,然后访问根节点,最后递归地中序遍历右子树。
- 后序遍历(Postorder traversal):先递归地后序遍历左子树,然后递归地后序遍历右子树,最后访问根节点。
这三种遍历方式都可以使用递归或者栈来实现。以下是使用递归实现的伪代码:
```python
# 前序遍历
def dfs_preorder(node):
if node is None:
return
visit(node) # 访问当前节点
dfs_preorder(node.left) # 递归前序遍历左子树
dfs_preorder(node.right) # 递归前序遍历右子树
# 中序遍历
def dfs_inorder(node):
if node is None:
return
dfs_inorder(node.left) # 递归中序遍历左子树
visit(node) # 访问当前节点
dfs_inorder(node.right) # 递归中序遍历右子树
# 后序遍历
def dfs_postorder(node):
if node is None:
return
dfs_postorder(node.left) # 递归后序遍历左子树
dfs_postorder(node.right) # 递归后序遍历右子树
visit(node) # 访问当前节点
```
在上述代码中,visit函数表示对节点进行处理,可以是打印节点值或其它操作。这些函数都是从根节点开始调用的。