печати двоичного уровень дерева на уровне питона

Question

Я хочу напечатать мое бинарное дерево следующим образом:

    10 

       6  12 

      5 7 11 13 

Я написал код для вставки узлов, но не в состоянии писать для печати дерева. поэтому, пожалуйста, помогите по этому поводу. Мой код:

class Node: 
    def __init__(self,data): 
     self.data=data 
     self.left=None 
     self.right=None 
     self.parent=None 

class binarytree: 
    def __init__(self): 
    self.root=None 
    self.size=0 

    def insert(self,data): 
    if self.root==None: 
     self.root=Node(data) 

    else: 
     current=self.root 
     while 1: 
      if data < current.data: 
       if current.left: 
        current=current.left 
       else: 
        new=Node(data) 
        current.left=new 
        break; 
      elif data > current.data: 
       if current.right: 
        current=current.right 
       else: 
        new=Node(data) 
        current.right=new 
        break; 
      else: 
       break 



b=binarytree() 

Answer 1

У этого есть домашнее звучание, и если это так, вы должны упомянуть об этом. Однако это все еще законный вопрос.

Что вы ищете, это breadth-first traversal, что позволяет пройти уровень дерева по уровню. В основном, вы используете очередь для отслеживания узлов, которые вам нужно посетить, добавляя детей в назад очереди, когда вы идете (в отличие от добавления их к передним стека). Сначала начните работать.

После этого вы можете определить, сколько уровней имеет дерево (log2(node_count) + 1) и использовать это для оценки пробелов. Если вы хотите получить пробелы точно вправо, вы можете использовать другие структуры данных, чтобы отслеживать, сколько пробелов вам нужно за уровень. Однако достаточно умной оценки с использованием количества узлов и уровней.

Answer 2

Похожий вопрос в настоящее время ответил более here Это может помочь следующий код будет печатать в этом формате

>>> 
1 
2 3 
4 5 6 
7 
>>> 

Код для этого, как показано ниже:

class Node(object): 
    def __init__(self, value, left=None, right=None): 
    self.value = value 
    self.left = left 
    self.right = right 

def traverse(rootnode): 
    thislevel = [rootnode] 
    a = '         ' 
    while thislevel: 
    nextlevel = list() 
    a = a[:len(a)/2] 
    for n in thislevel: 
     print a+str(n.value), 
     if n.left: nextlevel.append(n.left) 
     if n.right: nextlevel.append(n.right) 
     print 
     thislevel = nextlevel 

t = Node(1, Node(2, Node(4, Node(7)),Node(9)), Node(3, Node(5), Node(6))) 

traverse(t) 

Edited код дает результаты в этом формате:

>>> 
       1 
     2   3 
    4  9  5  6 
7 
>>> 

Это всего лишь трюк, способный сделать то, что вы хотите, чтобы их, может быть, правильный метод, который я предлагаю вам вникнуть в него.

Answer 3

Я усовершенствовал Prashant Shukla answer, чтобы печатать узлы на одном уровне в одной строке без пробелов.

class Node(object): 
    def __init__(self, value, left=None, right=None): 
     self.value = value 
     self.left = left 
     self.right = right 

    def __str__(self): 
     return str(self.value) 


def traverse(root): 
    current_level = [root] 
    while current_level: 
     print(' '.join(str(node) for node in current_level)) 
     next_level = list() 
     for n in current_level: 
      if n.left: 
       next_level.append(n.left) 
      if n.right: 
       next_level.append(n.right) 
      current_level = next_level 

t = Node(1, Node(2, Node(4, Node(7)), Node(9)), Node(3, Node(5), Node(6))) 

traverse(t)