400
A Rappels algorithmiques
– La fonction nouveau crée et renvoie un nœud d’un arbre ; suivant le contexte, ce
sera un arbre binaire ou un arbre-B.
– Lorsque nous utilisons des tableaux, le premier indice commence soit à 0, soit
à 1 suivant l’algorithme concerné.
A.1 Arbres binaires
Nous rappelons d’abord l’implémentation récursive des arbres binaires, puis le
schéma général du parcours en profondeur, avec ses trois variantes, et celui du
parcours en largeur ; ces parcours sont de coût linéaire en la taille de l’arbre. Nous
terminons en présentant l’algorithme de rotation, qui nous servira pour les arbres
binaires de recherche randomisés, et s’applique bien sûr à tout arbre binaire.
A.1.1 Le type de données Arbre binaire
Struct Arbre
élément clé
Arbre gauche, droit
A.1.2 Parcours en profondeur
Procedure parcoursProfondeur(Arbre A)
// Précondition : A est un arbre.
// Postcondition : A n’a pas été modifié ; l’arbre est visité par un parcours en
profondeur en passant trois fois par chaque nœud.
// Utilise : parcoursProfondeur, premièreVisite,
deuxièmeVisite, troisièmeVisite
si A != None alors
premièreVisite(A)
parcoursProfondeurA.gauche
deuxièmeVisite(A)
parcoursProfondeurA.droit
troisièmeVisite(A)