Discussion :

[slim_java]

salut tout le monde.
j'ai un problème au niveau de l'ajout d'un noeud dans un ABR:
le principe est en fait :
1- recherche dans l’arbre permettant de déterminer la feuille où doit se faire l’insertion,
2- création du noeud et modification du lien père.


mon probléme est au niveau du deusiéme point qui indique qu'apres avoir touver la place du noeud a insérer, il faut modifier le lien du père !!
alors que dans cette algorithme , il na pas fait cette modification :

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
void inserer(etudiant *x, arbre *a)
{
if (!*a)
{
*a=....malloc...
*a->element = x;
*a->FG=*a->FD=null;
}
else
{
if(x->age<*a->element->age)
inserer(x,&(*a->FG));
else
inserer(x,&(*a->FD));
}
}

je sais que c'est un truc de passage des adresses mais j'arrive pas a comprendre la situation.
si quelqu’un me donne une explication par un shéma ou autre..merci

[Flodelarab]

Bonjour

Tout est clair. Tu fais la question 2) avant d'avoir fait la question 1).
Tu dois chercher où insérer. Sinon, tu insères n'importe où et ce n'est pas bon. L'avantage de chercher l'endroit où insérer est que tu auras la référence du père

Bonne chance

[slim_java]

bien merci , j'ai compris qu'avec la la question 1 on cherche où insérer et qu'on aura par conséquence(par recursion) la référence du père.
Alors si on fait le parcour et on arrive a null, on fait l 'insertion où on est arrivé (c'est ce qui est implémenté par la version recursive).
Remarquer maintenant cette version itérative dans la quelle on "rebousse chemin" si on trouve qu'on est arriver à un noeud qui pointe sur NULL.(regarder les commentaires de mon code)
==>contradiction avec la version récurisie !!!

je rappelle ici que l'insertion se fait toujours a la fin au niveau des feuilles, par exemple dans cette figure l'ajout se fait apres le noeud 68, donc si on arrive a null,on fait l'insertion

voici le code itérative :

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
20
21
22
23
24
25
26
27
28
arbre inserer(struct etudiant * l, arbre a)
{
struct noeud p,pp,q;
q=(struct neoud*)malloc (sizeof(struct noeud));
q->elem=l;
q->G=q->D=NULL;

if(!a) a=q;
else 
{
p=a;
while(p)
{
  pp=p;// pour garder la derniére adresse(adresse du feuille) avant de pointer sur null (une feuille pointe sur nul )
if(q>elem->code < pp->elem->code)
 p=p->G
else
p=p->D;
}
if(q-> elem-> code < pp ->elem-> code)
pp->G=q;//remarque ici il a travailler avec pp et non pas l'adresse de p avec le quel il a fait le parcours.(a la fin de while p pointe vers null)
         // alors que dans la version récursive que j'ai donner en haut , il fait insertion sur le pointeur avec le quel il a fait le parcours (ce pointeur avec lequel  il a fait l'insertion pointe vers null)

}//fin else

return (a);
}

[Flodelarab]

Sans même regarder les exemples, la solution est évidente. Tu prends une précaution avec le code itératif, que tu ne prends pas avec le code récursif.
On ne veut pas le dernier pointeur. Mais le dernier pointeur non null.

[slim_java]

alors si on fait pas cette précaution, c'est pas correcte ? ça ne fonctionne pas ?