Dans une structure de données arborescente, afficher les nœuds de l'arborescence niveau par niveau

Question

Question: Comment pouvons-nous afficher les nœuds d'arbre niveau par niveau? pourriez-vous s'il vous plaît me donner temps et espace solution efficace.

Exemple:

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

void PrintTree(struct tree *root); 

Sortie: Vous devez imprimer le niveau des nœuds d'arbres par niveau

A 
    B C 
    D E F G 

Answer 1

Si vous vous sentez bestiale, et que vous voulez penser très simplement sur le niveau que vous êtes ...
Vous aurez besoin:

• Deux files d'attente
• une légère torsion sur l'approche de Jack

Alors, commencez par la racine.
Fixez ses enfants sur la première file d'attente. Parcourez-les, en passant leurs enfants dans la deuxième file d'attente au fur et à mesure.
Basculez dans la deuxième file d'attente, en poussant leurs enfants dans la première file d'attente.
Cirer, enlever la cire. En réalité, il ne s'agit que d'une légère expansion de la même idée, de la largeur de la première recherche ou balayage, ce qui vaut la peine d'être considéré comme un motif, puisqu'il s'applique à une variété de structures de données. Presque tout ce qui est un arbre ou trie, et quelques choses qui ne sont pas, en fait!

Answer 2

Ce genre de visite est appelée largeur d'abord ou Niveau Commande. Vous pouvez voir des informations supplémentaires here.

Fondamentalement, vous

• première visite le noeud courant
• alors tous les enfants de ce noeud
• alors tous les enfants de tous les enfants et ainsi de suite

Ceci devrait être réalisé facilement avec une structure FIFO:

• pousser la racine
• jusqu'à ce que la file d'attente est vide
• prendre premier élément, visiter, et pousser tous ses enfants à la fin de la file d'attente
• répétition

Answer 3

Pour économiser de l'espace et le temps sur le SO:

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