本节介绍广度优先搜索算法的核心思想与一般方法.
广度优先搜索算法的一般算法:
广度优先搜索算法的具体思想就是从起始节点开始,访问该节点所有与之相邻并且未被访问过的节点,让后依次对每个节点执行上述操作,最终实现所有节点的遍历.这一过程需要借助队列,其先进先出的特点可以保证依次访问各个节点.广度优先算法是一种盲目搜索,在查找的过程中覆盖性的访问每个节点的所有子节点,搜索目标节点的过程并不考虑目标节点的可能位置,而是较为彻底的搜索整个树或图.
二叉树的层序遍历:
广度优先算法的一个常用场景就是二叉树的层序遍历,即逐层的,按照从左到右的顺序依次访问各个节点.先将根节点入队,让后进行一个迭代的过程,只要队列不为空,就弹出其最左边的元素进行输出,即队列头部的元素;然后使其左右子节点依次入队,继续迭代过程.变量如下:
root变量:输入变量,表示给定二叉树的根节点
queue变量:表示队列结构
完整代码如下:
# 定义一个函数VisitTree，用于遍历二叉树
def VisitTree(root):# 如果根节点为空，则直接返回if not root:return# 初始化一个队列，并将根节点加入队列queue = deque([root])# 当队列不为空时，执行循环while queue:# 从队列中取出队头元素（即下一个要访问的节点）node = queue.popleft()# 打印当前节点的值print(node.val)# 如果当前节点有左子节点，将左子节点加入队列if node.left:queue.append(node.left)# 如果当前节点有右子节点，将右子节点加入队列if node.right:queue.append(node.right)
