Les listes chaînées, piles et files sont des collections linéaires. Un arbre est une collection non linéaire. Un cas particulier important est l'arbre binaire de recherche (ABR), dans lequel les valeurs du sous-arbre gauche sont inférieures à la racine, et celles du sous-arbre droit lui sont supérieures.
Un ABR est un arbre binaire tel que pour tout nœud n : toutes les valeurs du sous-arbre gauche sont inférieures à la valeur de n, et toutes les valeurs du sous-arbre droit lui sont supérieures. Cette propriété est vérifiée récursivement pour chaque nœud.
Parcours d'arbre binaire
Le parcours d'un ABR exige que chaque nœud soit traité exactement une fois. Il existe trois types de parcours :
| Parcours | Ordre de traitement | Propriété |
|---|---|---|
| Infixe (in-order) | Gauche → Racine → Droite | Produit les valeurs en ordre croissant |
| Préfixe (pre-order) | Racine → Gauche → Droite | La racine est traitée en premier |
| Postfixe (post-order) | Gauche → Droite → Racine | La racine est traitée en dernier — utilisé pour la destruction |
Parcours infixe
Le traitement de la racine se situe entre les deux sous-arbres. Le parcours infixe d'un ABR produit les valeurs dans l'ordre croissant.
Parcours préfixe
La racine est traitée en premier, suivie de tous les nœuds du sous-arbre gauche, puis du droit.
Parcours postfixe
Le traitement de la racine vient après les deux sous-arbres. C'est le parcours utilisé pour détruire un ABR.
Mise en œuvre
Classe ABR
Les méthodes de la classe sont divisées en deux catégories : les méthodes privées (aide récursive) et les méthodes publiques (interface simplifiée pour l'utilisateur).
#ifndef ABR_H
#define ABR_H
#include <iostream>
using namespace std;
template <typename T>
struct Noeud {
T donnees;
Noeud <T>* gauche;
Noeud <T>* droit;
};
template <class T>
class ABR {
private:
Noeud <T>* racine;
int compteur;
Noeud <T>* CreerNoeud (const T& valeur);
void detruire (Noeud <T>* ptr);
void inserer (const T& valeur, Noeud <T>*& ptr);
void infixe (Noeud <T>* ptr) const;
void prefixe (Noeud <T>* ptr) const;
void postfixe (Noeud <T>* ptr) const;
Noeud <T>* successeur (Noeud <T>* ptr, Noeud <T>*& parent) const;
Noeud <T>* predecesseur (Noeud <T>* ptr, Noeud <T>*& parent) const;
void supprimer (Noeud <T>* ptr, Noeud <T>* parent);
Noeud <T>* recherche (const T& valeur, Noeud <T>* ptr, Noeud <T>*& parent) const;
public:
ABR ();
~ABR ();
void inserer (const T& valeur);
void detruire ();
void supprimer (const T& valeur);
Noeud <T>* recherche (const T& valeur) const;
void infixe () const;
void prefixe () const;
void postfixe () const;
int taille () const;
bool estVide () const;
};
#endifConstructeur et destructeur
// Constructeur
template <class T>
ABR <T>::ABR() : racine(0), compteur(0) {}
// Destructeur — appelle detruire (parcours postfixe)
template <class T>
ABR <T>::~ABR () { detruire(racine); }Détruire un ABR
La destruction utilise un parcours postfixe : on détruit d'abord le sous-arbre gauche, puis le droit, puis la racine.
template <class T>
void ABR <T>::detruire (Noeud <T>* ptr) {
if (!ptr) { return; }
detruire(ptr -> gauche); // détruire sous-arbre gauche
detruire(ptr -> droit); // détruire sous-arbre droit
delete ptr; // détruire la racine
}Insertion
L'insertion est récursive : si l'arbre est vide, on insère à la racine ; sinon on descend à gauche si la valeur est inférieure, à droite sinon.
template <class T>
void ABR <T>::inserer (const T& valeur, Noeud <T>*& ptr) {
if (!ptr) {
ptr = CreerNoeud(valeur); // arbre vide : insérer comme racine
return;
} else if (valeur < ptr -> donnees) {
inserer(valeur, ptr -> gauche); // insérer dans le sous-arbre gauche
} else {
inserer(valeur, ptr -> droit); // insérer dans le sous-arbre droit
}
}Rechercher un nœud
La recherche est également récursive. Elle retourne le nœud trouvé (avec son parent) ou NULL si absent.
template <class T>
Noeud <T>* ABR <T>::recherche (const T& valeur, Noeud <T>* ptr, Noeud <T>*& parent) const {
if (!ptr) return NULL;
else if (ptr->donnees == valeur) return ptr;
else if (valeur < ptr->donnees) { parent = ptr; return recherche(valeur, ptr->gauche, parent); }
else { parent = ptr; return recherche(valeur, ptr->droit, parent); }
}Supprimer un nœud
La suppression couvre trois cas selon le nombre d'enfants du nœud à supprimer :
Cas 1 — Le nœud n'a pas d'enfants
Le lien du parent est mis à NULL et le nœud est supprimé.
Cas 2 — Le nœud a un seul enfant
Le nœud est supprimé et son enfant est directement relié au parent.
Cas 3 — Le nœud a deux enfants
On remplace la valeur du nœud par celle de son successeur (valeur minimale du sous-arbre droit) ou de son prédécesseur (valeur maximale du sous-arbre gauche), puis on supprime ce successeur/prédécesseur.
template <class T>
void ABR <T>::supprimer (Noeud <T>* ptr, Noeud <T>* parent) {
if (ptr->gauche == 0 && ptr->droit == 0) { // Cas 1 : feuille
if (ptr != racine) {
if (parent->gauche == ptr) parent->gauche = NULL;
else parent->droit = NULL;
} else racine = NULL;
delete ptr;
} else if (ptr->gauche && ptr->droit) { // Cas 3 : deux enfants
Noeud <T>* pere = ptr;
Noeud <T>* succ = successeur(ptr->droit, pere);
int val = succ->donnees;
supprimer(succ, pere);
ptr->donnees = val;
} else { // Cas 2 : un enfant
Noeud <T>* enfant = (ptr->gauche) ? ptr->gauche : ptr->droit;
if (ptr != racine) {
if (ptr == parent->gauche) parent->gauche = enfant;
else parent->droit = enfant;
} else racine = enfant;
delete ptr;
}
}Parcours (implémentations récursives)
template <class T>
void ABR <T>::infixe (Noeud <T>* ptr) const {
if (!ptr) { return; }
infixe(ptr -> gauche);
cout << ptr -> donnees << '\t';
infixe(ptr -> droit);
}
template <class T>
void ABR <T>::prefixe (Noeud <T>* ptr) const {
if (!ptr) { return; }
cout << ptr -> donnees << '\t';
prefixe(ptr -> gauche);
prefixe(ptr -> droit);
}
template <class T>
void ABR <T>::postfixe (Noeud <T>* ptr) const {
if (!ptr) { return; }
postfixe(ptr -> gauche);
postfixe(ptr -> droit);
cout << ptr -> donnees << '\t';
}Toutes les méthodes récursives ci-dessus sont privées. Les méthodes publiques (inserer(valeur), infixe(), etc.) appellent simplement leurs homologues privés avec les bons paramètres, masquant la récursion à l'utilisateur.
Programme principal
#include "abr.cpp"
int main() {
ABR <int> arbre;
arbre.inserer(40); arbre.inserer(50); arbre.inserer(14);
arbre.inserer(16); arbre.inserer(5); arbre.inserer(3);
arbre.inserer(7); arbre.inserer(55); arbre.inserer(45);
cout << "Parcours infixe : \n"; arbre.infixe();
cout << "\nParcours postfixe : \n"; arbre.postfixe();
cout << "\nParcours prefixe : \n"; arbre.prefixe();
if (arbre.recherche(3) != 0) cout << "\nNoeud 3 : present";
if (arbre.recherche(60) == 0) cout << "\nNoeud 60 : absent";
arbre.supprimer(3);
cout << "\nInfixe apres suppression de 3 : \n"; arbre.infixe();
arbre.supprimer(40);
cout << "\nInfixe apres suppression de 40 : \n"; arbre.infixe();
return 0;
}Parcours infixe : 3 5 7 14 16 40 45 50 55 Parcours postfixe : 3 7 5 16 14 45 55 50 40 Parcours prefixe : 40 14 5 3 7 16 50 45 55 Noeud 3 : present Noeud 60 : absent Infixe apres suppression de 3 : 5 7 14 16 40 45 50 55 Infixe apres suppression de 40 : 5 7 14 16 45 50 55
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.