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

今天药忘吃喽~ 2022-04-23 10:36 274阅读 0赞

# 深度优先遍历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()