一、BFS与DFS简介

在理解动态规划、BFS和DFS一文中，已经集合具体例子，介绍了图的BFS与DFS。但是比较复杂，这里就写的简单点吧。

BFS：每次输出一行，所用数据结构为队列
设想我们每次都从左到右、从上到下的去遍历一个图，那么就需要把一行中最左边先进来的先输出，最右边后进来的后输出。所以会用到队列。

DFS：每次深挖到底，所用数据结构为栈
设想我们从图的最上边先按照一条道深挖到最下面，在挖到底以后就需要再逐个返回到上面的顶点，再去遍历父节点是不是还有别的子节点。后进先出的模式，所以需要用到栈。

因为这是在图中，所以，一个顶点的相邻点可能包含着已经搜索过的点，因此这两个遍历都需要加一个集合nodeSet，里面是已经遍历过的点。在搜索过程中，如果发现新的节点已经存在于nodeSet中，那么就不对新节点进行搜索了。

而，如果是在树中用BFS与DFS，因为一个节点顶多有两个子节点，我们已经明确知道这个节点除了子节点以外不会再有相邻节点，因此在搜索过程中也不会遇到重复的节点，所以不需要加nodeSet。只需要按照BFS与DFS的思想与所用数据结构，遍历即可。

二、代码实现

参考 图的广度优先搜索（BFS）与深度优先搜索（DFS） Python实现

2.1、树的广度优先搜索

因为是树，每个node至多有两个子节点，而下面代码中语句是对图中不确定的子节点个数来说的，因此下面的这句

for next in cur.nexts:

都可以用对左右两个子节点的遍历来代替，参考前序遍历那一篇文章。
不过为了体现图的思想，这里都用上面这句代码来实现吧。

• 1.利用队列实现
• 2.从源节点开始依次按照宽度进队列，然后弹出
• 3.每弹出一个节点，就把该节点所有没有进过队列的邻接点放入队列
• 4.直到队列变空

这里如果需要按照BFS的顺序输出二叉树的元素的话，那么就可以把nodeSet去掉了。

def bfs(node):
    if node is None:
        return
    queue = []
    #nodeSet = set() 
    queue.insert(0,node)
    #nodeSet.add(node)
    while queue:
        cur = queue.pop()               # 弹出元素
        print(cur.val)                # 打印元素值
        for next in cur.nexts:          # 遍历元素的邻接节点
            #if next not in nodeSet:     # 若邻接节点没有入过队，加入队列并登记
                #nodeSet.add(next)
                queue.insert(0,next)

2.2、树的深度优先搜索

2.2.1、用递归的方法进行dfs

这里递归不需要nodeSet

因为想到有栈的思想，那么就不可避免的想到递归。

• 递归结束条件：节点是None，结束函数调用
• 递归改变：每次都要把节点添加到节点集合当中去
• 递归调用：对于每一个当前节点的相邻节点，只要不在节点集合中，就调用dfs进行搜索

#nodeSet = set()
def dfs1(node):
    if node is None:
        return
    #nodeSet.add(node)
    print(node.val)
    #相当于树的前序遍历了，只不过这里把左右子节点放到了nexts的列表中
    for next in node.nexts:
        #if next not in nodeSet:
            dfs1(next)

2.2.2、用循环的方法进行dfs

这个方法其实是图的遍历方法，对于树的DFS，其实不需要用nodeSet，可以参考树3，用循环实现树的三种遍历

若是按照如下方法进行dfs，那么还是要用nodeSet来保证不会重复遍历一些节点了。

用循环的方法，就一定会用到栈了。
对于下面代码，有两个地方需要解释：
1、为什么弹出了cur以后还要把cur压入栈中？

答：为了保证出入栈的顺序，若是cur没有子节点，则直接弹出栈。如果有子节点，那么就要再把cur压入栈，再把cur的子节点压入栈。这样，下一次栈弹出的会是cur的子节点，在子节点遍历完并且再次弹出栈以后，当前节点的索引又会回到父节点cur上。

2、为什么最后要用break语句？

**保持深度优先的顺序，在遍历完cur的左子节点以后，下一步会跳出循环，

• 你可以看看，若是不用break会是什么效果：以树为例，在搜索完根节点的左子节点以后，紧接着会把右子节点压入栈中。而不是我们预想的把左子节点的左子节点压入栈中。
• 在对root搜索到左子节点L1以后 ，此时我们想对L1进行搜索，而我们又想到此时此时此时，L1是在栈顶的，那我们何不直接break出循环，直接到对L1进行搜索。
  所以循环中用了一个break来保持深度优先

def dfs(node):
    if node is None:
        return
    nodeSet = set()
    stack = []
    print(node.val)
    nodeSet.add(node)
    stack.append(node)
    while len(stack) > 0:
        cur = stack.pop()               # 弹出最近入栈的节点
        for next in cur.nexts:         # 遍历该节点的邻接节点
            if next not in nodeSet:    # 如果邻接节点不重复
                stack.append(cur)       # 把节点压入
                stack.append(next)      # 把邻接节点压入
                nodeSet.add(next)           # 登记节点
                print(next.val)       # 打印节点值
                break                   # 退出，保持深度优先

用二叉树来检验上述算法

对于TreeNode类，在构造函数中又添加了一个next属性近似代替图中的临近节点列表。

#实现一个二叉树，并且用BFS或DFS去遍历她
class TreeNode:
    def __init__(self,x):
        self.val = x
        self.left = None
        self.right = None
        self.nexts = []

        
root_node = TreeNode(1)
node_2 = TreeNode(2)
node_3 = TreeNode(3)
node_4 = TreeNode(4)
node_5 = TreeNode(5)
node_6 = TreeNode(6)
node_7 = TreeNode(7)
node_8 = TreeNode(8)
node_9 = TreeNode(9)
node_10 = TreeNode(10)

def littleTree(root,left,right):
    root.left = left
    root.right = right
    if root.left:
        root.nexts.append(root.left)
    if root.right:
        root.nexts.append(root.right)

littleTree(root_node, node_2, node_3)
littleTree(node_2, node_4, node_5)
littleTree(node_3, node_6, node_7)
littleTree(node_4, node_8, node_9)
littleTree(node_5, node_10, None)