二叉树的遍历：深度优先与广度优先.pdf
需积分: 1 141 浏览量
2024-05-20
09:34:00
上传
评论
收藏 124KB PDF 举报
二叉树的遍历：深度优先与广度优先
在数据结构和算法中，二叉树是一种常见且重要的数据结构。对于二叉树的操作，遍历是最基本也最常
用的一种。本文将详细介绍二叉树的遍历方法，包括深度优先遍历（前序、中序、后序）和广度优先遍
历（层次遍历）。
一、深度优先遍历（DFS）
深度优先遍历，即按照树的深度遍历树的节点，尽可能深地搜索树的分支。在二叉树中，主要有三种深
度优先遍历方式：前序遍历、中序遍历和后序遍历。
1. 前序遍历（Pre-order Traversal）
前序遍历的顺序是：根节点 -> 左子树 -> 右子树。
以下是一个使用Python实现前序遍历的示例代码：
2. 中序遍历（In-order Traversal）
中序遍历的顺序是：左子树 -> 根节点 -> 右子树。这种遍历方式在二叉搜索树中特别有用，因为它会按
照升序访问所有节点。
3. 后序遍历（Post-order Traversal）
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def preorder_traversal(root):
if root is None:
return
print(root.val, end=' ') # 访问根节点
preorder_traversal(root.left) # 遍历左子树
preorder_traversal(root.right) # 遍历右子树
# 示例用法
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
preorder_traversal(root) # 输出: 1 2 4 5 3
def inorder_traversal(root):
if root is None:
return
inorder_traversal(root.left) # 遍历左子树
print(root.val, end=' ') # 访问根节点
inorder_traversal(root.right) # 遍历右子树
# 示例用法（沿用上面的树结构）
inorder_traversal(root) # 输出: 4 2 5 1 3
资源评论
