python深度优先与广度优先的遍历算法比较

Bertha 。 2022-06-03 05:15 152阅读 0赞

在实现爬虫遍历页面url的算法的时候，我们需要使用到深度优先或者广度优先的遍历算法，

例子：现在我们使用两种算法进行遍历下面结构的一棵树结构

![20171219154245631][]

深度优先：

将一个子节点的所有内容全部遍历完毕之后再去遍历其他节点实现的 （递归实现）

上面的树通过深度优先遍历出来的结果是:  A-->B-->D-->E-->I-->C-->F-->G-->H

使用python语言编写的代码如下:

def depth_tree(tree_node):
        if tree_node is not None:
            print(tree_node._data)
            if tree_node._left is not None:
                return depth_tree(tree_node._left)
            if tree_node._right is not None:
                return depth_tree(tree_node._right)

广度优先:

广度优先的算法的实现是通过 分层次的进行遍历 先遍历第一层，然后第二层，第三层 (队列实现)

上面的树通过深度优先遍历出来的结果是:   A-->B-->C-->D-->E-->F-->F-->G-->H

#广度优先遍历算法 def level_queue(root):
        if root is None:
            return my_queue = []
        node = root
        my_queue.append(node)
        while my_queue:
            node = my_queue.pop(0)
            print(node.elem)
            if node.lchild is not None:
                my_queue.append(node.lchild)
            if node.rchild is not None:
                my_queue.append(node.rchild)

比较上面的两种算法，我们看出，深度优先遍历的算法是通过递归的方式一只只遍历某一个节点从而进行的，

而广度优先遍历算法则是把上一个层次的所有节点归入队列全部遍历完毕再进行下面的遍历的

[20171219154245631]: /images/20220603/f0073cb39ade4954aada830efbc7ab59.png