La notion d'arbre est vraiment ardue (pour moi) car elle fait appel à trois notions complexes en programmation : structure, pointeur et récursivité.
I) Structure
Dans PureBasic (et dans d'autres langages), une structure est un type d'objet défini par le programmeur. Petit rappel : un type de variable indique les données que peut traiter cette variable. Par exemple, dans PB, une variable de type Byte supporte les nombres entiers de -128 à + 127, tandis qu'une variable de type String supporte tous les caractères. Une structure permet de créer son propre type de variable, en respectant une convention d'écriture et en utilisant des types de variables existants.
Par exemple, je veux stocker des données de consommation moyenne de carburant des voitures. Il me faut : une marque, un modèle et la consommation moyenne mixte. Ma structure sera (syntaxe PB) :
Code : Tout sélectionner
Structure Conso
marque.s
modele.s
mixte.f
EndStructure
Code : Tout sélectionner
Structure Conso
marque.s
modele.s
mixte.f
EndStructure
Define MaVoiture.Conso, TaVoiture.Conso
MaVoiture.Conso\marque="fiat"
MaVoiture.Conso\modele="cinquecento"
MaVoiture.Conso\mixte=4.5
TaVoiture.Conso\marque="peugeot"
TaVoiture.Conso\modele="206 HDi 90"
TaVoiture.Conso\mixte=5.5
Lorsqu'une donnée est chargée en mémoire vive (RAM), le système d'exploitation (SE) lui assigne un emplacement et donc une adresse. Cette adresse est utilisée par le SE pour manipuler la donnée. Elle peut aussi être utilisée par le programmeur. Il n'a pas pour autant à connaître la valeur de l'adresse (qui est de plus variable). Il suffit que le programmeur créé un objet appelé "pointeur" qui servira à référencer l'adresse mémoire de la donnée. Par exemple, le code suivant :
Code : Tout sélectionner
MonObjet.b=12
*AdrPoint=@MonObjet ; *AdrPoint est un pointeur !
Un pointeur peut "pointer" une structure. L'instruction suivante déclare le pointeur, l'associe a une structure et l'initialise avec l'adresse de MaVoiture
Code : Tout sélectionner
*MonPoint.Conso=@MaVoitureCode : Tout sélectionner
MaVoiture.Conso\marque="fiat"
*MonPoint.Conso=@MaVoiture
Debug MaVoiture\marque
Debug *MonPoint\marque
Code : Tout sélectionner
Structure Conso
marque.s
modele.s
mixte.f
EndStructure
Structure Classement
carburant.s
*nom.Conso
EndStructure
Define MaVoiture.Conso, Voiture.Classement
MaVoiture.Conso\marque="fiat"
*MonPoint.Conso=@MaVoiture
Voiture\carburant="gazole"
Voiture\nom=@MaVoiture
Debug Voiture\nom\marque + " " + Voiture\carburant
Code : Tout sélectionner
Structure Conso
marque.s
modele.s
mixte.f
EndStructure
Structure Classement
carburant.s
*nom.Conso
EndStructure
Debug "Taille Conso: " + Str(SizeOf(Conso)) + " octets. Classement: " + Str(SizeOf(Classement)) + " octets"
Ici, il s'agit d'une procédure qui s'appelle elle-même. Evidemment, l'astuce consiste à trouver un critère pertinent d'arrêt. Exemple (archi classique : calcul de factoriel !) :
Code : Tout sélectionner
Procedure.q Fact(n.q)
If n=1
ProcedureReturn 1
Else
ProcedureReturn n*Fact(n-1)
EndIf
EndProcedure
Define.q n=1
While n < 16
Debug Str(n) + "! = " + Str(Fact(n))
n=n+1
Wend
IV) Les arbres binaires
La gestion des arbres fait appel à la récursivité car un arbre se décompose en sous-arbres (qui sont en réalité eux aussi des arbres). Supposons un arbre constitué d'un parent (ou noeud) avec deux fils au maximum. Il s'agit de ce qu'on appelle un arbre binaire. Dans notre exemple, le parent est un nombre entier. Le fils de gauche contient l'arbre des valeurs inférieurs au parent et le fils de droite contient l'arbre des valeurs supérieurs au parent. Soit, dans la pratique, la structure suivante :
Code : Tout sélectionner
Structure ARB
valeur.b
*gauche.ARB
*droite.ARB
EndStructure
Maintenant, il faut alimenter la structure ARB. Alimenter ARB signifie créer un premier arbre, puis un second etc. La création d'un arbre nécessite de demander au SE de lui allouer de la mémoire pour le remplir (et donc le créer). C'est l'instruction : AllocateMemory. le montant a allouer est celui de la taille de la structure ARB (cf. SizeOf).
Lors de la création du second arbre avec un nouveau nombre entier, celui-ci peut être égal au nombre du premier arbre, inférieur ou supérieur. Si le nouveau nombre entier est égal, il n'y a rien à faire (dans notre exemple volontairement simple) puisque l'arbre existe avec la valeur. Si le nouveau nombre est inférieur, il faut le ranger dans l'arbre gauche (qui n'existe pas encore : il faudra le créer), sinon il faut le ranger dans l'arbre droit (qui n'existe pas encore : il faudra le créer). Le processus sera identique pour le 3ième nombre, puis le 4ième, etc.
Pour résumé, il faut d'abord savoir si le noeud existe ou non, et s'il existe comment se situe la nouvelle valeur par rapport à lui. En fonction de sa position, on appelle à nouveau la même procédure en transmettant le coté gauche ou droit de l'arbre.
Le tour est joué !
Code : Tout sélectionner
; Création de la structure (qui est vide à ce moment)
Structure ARB
valeur.b
*gauche.ARB
*droite.ARB
EndStructure
; Procédure de création des arbres ou sous-arbres
Procedure arbre (*noeud.ARB,n.b)
If *noeud ; le noeud existe déjà
If n = *noeud\valeur
*noeud\valeur = n ; inutile mais bon je n'ai rien trouvé d'autres...
ElseIf n < *noeud\valeur
*noeud\gauche=arbre(*noeud\gauche,n) ; on transmet la partie gauche à traiter
Else
*noeud\droite=arbre(*noeud\droite,n) ; on transmet la partie droite à traiter
EndIf
Else
*noeud = AllocateMemory(SizeOf(ARB)) ; tentative de création du noeud par allocation de la mémoire
If *noeud ; le noeud a été créé avec succès
*noeud\valeur = n
*noeud\gauche = #Null
*noeud\droite = #Null
Else
MessageRequester("Erreur","Impossible d'allouer de la mémoire !",0)
End
EndIf
EndIf
ProcedureReturn *noeud
EndProcedure
; Procédure d'affichage par ordre croissant des valeurs
; les valeurs inférieurs étant à gauche, je commence par la gauche puis je continue par la droite
Procedure affiche_croissant(*noeud.ARB)
If *noeud\gauche <> #Null : affiche_croissant(*noeud\gauche) : EndIf
Debug *noeud\valeur
If *noeud\droite <> #Null : affiche_croissant(*noeud\droite): EndIf
EndProcedure
; traitement
; population de l'arbre
*arbre=arbre(*arbre,4)
*arbre=arbre(*arbre,3)
*arbre=arbre(*arbre,1)
*arbre=arbre(*arbre,6)
*arbre=arbre(*arbre,7)
*arbre=arbre(*arbre,9)
*arbre=arbre(*arbre,6)
; affichage par ordre croissant des valeurs de l'arbre
affiche_croissant(*arbre)
merci de nous en faire profiter, joli boulot !
remarques.