如何打印二级树级别

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

您可以考虑逐层打印二叉树作为从根开始的树的宽度优先搜索。在广度优先搜索中，探索距离为2的节点之前距离根节点的所有节点，以及在距离为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列表中。

Answer 2

尝试为此使用递归。如果您使用的基本条件树是空的，你可以简单地这样说：

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

的想法在这里被调用左边的功能和树的分支的右部分，并把它们添加到结果包括你所在的树的根。如果树有一个空的分支，函数将附加一个空字符串和“保持滚动”。

Answer 3

这里是一些代码，将逐级打印二叉树。我使用了不同的类定义。

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]