Ajout dans un arbre binaire

Bonjour,
Je veux savoir votre avis sur cette solution itérative pour ajouter une valeur dans un arbre binaire de recherche :

Procédure Ajouter(x:entier; var b:Arbre)
variables A:Arbre
Début
Si(B=nil) alors //arbre vide
Allouer(B)
B^. val<--x
B^.gauche<--nil
B^.droite<--nil
sinon
A<--B //A : pointeur pour chercher l'emplacement à insérer
Tantque (A#nil) faire
Si(x<A^.val) alors
A<--A^.gauche
Sinon Si(x>A^.val) alors
A<--A^.droite
FinSi
Fin TantQue
FinSi
// on obtient le pointeur dans le bon emplacement pour effectuer l'insertion

Allouer(A)
A^. val<--x
A^.gauche<--nil
A^.droite<--nil
Fin

Merci de me la corriger s'il y a une erreur.

Bonjour,
en regardant en diagonale, ta procédure me semble correcte.

par contre pense à utiliser les balises "code", et à indenter correctement pour rendre ton code plus lisible.

regarde ce que cela donne :

Code:

---

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

Procédure Ajouter(x:entier; var B:Arbre) variables A:Arbre   Début Si(B=nil) alors //arbre vide Allouer(B) B^. val<--x B^.gauche<--nil B^.droite<--nil sinon A<--B //A : pointeur pour chercher l'emplacement à insérer Tantque (A#nil) faire Si(x<A^.val) alors A<--A^.gauche Sinon Si(x>A^.val) alors A<--A^.droite FinSi Fin TantQue FinSi // on obtient le pointeur dans le bon emplacement pour effectuer l'insertion   Allouer(A) A^. val<--x A^.gauche<--nil A^.droite<--nil Fin

---

C'est plus clair, non ?

Bon courage

merci pour la remarque :ccool:

Bonjour,

Il y a une erreur car jamais tu n'insères dans l'arbre la feuille que tu crées (lier le père et le fils). Essaye ton algorithme à la main sur un exemple simple comme :

Code:

---

1 2 3

Arbre:=nil Ajouter(1,Arbre); Ajouter(2,Arbre);

---

Une autre erreur, que se passe-t-il si tu insères une valeur déjà présente dans l'arbre ?

on peut rectifier la solution par la suivante :
après la fin d'exécution de la boucle tant que, on'ai d'accord que :

1. Le pointeur A se trouve sur le bon emplacement pour ajouter une nouvelle feuille
2. Le pointeur A pointe sur Nil

alors ma solution consiste à créer une nouvelle cellule, la remplir puis effectuer le chaînage.

...
Fin TantQue
Allouer(tmp)
tmp^. val<--x
tmp^.gauche<--nil
tmp^.droite<--nil
A<--tmp
Fin

Citation:

---

Envoyé par damosnet

on peut rectifier la solution par la suivante :
après la fin d'exécution de la boucle tant que, on'ai d'accord que :

1. Le pointeur A se trouve sur le bon emplacement pour ajouter une nouvelle feuille
2. Le pointeur A pointe sur Nil

(...)

---

Bonjour,

À la sortie de ta boucle, A vaut nil : il ne pointe pas sur le bon emplacement (car cet emplacement n'existe pas). Un pointeur qui vaut nil ne pointe plus nul part.

Une version itérative de l'insertion d'une valeur dans un arbre binaire de recherche doit trouver le père pour lequel on va créer un nouveau fils ...


Ton code (et pense aux balises code !!!!) donnerait quelque chose comme ça, en utilisant une fonction de création de noeud que j'appelle CreerNoeud(val:entier; FG: Arbre; FD: Arbre) : Arbre

Code:

---

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 29 30 31 32

Procédure Ajouter(x:entier; var B:Arbre) variables A:Arbre   Début Si(B=nil) alors //arbre vide B<--CreerNoeud(val,nil,nil); sinon A<--B //A : pointeur pour chercher l'emplacement à insérer val_inseree = FAUX Tantque non val_inseree faire Si (x<A^.val) alors Si (A^.gauche=nil) alors // ici on crée et rattache la nouvelle feuille à gauche A^.gauche=CreerNoeud(val,nil,nil) val_inseree<--VRAI Sinon A<--A^.gauche Finsi SinonSi (x>A^.val) alors Si (A^.droite=nil) alors // ici on crée et rattache la nouvelle feuille à droite A^.droite=CreerNoeud(val,nil,nil) val_inseree<--VRAI Sinon A<--A^.droite Finsi Sinon // ici on a obligatoirement x = A^.val val_inseree<-VRAI // dans le cas où on ne garde pas de doublon FinSi Fin TantQue FinSi Fin

---

Autre méthode plus simple d'insertion d'une valeur dans un A.B.R
i.e : on accepte pas les doublons

Code:

---

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 29 30 31 32

Procédure Ajouter(x:Entier, var A: ABR) variables P,PP:ABR Début P<-- A PP<-- nil //pointeur père de p Tantque(p#nil) et (P^.val#x) faire PP<--P Si(x<P^.val) alors P<--P^.gauche sinon P<--P^.droite FinSi FinTantQue Si(P#nil) alors Ecrire('valeur existe') sinon Allouer(P) P^.val<--x P^.gauche<--nil P^.droite<--nil Si(PP=nil) alors A<--P sinon Si(x<PP^.val) alors PP^.gauche<--P sinon PP^.droite<--p FinSi FinSi FinSi Fin

---