In una struttura dati ad albero, visualizza i nodi dell'albero livello per livello

Question

Domanda: come possiamo visualizzare i nodi dell'albero livello per livello?potresti per favore darmi una soluzione efficiente in termini di tempo e spazio.

Esempio :

    A
   / \
  B   C
 / \  / \
D   E F  G

void PrintTree(struct tree *root);

Produzione:Devi stampare i nodi dell'albero livello per livello

  A
  B C
  D E F G

Answer 1

Se ti senti brutale e voglio pensare molto semplicemente circa il livello si è a ...
Avrete bisogno di:

• due code
• Una leggera torsione sul metodo di Jack

Quindi, inizia con la radice.
Tack suoi figli sulla prima fila.
Passo attraverso di loro, virata loro figli sulla seconda coda, come si va.
Passare alla seconda coda, passo attraverso, spingendo i loro figli sulla prima fila.
Cera su, cera off.

In realtà è solo una leggera espansione della stessa idea, la ricerca in ampiezza o spazzare, che è il pensiero vale circa come un modello, in quanto si applica a una varietà di strutture di dati. Quasi tutto ciò che è un albero o trie, e un paio di cose che non sono, in realtà!

Answer 2

Per risparmiare spazio e tempo su SO:

http://thecodecracker.com/c-programming/bfs-and-dfs /

Answer 3

Questo tipo di visita si chiama Prima in ampiezza O Ordine di livello.Puoi vedere informazioni aggiuntive Qui.

Fondamentalmente tu

• visitare prima il nodo corrente
• quindi tutti i figli di quel nodo
• poi tutti i figli di ogni figlio e così via

Ciò dovrebbe essere ottenuto facilmente con una struttura FIFO:

• spingere la radice
• finché la coda non sarà vuota
• prendi il primo elemento, visitalo e spingi tutti i suoi bambini fino alla fine della coda
• ripetere