如何逐层打印二叉树

Question

你想用Python把一个二叉树的数据按层级从上到下打印出来，对吧？

我刚开始接触这个，完全不知道该怎么着手。

from collections import deque

class EmptyTree(object):
    def isEmpty(self):
        return True

    def __str__(self):
        return ""    

class BinaryTree(object):

    THE_EMPTY_TREE = EmptyTree()

    def __init__(self, item):
        self._root = item
        self._left = BinaryTree.THE_EMPTY_TREE
        self._right = BinaryTree.THE_EMPTY_TREE

    def isEmpty(self):
        return False

    def getRoot(self):
        return self._root

    def getLeft(self):
        return self._left

    def getRight(self):
        return self._right

    def setRoot(self, item):
        self._root = item

    def setLeft(self, tree):
        self._left = tree

    def setRight(self, tree):
        self._right = tree

    def removeLeft(self):
        left = self._left
        self._left = BinaryTree.THE_EMPTY_TREE
        return left

    def removeRight(self):
        right = self._right
        self._right = BinaryTree.THE_EMPTY_TREE
        return right

    def __str__(self):
        """Returns a string representation of the tree
        rotated 90 degrees to the left."""
        def strHelper(tree, level):
            result = ""
            if not tree.isEmpty():
                result += strHelper(tree.getRight(), level + 1)
                result += "| " * level
                result += str(tree.getRoot()) + "\n"
                result += strHelper(tree.getLeft(), level + 1)
            return result
        return strHelper(self, 0)

Answer 1

这里有一段代码，可以按层级打印一个二叉树。不过我用了不同的类定义。

from collections import deque

def treeLevels(self):
        # Two queues, one for the nodes one for the level of the nodes.
        Q = deque()
        L = deque()

        # Initiation and printing the root.
        Q.append(self.root)
        level = 0
        L.append(level)
        print level, [self.root.key]

        while len(Q) > 0:
            u = Q.popleft()
            l = L.popleft()

            # For the current node if it has a left or right child,
            # add it to the queue and with its corresponding level + 1.
            if u.left != None:
                Q.append(u.left)
                L.append(l + 1)
            if u.right != None:
                Q.append(u.right)
                L.append(l+1)

            # If there is a node still in the queue and all the nodes in the queue
            # are at the same level, then increment the level and print.
            if len(L) > 0 and L[0] > level and L[0] == L[-1]:
                level += 1
                print level, [x.key for x in Q]

Answer 2

试着用递归来解决这个问题。如果你设定一个基本条件，就是树是空的，那么你可以简单地写成这样：

def printTree(me):
  if isEmpty(me):
    return ""
  else:
    return getRoot(me) + printTree(getLeft(me)) + printTree(getRight(me))

这里的意思是对树的左边和右边的分支分别调用这个函数，然后把它们的结果加到一起，同时也包括你当前所在的树的根节点。如果树的某个分支是空的，函数就会加上一个空字符串，然后“继续进行”。

Answer 3

你可以把按层打印二叉树想象成从树的根节点开始进行广度优先搜索。在广度优先搜索中，你会先探索离根节点一层的所有节点，然后再去看离根节点两层的节点，接着是三层的节点，依此类推。

其实我对Python编程并不熟悉，但这个算法的伪代码非常简单。考虑到Python本质上就是可以执行的伪代码，我觉得把它转成合法的Python代码应该不会太难。:-)

Create a queue Q of nodes to visit.
Enqueue the tree root into Q.

While Q is not empty:
    Dequeue an element from the queue, call it u.
    Output u.

    If u has a left child, add that to the queue.
    If u has a right child, add that to the queue.

希望这对你有帮助！抱歉没有提供真正的代码；学习Python仍然在我的待办事项列表上。