Как я могу напечатать бинарное дерево уровня по уровню

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

Вы можете думать о распечатке бинарного дерева по уровням как поиск в ширину дерева, начинающегося в корне. При поиске в ширину вы исследуете все узлы на расстоянии один от корня до узлов на расстоянии два, а узлы на расстоянии два от корня до узлов на расстоянии три и т. Д.

На самом деле я не знаю программирования на 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]