如何打印二級樹級別

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]