首页 文章

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

提问于
浏览 次
0

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

#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 函数？我如何实现二进制树的级别订单打印输出？

非常感谢Alex

python data-structures recursion

1 回答

  • 1

    在数据结构方面，深度优先和广度优先的区别在于深度优先使用堆栈，广度优先使用队列 .

    在深度优先，这个想法是“处理你处理的最后一件事的后果” . 因此，对于堆栈，您始终会弹出最后推送的节点，并获得正确的行为 .

    在广度优先，这个想法是“首先处理所选节点的所有后果，然后继续前进” . 因此，您首先要找出后果（并存储它们），然后才能按照找到它们的顺序开始处理它们 . 支持此操作的最简单的数据结构是队列 .

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

    如果您需要有关队列的广度优先实现的信息，我建议您查看Wikipedia .

    回复于

相关问题