Discussion :

[nadia85]

Bonsoir,

Je voudrais implémenter la version itérative de la copie d'un arbre binaire de recherche dans un autre ABR.

La version récursive est la suivante:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
node * copier(node* A, node* B)
{
  if(A!=NULL) 
   {
       B=inserer_rec(B,A->val);
       copier(A->FG,B);
       copier(A->FD,B);
   }
   return B;
}

Pour la version itérative j'ai pensé à utiliser une file dont les cellules renferment les nœuds de l'arbre originale:

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
17
18
19
 
node * copie(node* A, node* B)
 {
     File* F;
     node* root; cellule* a;
 
     if (A!=NULL)
      enfiler(A,F);
     while(!FileEstVide(F))
     {
         root=F->tete->valeur;   /* la cellule contient un nœud */
         B=inserer_rec(B,root->val);   /* le nœud contient un entier */
         defiler(F);
         enfiler(root->FG,F);
         enfiler(root->FD,F);
     }
 
     return B;
 }

Je n'arrive pas à récupérer l'arbre B pour l'afficher.
Pourriez-vous m'aider à repérer le problème?

Merci d'avance

[foetus]

Tous les algos de parcours itératifs sont sur la page wikipedia : Tree traversal#Depth-first search implementation, lien en anglais
Sur cette page tu as aussi 1 lien vers l'algo de Morris pour 1 parcours infixe sans pile.

Je pense qu'il faut faire 1 parcours infixe ("in-order traversal") pour insérer les éléments dans le nouveau arbre 1 à 1.

[nadia85]

Bonsoir

j'ai rectifié mon code en initialisant ma file à NULL, et cela a bien marché.

Merci

[Médinoc]

Tous les algos de parcours itératifs sont sur la page wikipedia : Tree traversal#Depth-first search implementation, lien en anglais

C'est décevant que tous leurs parcours "itératifs" soient avec pile (et donc, récursifs déguisés).
Il y a moyen de faire du vrai itératif sur un parcours d'arbre, mais ça nécessite que chaque nœud maintienne un pointeur sur son parent en plus des pointeurs vers ses enfants.

↓Tu as raison.

[WhiteCrow]

En même temps j'ai envie de dire que les algos récursifs sont extrêmement bien adapté sur des structures de donnée récursives. Passer en itératif n'apportera sans doute pas grand chose et nuira certainement autant à la lisibilité qu'à la maintenance du code.