[algo] algo non recursif pour parcourir les niveaux d'un arbre

Marsh Posté le 11-03-2005 à 11:00:43

hello,

un algo non-recursif et simple pour parcourir successivement les niveaux d'un arbre, comment on fait ca ?

Sylvain

Marsh Posté le 11-03-2005 à 11:00:43

Marsh Posté le 13-03-2005 à 15:50:40

ben avec une file (un tableau) :

enfile la racine,
tant que la file n'est pas vide,
défile le noeud (traite le),
enfile chaque enfant du noeud,
fin tant que.

Marsh Posté le 13-03-2005 à 15:52:11

tin, regle [OC] :fou:

c'est peu-etre passé pour l'autre pas cette fois

---------------
Nos estans firs di nosse pitite patreye...

Marsh Posté le 13-03-2005 à 16:17:01

dude,
on ne fait pas le boulot a ma place.

pour "l'autre fois", avant d'avoir une reponse pertinante,
j'avais deja trouvé une solution iterative, et une solution reccursive.
je voulais juste d'autre idee, ce que j'ai eu par "leneuf22"

Pour la question ici, j'ai deja plusieurs idees de reponses.
mais je ne pretends pas les avoir toutes, ni meme avoir la meilleure. donc toute autre solution m'interesse

Message édité par slvn le 13-03-2005 à 16:19:01

Marsh Posté le 16-03-2005 à 02:16:48

Apres reflexion, je pense que l'exo est pas mal tout.
il doit y avoir un algo en O(n) et O(1) espace.

Pour l'arbre, on suppose qu'il est equilibré et on peut prendre la structure suivante pour le décrire:

Code :

struct node{
struct node *gauche;
struct node *droite;
int valeur_a_afficher;
};

Marsh Posté le 16-03-2005 à 08:12:45

Oui, mais non.
Là t'es lourd avec tes questions qui sont clairement des exos...On ne fait pas la résolution d'exos, ici.

---------------
Can't buy what I want because it's free -

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed

Name *

Email *

URL

Message *