欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

 

测试结果:

python实现二叉树的广度优先遍历(BFS)和深度优先遍历(DFS)

测试用例:

python实现二叉树的广度优先遍历(BFS)和深度优先遍历(DFS)

广度优先遍历:1,2,3,4,5,6,7,8,9

深度优先遍历:1,2,4,8,9,5,3,6,7