使用_specific formatting_以级别顺序打印BFS(二叉树)

Question

首先,这个问题是不是一个DUP 这一个,而是以它.

以该问题中的树为例,

    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更有效.由于所有生成都是先发生的,然后所有迭代(或消耗),如果内存受到严格约束,一个有趣的替代方案可能是使用列表来表示每个级别,然后.reverse在开始使用它之前(使用.pop调用) - 我没有大树可以通过测量来检查,但我怀疑这种方法仍然会比deque(假设list [[或std :: vector]]的底层实现确实更快(并且实际上更少耗费内存)在几次调用pop[[或pop_back]] 之后回收内存- 当然还有deque相同的假设;-).

Answer 2

听起来像广度优先遍历我.

广度优先遍历是通过队列实现的.在这里,只需在队列中插入一个特殊标记,表示必须打印换行符.每次找到令牌时,打印换行符并在队列中重新插入令牌(最后 - 这是队列的定义).

使用包含root后跟特殊换行令牌的队列启动算法.