Discussion :

[nicolas2117]

Bonjour,
j'aimerais juste savoir comment supprimer un arbre en utilisant que des boucles, sans appels récursif.
mon type arbre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
struct noeud
{
  T valeur;
  struct noeud* fg;
  struct noeud* fd;
};
 
typedef struct noeud arbre;

Ma fonction "delete" récursive:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
void arbre_delete(arbre* a)
{
if(a!=NULL)
{
arbre_delete(arbre_fg(a));
arbre_delete(arbre_fd(a));
free(a);
}
}

j'espere pouvoir faire la meme chose avec des boucles. Merci de me mettre sur la voie

[Climoo]

Il y a plusieurs possibilités... J'en connais une simple, première qui me vient à l'esprit :
Parcourir tout l'arbre (par la méthode que tu veux, mais prend la plus simple en iteratif tant qu'a faire, je sais plus laquelle simplemente le plus facilement entre post/inf/pre-fixe), de stocker chaque adresse de noeuds dans un tableau de pointeurs, puis de liberer chacune de ces adresses (après le parcours bien sûr).

Après ya surement plus élégant et plus efficace, mais là, ca demande plus ample réflexion

[nicolas2117]

Il y a plusieurs possibilités... J'en connais une simple, première qui me vient à l'esprit :
Parcourir tout l'arbre (par la méthode que tu veux, mais prend la plus simple en iteratif tant qu'a faire, je sais plus laquelle simplemente le plus facilement entre post/inf/pre-fixe), de stocker chaque adresse de noeuds dans un tableau de pointeurs, puis de liberer chacune de ces adresses (après le parcours bien sûr).

Après ya surement plus élégant et plus efficace, mais là, ca demande plus ample réflexion

Bas le premier probleme c'est que je ne vois pas vraiment comment parcourir l'arbre en iteratif, mais en plus j'aimerai evité le tableau de pointeur. Apres est ce possible je n'en sais absolument rien :p

[Climoo]

En effet le tableau de pointeur c'est pas terrible terrible...
Pour les parcours, tu devrais trouver en cherchant un peu un qui est itératif (sur ce site ou bien ailleurs).

Ensuite il mest venu une autre idée (j'allais mendormir dans mon lit quand soudain...)
Il te faut juste une pile. Ca te suffit ? de toute facon sans structure annexe, ca risque detre sacrément difficile... Voilà l'algo que je te propose :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
arbre a
pile p
si (racine <> nil) 
   empiler(p,racine)
   tant que (non (est_vide(p))) faire
      a=depiler(p)
      si (a.fg <> nil)
         empiler(a.fg)
      fsi
      si (a.fd <> nil)
         empiler(a.fd)
      fsi
      liberer(a)
    ftq
fsi

Ca devrait marcher... Après c'est à verifier. Sur ce, je vais vraiment me coucher...

[matafan]

Ensuite il mest venu une autre idée (j'allais mendormir dans mon lit quand soudain...)
Il te faut juste une pile.

Comme celle qui sert à empiler les appels de fonction par exemple

A moins que les noeuds de ton arbre contiennent un lien vers leur parent, le parcours d'un arbre nécessite effectivement une pile. Donc tant qu'à faire, autant faire du récursif.

[Médinoc]

Dès qu'il y a une pile, tu peux appeler ça du récursif. Qu'il s'agisse de la pile système ou d'une pile extérieure.

Et comme l'ont déjà dit les autres, comme ton arbre ne possède pas de pointeur vers le nœud parent, tu dois forcément y aller en récursif.