Discussion :

[damosnet]

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.

[sologne]

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 :

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

[damosnet]

merci pour la remarque

[kwariz]

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 :

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

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 ?

[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

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

[kwariz]

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 :

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