imprimer arbre binaire de niveau par niveau en python

Je veux imprimer mon arbre binaire de la manière suivante:

                   10

               6        12

             5   7    11  13

J'ai écrit du code pour l'insertion de nœuds, mais ne peut pas en mesure d'écrire pour l'impression de l'arbre. donc, s'il vous plaît aider sur ce point . Mon code est :

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()
  • Vous pouvez ajouter une méthode à votre Node classe qui compte compte combien de fois vous pouvez retourner un parent avant de vous obtenez None ou votre racine.
InformationsquelleAutor user2762315 | 2015-12-01
  1. 9

    Cela a un homeworky de son à elle, et si elle l'est, vous devriez le mentionner. Cependant, il est encore une question légitime.

    Ce que vous cherchez est largeur de la première traversée de l', qui vous permet de parcourir un arbre de niveau par niveau. Fondamentalement, vous utilisez une file d'attente de garder une trace des nœuds que vous avez besoin pour visiter, ajouter des enfants à la retour de la file d'attente que vous allez (au lieu de les ajouter à la avant d'une pile). Obtenir que le travail d'abord.

    Après vous le faites, alors vous pouvez comprendre comment beaucoup de niveaux de l'arbre a (log2(node_count) + 1) et de l'utiliser pour estimer les espaces. Si vous souhaitez obtenir de l'espace exactement droit, vous pouvez utiliser d'autres structures de données pour garder une trace de la façon dont de nombreux espaces vous avez besoin par niveau. Une smart estimation en utilisant le nombre de nœuds et les niveaux devrait être suffisant, mais.

    InformationsquelleAutor Juan Carlos Coto
  2. 10

    Voici ma tentative, en utilisant la récursivité, et garder une trace de la taille de chaque nœud et la taille des enfants.

    class BstNode:
def __init__(self, key):
self.key = key
self.right = None
self.left = None
def insert(self, key):
if self.key == key:
return
elif self.key < key:
if self.right is None:
self.right = BstNode(key)
else:
self.right.insert(key)
else: # self.key > key
if self.left is None:
self.left = BstNode(key)
else:
self.left.insert(key)
def display(self):
lines, _, _, _ = self._display_aux()
for line in lines:
print(line)
def _display_aux(self):
"""Returns list of strings, width, height, and horizontal coordinate of the root."""
# No child.
if self.right is None and self.left is None:
line = '%s' % self.key
width = len(line)
height = 1
middle = width // 2
return [line], width, height, middle
# Only left child.
if self.right is None:
lines, n, p, x = self.left._display_aux()
s = '%s' % self.key
u = len(s)
first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s
second_line = x * ' ' + '/' + (n - x - 1 + u) * ' '
shifted_lines = [line + u * ' ' for line in lines]
return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2
# Only right child.
if self.left is None:
lines, n, p, x = self.right._display_aux()
s = '%s' % self.key
u = len(s)
first_line = s + x * '_' + (n - x) * ' '
second_line = (u + x) * ' ' + '\\' + (n - x - 1) * ' '
shifted_lines = [u * ' ' + line for line in lines]
return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2
# Two children.
left, n, p, x = self.left._display_aux()
right, m, q, y = self.right._display_aux()
s = '%s' % self.key
u = len(s)
first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s + y * '_' + (m - y) * ' '
second_line = x * ' ' + '/' + (n - x - 1 + u + y) * ' ' + '\\' + (m - y - 1) * ' '
if p < q:
left += [n * ' '] * (q - p)
elif q < p:
right += [m * ' '] * (p - q)
zipped_lines = zip(left, right)
lines = [first_line, second_line] + [a + u * ' ' + b for a, b in zipped_lines]
return lines, n + m + u, max(p, q) + 2, n + u // 2
import random
b = BstNode(50)
for _ in range(50):
b.insert(random.randint(0, 100))
b.display()

    Exemple de sortie:

                                  __50_________________________________________ 
/                                             \
________________________43_                   ________________________99
/                           \                 /                          
_9_                         48    ____________67_____________________     
/   \                             /                                   \    
3  11_________                   54___                         ______96_   
/ \            \                       \                       /         \  
0 8       ____26___________           61___           ________88___     97  
/                 \         /     \         /             \        
14_             __42        56    64_       75_____       92_       
/   \           /                 /   \     /       \     /   \      
13  16_         33_               63  65_   72      81_   90  94      
\       /   \                     \         /   \              
25    __31  41                    66        80  87              
/                                     /                    
28_                                   76                    
\                                                        
29
    InformationsquelleAutor J. V.
  3. 2

    J'ai amélioré Prashant Shukla répondre pour imprimer les nœuds sur le même niveau dans la même ligne, sans espace.

    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)
    • Je suis confus au sujet de current_level qui est remplacé dans le for boucle sur les éléments de current_level! Pouvez-vous expliquer comment ce bout de code fonctionne?
    InformationsquelleAutor Emad Mokhtar
  4. 1

    La même question est posée sur ici Cela peut aider à code suivant apparaîtra à l'impression dans ce format 

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

    Code est comme ci-dessous : 

    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)

    Édité code donne suite dans ce format :

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

    C'est juste un truc de chemin à faire ce que vous voulez leur peut-être une bonne méthode pour que je vous suggère de creuser plus en elle.

    • merci pour la réponse mais je veux imprimer mon arbre dans le format que j'ai indiqués ci-dessus(hierarchial structure)
    • J'ai édité ma réponse originale à cette question , espérons que cela résout votre but.
    InformationsquelleAutor Prashant Shukla