打印二叉树宽度firs的深度优先迭代深化算法

Question

我不是一个程序员，但作为我个人项目的一部分，我很想知道是否有一个递归的解决方案可以打印一个二叉树的宽度优先，级别顺序？我知道可以使用迭代深度优先算法吗？在

#Helper method
def getChildren(node):
    children=[]
    hasLeft = node.left is not None
    hasRight = node.right is not None
    if not hasLeft and not hasRight:
        return []
    if hasLeft:
        children.append(node.left)
    if hasRight:
        children.append(node.right)
    return children

def DLS(node, depth):
    """Depth Limited Search"""
    if (depth == 0):
        return node
    elif (depth > 0):
        print node.value,
        children = getChildren(node)
        for child in children:
            DLS(child, depth-1)
    else:
        return False

对于以下二叉树：
(1)3
(2)2 (3)1
(4)1 (5)1 (6)1 (7)0
(8)1 (9)0

我得到了这个遍历输出： (1)3 (2)2 (4)1 (8)1 (9)0 (5)1 (3)1 (6)1 (7)0 None

这不是水平顺序而是预订单深度优先。在

我必须迭代深度到DLS函数吗？如何实现二叉树的级别顺序打印输出？在

非常感谢 亚历克斯

Answer 1

就数据结构而言，深度优先和广度优先的区别在于深度优先使用堆栈，而宽度优先使用队列。在

首先，这个想法是“处理你最后处理的事情的后果”。所以使用堆栈时，总是弹出最后一个被推送的节点，这样就可以获得正确的行为。在

广度优先的思想是“首先处理所选节点的所有后果，然后继续前进”。所以你首先要找出后果（并储存起来），然后你才开始按照发现的顺序来处理。支持这一点的最简单的数据结构是队列。在

问题是递归使用堆栈（调用堆栈）。所以你看不到数据结构，但它确实在那里。因为没有（简单）排队调用的方法，所以如果不使用显式队列，就无法将宽度优先搜索转换为代码。在

如果您需要关于使用队列的宽度优先实现的信息，我建议您查看Wikipedia。在