在 Python 中按级别顺序打印二叉树，没有左或右

Question

此问题正在寻找 this post 中给出的答案的替代方法。

如何使用以下二叉树结构创建一个字符串，该字符串在新行上具有树的每个级别：

# A Node is an object
# - value : Number
# - children : List of Nodes
class Node:
    def __init__(self, value, children):
        self.value = value
        self.children = children

我的问题是我习惯了这样的树结构：

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

这是一个示例树：

exampleTree = Node(1,[Node(2,[]),Node(3,[Node(4,[Node(5,[]),Node(6,[Node(7,[])])])])])

这将打印为：

任何有关如何使用该新结构创建定义的帮助或想法将不胜感激。

Answer 1

您可以使用队列在您的树上执行 BFS：

try:
    from queue import Queue # Python 3
except ImportError:
    from Queue import Queue # Python 2
q = Queue() # create new queue
q.put(root) # where "root" is the root node of the tree
while not q.empty():
    curr = q.get() # get next node from queue
    print(curr.value) # get node's value
    for child in curr.children:
        q.put(child) # add each child to the queue

请注意，此解决方案适用于所有树，而不仅仅是二元树

编辑：抱歉，没有意识到您希望同一级别的所有内容都在同一行输出中。使用其他解决方案（或适当修改我的）

Answer 2

您可以只使用 list.extend 添加子节点，而不是 append 一个接一个添加它们。

class Node:
  def __init__(self, value, children):
    self.value = value
    self.children = children


def traverse(root):
  curr = [root]
  while curr:
    next_level = []
    for n in curr:
      print(n.value, end='')
      next_level.extend(n.children)
    print()
    curr = next_level

exampleTree = Node(1,[Node(2,[]),Node(3,[Node(4,[Node(5,[]),Node(6,[Node(7,[])])])])])

traverse(exampleTree)

打印

（对于没有读过问题的人，这完全是 this answer 的派生词）

在 Python 中按级别顺序打印二叉树，没有左或右

Printing Binary Tree in Level Order without Left or Right in Python

python

binary-tree

python-3.x