Suppression d'un arbre en C

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

Code:

---

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:

---

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 :mouarf:

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

Citation:

---

Envoyé par 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

---

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

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:

---

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...

Citation:

---

Envoyé par Climoo

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 :mrgreen:

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.

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.

Merci de vos réponses.
Effectivement, si c'est pour utiliser une pile je prefere de loin le recursif...
Dans le cas ou j'utiliserai

Code:

---

1 2 3 4 5 6 7

struct noeud { T valeur; struct noeud* pere; struct noeud* fg; struct noeud* fd; };

---

Comment puis je le faire en itératif(la suppression de l'arbre), désolé mais je vois pas comment :s
Et est il plus intéressant d'utiliser cette structure en itératif pour des parcours d'arbre, ou la structure de départ en récursif?

Moi, il me vient à l'esprit un moyen assez simple de faire tenir tout cela dans un seul while() en utilisant une file à la place d'une pile ... :-) et sans champ « *pere ».

Citation:

---

Et est il plus intéressant d'utiliser cette structure en itératif pour des parcours d'arbre, ou la structure de départ en récursif?

---

Ça dépend énormément du contexte mais, en l'occurence, garder un champ « père » qui ne sert qu'à détruire l'arbre est absurde car cela te coûtera toujours plus que ce que ta fonction récursive stockera dans ta pile, et en plus, ce sera permanent (au contraire de ta fonction qui n'utilise de la mémoire qu'au moment voulu et qui la rend automatiquement quand elle n'en a pas besoin).

Par contre, d'une manière générale, à fonctions comparables (c'est-à-dire quand l'une n'implique pas la mise en place d'un dispositif dont l'autre n'a pas besoin), il est toujours plus intéressant de faire de l'itératif que du récursif.

Citation:

---

Envoyé par Obsidian

Moi, il me vient à l'esprit un moyen assez simple de faire tenir tout cela dans un seul while() en utilisant une file à la place d'une pile ... :-) et sans champ « *pere ».

---

Mouai si c'est pour remplacer une pile par une file sa me change pas grand chose :cry:

Citation:

---

Envoyé par Obsidian

Ça dépend énormément du contexte mais, en l'occurence, garder un champ « père » qui ne sert qu'à détruire l'arbre est absurde car cela te coûtera toujours plus que ce que ta fonction récursive stockera dans ta pile, et en plus, ce sera permanent (au contraire de ta fonction qui n'utilise de la mémoire qu'au moment voulu et qui la rend automatiquement quand elle n'en a pas besoin).

---

pas forcément sa depend de la hauteur de l'arbre ainsi que du type T. Mais effectivement je ne pense pas que rajouter un champ a ma structure est la meillleur solution. Mais par pur curiosité j'aimerai bien voir comment faire, car je dois l'avouer j'en est aucune idée :aie:

Citation:

---

Envoyé par nicolas2117

Mais par pur curiosité j'aimerai bien voir comment faire, car je dois l'avouer j'en est aucune idée :aie:

---

Bon, après relecture, l'algorithme utilisant une file est le même que celui à pile de Climoo en #4, et en plus, il consomme beaucoup plus de mémoire. Il stocke la moitié de l'arbre, là où une pile ne stocke que la branche explorée. En plus, la pile est plus facile à gérer. Donc, on oublie.

Par contre, il a l'avantage de détruire l'arbre « dans l'ordre » (père, puis fils, puis petits-fils) tels que les noeuds auraient été créés, même récursivement. En plus, il permet d'affirmer que l'algorithme n'est plus du tout récursif.

Citation:

---

pas forcément sa depend de la hauteur de l'arbre ainsi que du type T. Mais effectivement je ne pense pas que rajouter un champ a ma structure est la meillleur solution.

---

Non, Si tu as un champ « père », tu auras en permanence n éléments en mémoire, là où la file n'en retiendrait que n/2 et la pile log2(n). Pour te donner un ordre d'idée, pour un arbre complet à 16 niveaux :

- 65535 éléments non libérables dormants (autant que le nombre de nœuds) avec un champ « père », avant le processus de libération. Tant que ton arbre existe, cette mémoire est perdue et, en plus, cela t'oblige à modifier la structure.

- 32768 éléments dans la file, étant donné que pour chaque élément supprimé, on ajoute 2 fils, soit un nœud stocké pour chaque nœud visité, jusqu'à ce que l'on atteigne le dernier niveau. Donc emmagasinage de n-1 niveaux. Exploration « en largeur d'abord ».

- 16 avec la pile, puisqu'on explore d'abord les fils, « en profondeur » d'abord, ce qui permet de commencer à retirer des nœuds (les feuilles) sans en ajouter, avant d'avoir exploré la totalité des niveaux supérieurs.

Dans tous les cas, la solution à champ « père » est la pire si elle ne sert qu'à la suppression de l'arbre, d'autant plus qu'elle stocke exactement les mêmes informations que la fonction de suppression dans la pile ou la file, mais que ce travail est fait à l'avance. Et ce prétraitement ne t'apporte rien puisque cela t'oblige ensuite à examiner plusieurs fois le même nœud.

En revanche, l'intérêt d'une telle méthode est d'être applicable à un automate : il n'a besoin d'aucune mémoire des états antérieurs pour mener à bien sa mission.

Citation:

---

Envoyé par Obsidian

