Python二叉树深度与广度优先遍历实现详解

Leo

发布时间：2026-10-13| 5人浏览过

原创

本文介绍Python中二叉树的两种核心遍历方式：深度优先遍历（DFS）与广度优先遍历（BFS）。深度遍历基于递归逻辑，遵循“根-左-右”顺序；广度遍历结合队列思想，逐层访问节点。文章通过Node类定义树结构，并展示具体的递归实现代码，帮助开发者理解遍历算法的本质与Python编码技巧。

深度优先遍历（DFS）

其核心原则是遵循“从上到下、从左到右”的访问顺序。

具体逻辑实现主要依赖递归机制，步骤如下：

首先定位并访问根节点；

接着递归处理根节点的左子树；

最后递归处理根节点的右子树。

class Node(object):
 def __init__(self, item=None, left=None, right=None):
  self.item = item
  self.left = left
  self.right = right
 
 
d = Node("D")
e = Node("E")
b = Node("B", d, e)
f = Node("F")
g = Node("G")
c = Node("C", f, g)
a = Node("A", b, c)
 
 
result = []
 
 
def deep_search(root):
 # 深度遍历 核心：递归
 result.append(root.item)
 if root.left:
  deep_search(root.left)
 if root.right:
  deep_search(root.right)
 return "-->".join(result)
 
 
print deep_search(a)

广度优先遍历（BFS）

该算法的核心在于结合队列数据结构与递归逻辑进行逐层访问。

def wide_search(root, result=[]):
 
 if not result:
  result.append(root.item)
 if root.left:
  result.append(root.left.item)
 if root.right:
  result.append(root.right.item)
 if root.left:
  wide_search(root.left)
 if root.right:
  wide_search(root.right)
 return "-->".join(result)
 
 
print wide_search(a)

以上关于Python实现二叉树深度与广度遍历的方法介绍完毕，希望能为读者提供有益参考。