python实现二叉树的广度优先遍历(BFS)和深度优先遍历(DFS)
程序员文章站
2022-05-21 19:25:26
...
本文用python3实现二叉树的广度优先遍历(BFS)和深度优先遍历(DFS)。
完整代码链接:https://github.com/toanoyx/BasicAlgorithm/tree/master/tree
广度优先遍历
广度遍历又叫层次遍历。用队列实现,依次将根,左子树,右子树存入队列,按照队列的先进先出规则来实现层次遍历。
# 层次遍历(广度优先)
def BFS(root):
if root:
res = []
queue = [root]
while queue:
currentNode = queue.pop(0)
res.append(currentNode.val)
if currentNode.left:
queue.append(currentNode.left)
if currentNode.right:
queue.append(currentNode.right)
return res
深度优先遍历
用栈实现,先将根入栈,再将根出栈,并将根的右子树,左子树存入栈,按照栈的先进后出规则来实现深度优先遍历。
# 深度优先
def DFS(root):
if root:
res = []
stack = [root]
while stack:
currentNode = stack.pop()
res.append(currentNode.val)
if currentNode.right:
stack.append(currentNode.right)
if currentNode.left:
stack.append(currentNode.left)
return res
测试结果:
测试用例:
广度优先遍历:1,2,3,4,5,6,7,8,9
深度优先遍历:1,2,4,8,9,5,3,6,7
上一篇: 深度优先遍历和广度优先遍历
推荐阅读
-
Java实现二叉树的深度优先遍历和广度优先遍历算法示例
-
深度优先遍历,广度优先遍历实现对象的深拷贝
-
Python实现深度遍历和广度遍历的方法
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
PHP实现二叉树的深度优先与广度优先遍历方法
-
深度优先遍历,广度优先遍历实现对象的深拷贝
-
可能是目前为止最为详细的深度优先搜索DFS和广度优先搜索BFS算法分析
-
Java数据结构与算法:图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现
-
【数据结构】图的遍历——深度优先搜索DFS、广度优先搜索BFS
-
数据结构与算法————图的遍历DFS深度优先搜索和BFS广度优先搜索