Bon, après relecture, l'algorithme utilisant une file est le même que celui à pile de Climoo en #4, et en plus, il consomme beaucoup plus de mémoire. Il stocke la moitié de l'arbre, là où une pile ne stocke que la branche explorée. En plus, la pile est plus facile à gérer. Donc, on oublie.

Par contre, il a l'avantage de détruire l'arbre « dans l'ordre » (père, puis fils, puis petits-fils) tels que les noeuds auraient été créés, même récursivement. En plus, il permet d'affirmer que l'algorithme n'est plus du tout récursif.



Non, Si tu as un champ « père », tu auras en permanence n éléments en mémoire, là où la file n'en retiendrait que n/2 et la pile log2(n). Pour te donner un ordre d'idée, pour un arbre complet à 16 niveaux :

- 65535 éléments non libérables dormants (autant que le nombre de nœuds) avec un champ « père », avant le processus de libération. Tant que ton arbre existe, cette mémoire est perdue et, en plus, cela t'oblige à modifier la structure.

- 32768 éléments dans la file, étant donné que pour chaque élément supprimé, on ajoute 2 fils, soit un nœud stocké pour chaque nœud visité, jusqu'à ce que l'on atteigne le dernier niveau. Donc emmagasinage de n-1 niveaux. Exploration « en largeur d'abord ».

- 16 avec la pile, puisqu'on explore d'abord les fils, « en profondeur » d'abord, ce qui permet de commencer à retirer des nœuds (les feuilles) sans en ajouter, avant d'avoir exploré la totalité des niveaux supérieurs.

Dans tous les cas, la solution à champ « père » est la pire si elle ne sert qu'à la suppression de l'arbre, d'autant plus qu'elle stocke exactement les mêmes informations que la fonction de suppression dans la pile ou la file, mais que ce travail est fait à l'avance. Et ce prétraitement ne t'apporte rien puisque cela t'oblige ensuite à examiner plusieurs fois le même nœud.

En revanche, l'intérêt d'une telle méthode est d'être applicable à un automate : il n'a besoin d'aucune mémoire des états antérieurs pour mener à bien sa mission.

---

Dans le cas ou on utilise pere, tu n'as pas besoin de pile, file ou autre... Donc ton arbre si il fait n element de m taille, la taille total utilisée est n*m. Alors que si tu utilise la recursivité qui utilise la pile ton arbre a une taille de n*(m-taille_de_pere) + la taille de la pile, car a chaque appel pour passer aux fils tu stock un pointeur donc si tu a un arbre de hauteur z, tu stocke z*(taille_pointeur) (et il y a aussi les autres valeurs stocké sur la pile de facon caché). Enfin au final en utilisant la recursivité c'est plus lourd non? Enfin je me trompe peut etre :aie:

Citation:

---

Envoyé par nicolas2117

Dans le cas ou on utilise pere, tu n'as pas besoin de pile, file ou autre...

---

Ce que je veux dire, c'est que les éléments que tu ne stockes pas dans ta pile, tu les stockes à la place dans ton arbre. Et, à cette place, ils occupent de la mémoire de façon permanente.

Donc, non seulement, ça revient au même, mais en plus, c'est la méthode qui coûte le plus de mémoire, puisque là où la taille de ta pile ne dépassera jamais la profondeur de ton arbre (soit 8 éléments stockés dans la pile pour un arbre complet de 256 nœuds ou feuilles), tu stockeras autant de pointeurs qu'il y a de nœuds dans ton arbre, y compris pour la racine puisque le champ « père » est alloué de manière statique par la définition de la structure.

Si tu gères ta pile toi-même, tu n'as pas besoin d'y stocker autre chose que les pointeurs « père ». Si tu appelles récursivement la fonction de nettoyage, tu stockeras effectivement un pointeur-père plus l'adresse de retour de la fonction, et comme ils ont en principe le même format, tu stockes donc 2*log2(n) éléments. En faisant le calcul, on s'aperçoit que ça redevient rentable au delà de six nœuds.

Citation:

---

Enfin au final en utilisant la recursivité c'est plus lourd non? Enfin je me trompe peut etre

---

Eh bien, curieusement, non. Parfois, on a l'intuition que c'est qui va être le plus compliqué, alors que ça peut être au contraire ce qui va se révéler le plus simple.

Un exemple : quand j'avais désassemblé le BASIC de mon TO8D, je me suis notamment demandé comment il gérait le GOSUB. Étant donné qu'il y avait déjà une pile assez complexe pour les boucles (FOR, DO, etc.), je m'attendais à un truc du même acabit. Et bien non : un simple appel (JSR, équivalent de CALL sur Intel), au même point d'entrée que le GOTO, au niveau du microprocesseur. Deux octets de retour dans la pile, et ça suffisait.

Évidemment, ça dépend beaucoup de la manière dont la fonction a été écrite. Si tout un tas de variables locales sont déclarées dans son corps pour le traitement de l'élément en cours, il est certain qu'elles vont d'autant multiplier la taille de la pile.

Quand on lit ta réponse sa semble logique que c'est plus intéressant en recursif :mouarf:, j'avais pas vu sa comme sa :aie:
Enfin merci à tous pour les explications.:)

Citation:

---

Envoyé par nicolas2117

j'avais pas vu sa comme sa :aie:

---

Hint : le « ç » se trouve sur la touche « 9 » ! :-)