博客

#Python树的BFS与DFS

BFS:Breadth First Search，广度优先搜索

DFS:Depth First Search，深度优先搜索

BFS与树的层序遍历类似，DFS则与树的后序遍历有着区别。

BFS(广度优先搜索)：

1. 使用队列实现
2. 每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，再把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
3. 优先遍历取出元素下一级的同级元素

DFS(深度优先搜索):

1. 使用栈实现
2. 每次从栈的末尾弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。
3. 优先遍历弹出元素下一级的下一级元素

以一颗满二叉树为例，如下图

# 定义节点类
class Node(object):
    def __init__(self,val,left=None,right=None):
        self.val = val
        self.left = left
        self.right = right
        
# 创建树模型
node = Node("A",Node("B",Node("D"),Node("E")),Node("C",Node("F"),Node("G")))

如图，A节点的下一级元素为B节点和C节点，B节点的下一级元素为D节点和E节点，C节点的下一级元素为F节点和G节点。

BFS优先遍历当前节点下一级节点的同级元素，即若当前节点为A节点，则继续遍历的节点为B和C；当A的所有相邻节点遍历完以后，再遍历B节点的相邻节点D节点和E节点，以及C节点的相邻节点F节点和G节点。至此，所有节点遍历完成。

DFS优先遍历当前节点下一级节点的下一级元素，即若当前节点为A节点，则继续遍历的节点为B节点和B节点的下一级节点D节点；D节点没有下一级节点，此时再返回D节点的上一级B节点处，再遍历B节点的另一个下一级元素E节点，若没有未遍历过的下一级元素，则返回上一级，依此规律遍历整个树，完成树的DFS。

代码中为了更直观地观察遍历顺序，采用直接打印node.val的方式输出遍历结果

代码实现：

def BFS(root):
# 使用列表作为队列
    queue = []
    # 将首个根节点添加到队列中
    queue.append(root)
    # 当队列不为空时进行遍历
    while queue:
    # 从队列头部取出一个节点并判断其是否有左右节点
    # 若有子节点则把对应子节点添加到队列中，且优先判断左节点
        temp = queue.pop(0)
        left = temp.left
        right = temp.right
        if left:
            queue.append(left)
        if right:
            queue.append(right)
        print(temp.val,end=" ")

def DFS(root):
# 使用列表作为栈
    stack = []
    # 将首个根节点添加到栈中
    stack.append(root)
    # 当栈不为空时进行遍历
    while stack:
    # 从栈的末尾弹出一个节点并判断其是否有左右节点
    # 若有子节点则把对应子节点压入栈中，且优先判断右节点
        temp = stack.pop()
        left = temp.left
        right = temp.right
        if right:
            stack.append(right)
        if left:
            stack.append(left)
        print(temp.val,end=" ")

print("BFS",end=" ")
BFS(node)
print("")
print("DFS",end=" ")
DFS(node)

输出结果：

BFS A B C D E F G 
DFS A B D E C F G 

代码输出结果与上述分析相符