stampa albero binario livello per livello in python

2022-07-29 10:30:05

Voglio stampare il mio albero binario nel modo seguente:

                   10

               6        12

             5   7    11  13 

Ho scritto il codice per l'inserimento dei nodi ma non riesco a scrivere per la stampa dell'albero. quindi per favore aiutatemi su questo. Il mio codice è :

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()  

- user2762315

Source
Risposta


32
  • Quello che stai cercando è breadth-first traversal, che ti consente di attraversare un albero livello per livello. Fondamentalmente, usi una coda per tenere traccia dei nodi che devi visitare, aggiungendo i bambini sul indietro della coda mentre procedi (invece di aggiungerli in prima > di una pila). Prima fallo funzionare.

    Dopo averlo fatto, puoi capire quanti livelli ha l'albero (log2(node_count) + 1) e usarlo per stimare gli spazi bianchi. Se vuoi ottenere esattamente lo spazio bianco, puoi utilizzare altre strutture di dati per tenere traccia di quanti spazi sono necessari per livello. Tuttavia, dovrebbe essere sufficiente una stima intelligente utilizzando il numero di nodi e livelli.