Ubuntu-fr

Premium

Parcours en largeur

Salut,

quel est l'algo pour le parcours en largeur d'un arbre binaire?

Merci

Dernière modification par Premium (Le 12/06/2006, à 19:17)

gene69

Re : Parcours en largeur

héhéhé

encore toi! Courage même si la température monte, faut pas baisser les bras.

imagine un arbre

A                            20
                       /           \
B                    10             30
                    /     \        /  \
C                 5       15           31
                 / \     /  \         /  \
D                           14           32

que donne le parcour en largeur?
(A) 20 (B) 10 30 (C)5 15 31 (D) 14 32

Que se passe-t'il? Par récurence ou itération ça ne marche pas. La difficulté est de garder le pointeur sur un noeud jusqu'à ce qu'on s'interesse au fils du noeud. Parce que par rapport à un parcours infixe par exemple le parcour en largeur donne l'impression de "remonter" dans l'arbre, or c'est impossible tu le sais.

l'astuce que j'avais deviné tout seul le jour ou le prof nous a présenté ce parcours (merci pour les fleurs) est d'utiliser une file. (Comme les files d'attentes, premier arrivé = premier parti)

que fait t'on en vrai:
j'enfile 20,
je défile 20, et j'enfile ses fils 10 et 30,
je défile 10 j'enfile 5 et 15, je défile 30 j'enfile RIEN et 31
je défile 5 et j'enfile RIEN et RIEN etc.

graphe* tmp,suivant;
graphe* g = uneRacineArbre();
file* f = creerNouvelleFile();
compteur registre= mettreAZero(creerNouveauCompteur());

enfiler(g,f);

tant que etreNonVide(f);
         tmp = defiler(f)
         tant que   suivant = successeur(tmp) et alors etreValable(suivant);
                         enfiler(suivant,f);
         ecrireSortie(tmp);
         incrementer(registre);
renvoyer(registre);

c'est clair comme ça?

Dernière modification par gene69 (Le 12/06/2006, à 21:31)

---

Quand le berger est lâche, le loup chie de la laine.
A (draft) guide to UFO Alien-Invasion

gene69

Re : Parcours en largeur

pour la traduction en java je te laisse faire.

On peut pas faire les exercices à ta place quand même.

---

Quand le berger est lâche, le loup chie de la laine.
A (draft) guide to UFO Alien-Invasion