树的广度优先搜索（BFS） 深度优先搜索(DFS)

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

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

如图，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。

1.BFS

BFS与树的层序遍历类似，使用队列实现

算法流程：

将树append到队列中while 队列不为空

取队列第一个元素

if该元素的左孩子不为空

将左孩子append到队列

if该元素的右孩子不为空

将右孩子append到队列

打印该元素的val

代码：

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

2.DFS

DFS跟前序遍历一样，使用栈实现

算法流程：

将树append到栈中while 栈不为空

取栈最后一个元素

if该元素的右孩子不为空

将右孩子append到栈

if该元素的左孩子不为空

将左孩子append到栈

打印该元素的val

代码：

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