按层次迭代打印二叉树的层级

Question

我想要逐层打印一个二叉树，使用循环的方式，不想用双端队列或其他数据结构，只想用一个Python列表。我在网上查了很多资料，大部分都是用上面提到的那些方法。

假设我有一棵树：

    41
   /  \
  7   53
 / \  /
1  19 47

我希望它打印成这样：

41

7
53

1
19
47

这是我尝试的代码，但它没有打印出二叉搜索树中的所有值：

def levelorder(self):

        current = self._root
        current_left = current_right = self._root
        a = [current._value]

        while current_left is not None and current_right is not None:

            current_left = current_left._left
            current_right = current_right._right

            if current_left is not None:
                a.append(current_left._value)

            if current_right is not None:
                a.append(current_right._value)

        return a

这是它输出的结果：

[41, 7, 53, 1]

有没有人知道我的代码哪里出错了？我该如何解决这个问题呢？

树的类定义：

class _BSTNode:

    def __init__(self, value):

        self._value = copy.deepcopy(value)
        self._left = None
        self._right = None
        self._height = 1
        return

class BST:

    def __init__(self):

        self._root = None
        self._count = 0
        self.comparisons = 0
        return

    def levelorder(self):


        levels = [[self._root]]

        while levels[-1]:

            nextlevel = []
            for node in levels[-1]:
                nextlevel.extend([node for node in (node._left, node._right) if node])

            levels.append(nextlevel)
        return levels[:-1]

这是我主要的代码部分：

b = BST()
b.insert(41)
b.insert(7)
b.insert(53)
b.insert(1)
b.insert(19)
b.insert(47)

print (b.levelorder())

Answer 1

我没有你的 Tree 类，所以不能测试，但我希望这个大致的思路是适用的：

def levelorder(tree):
    levels = [ [tree.root] ]
    while levels [-1]:
        nextLevel = []
        for node in levels [-1]:
            nextLevel.extend ( [node for node in (node.left, node.right) if node] )
        levels.append (nextLevel)
    return levels # or maybe levels [:-1]

---

下面是一个完整的示例：

#! /usr/bin/python3

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

    def __repr__(self):
        return self.payload

class Tree:
    def __init__(self, root):
        self.root = root

    def levels(self):
        levels = [[self.root]]
        while levels[-1]:
            nextLevel = []
            for node in levels[-1]:
                nextLevel.extend([node for node in (node.left, node.right) if node])
            levels.append(nextLevel)
        return levels[:-1]

t = Tree(Node('41', Node('7', Node('1'), Node('19')), Node('53', Node('47'))))

print(t.levels())

---

输出结果是 [[41], [7, 53], [1, 19, 47]]