二叉树深度优先和广度优先过程的Python描述
程序员文章站
2022-05-22 20:57:07
...
二叉树深度优先(DFS)和广度优先(BFS)
深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。二叉树的深度优先遍历的非递归的通用做法是采用栈,要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历、中序遍历、后序遍历。具体说明如下:
- 先序(根)遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树。
- 中序(根)遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树。
- 后序(根)遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。
DFS的Python算法描述:
def depth_tree(tree_node):
"""
# 深度优先过程
:param tree_node:
:return:
"""
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)
注:
scrapy
默认是通过深度优先来实现的。
广度优先遍历:又叫层次遍历,从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。广度优先遍历的非递归的通用做法是采用队列。
BFS的算法描述:
def level_queue(root):
"""
# 广度优先过程
:param root:
:return:
"""
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)
区别:
通常深度优先搜索法遍历时不全部保留结点,遍历完后的结点从栈中弹出删去,这样,一般在栈中存储的结点数就是二叉树的深度值,因此它占用空间较少。所以,当搜索树的结点较多,用其它方法易产生内存溢出时,深度优先搜索不失为一种有效的求解方法。 但深度优先搜素算法有回溯操作(即有入栈、出栈操作),运行速度慢。
广度优先搜索算法,一般需存储产生的所有结点,占用的存储空间要比深度优先搜索大得多,因此,程序设计中,必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作,即入栈和出栈的操作,所以运行速度比深度优先搜索要快些。