python - 使用特定格式以级别顺序打印 BFS(二叉树)

Question

首先，这个问题不是 this one 的重复。 ，但建立在它之上。

以该问题中的树为例，

    1 
   / \
  2   3
 /   / \
4   5   6

你会如何修改你的程序来打印它，

1
2 3
4 5 6

而不是一般的

1 
2 
3 
4 
5 
6

我基本上是在寻找最有效方法的直觉——我有一种方法，包括将结果附加到列表中，然后循环遍历它。一种更有效的方法可能是在弹出的每个级别中存储最后一个元素，然后打印出一个新行。

想法？

Answer 1

一次只构建一个级别，例如:

class Node(object):
  def __init__(self, value, left=None, right=None):
    self.value = value
    self.left = left
    self.right = right

def traverse(rootnode):
  thislevel = [rootnode]
  while thislevel:
    nextlevel = list()
    for n in thislevel:
      print n.value,
      if n.left: nextlevel.append(n.left)
      if n.right: nextlevel.append(n.right)
    print
    thislevel = nextlevel

t = Node(1, Node(2, Node(4, Node(7))), Node(3, Node(5), Node(6)))

traverse(t)

编辑:如果您希望在最大消耗的“辅助”内存中节省一点点(在这种“辅助”内存中永远不会同时拥有所有这个级别和下一个级别)，您可以当然使用 collection.deque 而不是 list，并在你进行时使用当前关卡(通过 popleft)而不是简单地循环。一次创建一个级别的想法(当您使用 - 或迭代 - 前一个级别时)保持不变 - 当您确实需要区分级别时，它比使用单个大双端队列加上辅助信息更直接(例如深度，或给定级别中剩余的节点数)。

但是，仅附加到(并循环，而不是“消耗”)的列表比双端队列更有效(如果您使用 C++ 解决方案，则类似地， std::vector仅使用 push_back 来构建它，然后使用一个循环来使用它，比 std::deque 更有效)。由于所有的生产首先发生，然后是所有的迭代(或消费)，一个有趣的替代方案 if 内存被严格限制可能是使用一个列表来表示每个级别，然后是 .reverse 在你开始使用它之前(使用 .pop 调用)——我没有大树可以通过测量来检查，但我怀疑这种方法仍然会更快(实际上比 deque 更少的内存消耗)(假设 list [[or std::vector]] 的底层实现实际上确实在几次调用 pop [[或 pop_back]]——当然，对双端队列也有同样的假设；-)。