如何通过

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

可以将逐级打印二叉树视为从根开始的树的宽度优先搜索。在广度优先搜索中，在距离2的节点之前搜索距离1的所有节点，在距离3的节点之前搜索距离2的所有节点，等等

实际上我不知道任何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仍然在我的TODO列表中。