Python深度优先遍历DFS与广度优先遍历BFS

深度优先遍历DFS与广度优先遍历BFS

以下代码块是在python3.7-32bit下成功运行的例子，其中广度优先遍历是由队列实现的，深度优先遍历是由递归和栈两种方法实现的。

""" 广度优先遍历和深度优先遍历在二叉树以及图的问题上非常重要。 要深入理解这两种遍历的过程实现，先知道怎么用纸和笔比画出来。 深入理解先入先出和后入先出这两个过程，是一个二层的过程，上一层先弄的下一层也先弄为队列，上一层先弄的下一层后弄为栈。 """
# 先造出来一棵简单的二叉树结构供使用
class Tree:
    def __init__(self, list_of_three):
        # list_of_three [1，2，3] 根左右
        # print("依次输入树的根、左节点、右节点")
        # .node其实是当前节点的值
        # 面向对象思想还是挺有用的
        if list_of_three[0] != 0:
            self.node = list_of_three[0]
        else:
            self.node = "none"
        if list_of_three[1] != 0:
            self.left = list_of_three[1]
        else:
            self.left = "none"
        if list_of_three[2] != 0:
            self.right = list_of_three[2]
        else:
            self.right = "none"
# 进行广度优先遍历BFS
def BFS(root_node):
    # pop(0)和append()是队列
    q = []
    q.append(root_node)
    while len(q) != 0:
        temp = q.pop(0)
        print(temp.node)
        if temp.left != "none":
            q.append(temp.left)
        if temp.right != "none":
            q.append(temp.right)
# 使用递归方式实现DFS
def DFS_recursion(root_node):
    print(root_node.node)
    if root_node == "none":
        return
    if root_node.left != "none":
        DFS_recursion(root_node.left)
    if root_node.right != "none":
        DFS_recursion(root_node.right)
# 使用栈来实现DFS
def DFS_stack(root_node):
    # pop()和append()是栈，pop()就差个0与队列相比
    s = []
    if root_node == "none":
        return
    s.append(root_node)
    while len(s) != 0:
        temp = s.pop()
        print(temp.node)
        if temp.right != "none":
            s.append(temp.right)
        if temp.left != "none":
            s.append(temp.left)
def main():
    # 自定义搭建了一棵二叉树
    node = "root"
    n = [i for i in range(12)]
    for i in range(12):
        n[i] = Tree([i, 0, 0])
    n[5] = Tree([5, n[10], n[11]])
    n[4] = Tree([4, n[8], n[9]])
    n[3] = Tree([3, n[6], n[7]])
    n[2] = Tree([2, n[4], n[5]])
    n[1] = Tree([1, n[2], n[3]])  
    # 变量的覆盖作用，导致之前的未被更新，解释性语言，所以赋值需要从后往前
    print("--------------------------------------------------------------")
    print("基于递归的深度优先遍历：")
    DFS_recursion(n[1])
    print("--------------------------------------------------------------")
    print("基于栈的深度优先遍历：")
    DFS_stack(n[1])
    print("--------------------------------------------------------------")
    print("广度优先遍历：")
    BFS(n[1])
    print("--------------------------------------------------------------")
if __name__ == "__main__":
    main()