Définition d'un arbre binaire

Un arbre binaire est une structure de données composée de nœuds (n > 0). Il peut être soit un arbre vide (racine nulle), soit un arbre non vide. Pour un arbre non vide, il existe un nœud unique appelé racine. Tous les autres nœuds forment deux ensembles disjoints, T1 et T2, qui sont respecitvement les sous-arbres gauche et droit de la racine, et qui sont eux-mêmes des arbres binaires.

Différence avec un arbre général

Chaque nœud d'un arbre binaire possède au maximum deux sous-arbres. Ces sous-arbres sont ordonnés : le sous-arbre gauche et le sous-arbre droit sont distincts et ne peuvent pas être intervertis.

Propriétés fondamentales

Au niveau i (i ≥ 1), il y a au maximum 2i-1 nœuds. La profondeur k d'un arbre binaire permet au maximum 2k - 1 nœuds. Pour tout arbre binaire, si le nombre de nœuds terminaux (feuilles) est n0 et le nombre de nœuds avec deux enfants est n2, alors n0 = n2 + 1.

Stockage chaîné

L'implémentation la plus courante pour un arbre binaire est la liste chaînée (pointeurs). Chaque nœud contient une donnée et des pointeurs vers ses enfants gauche et droit.

Exemples d'opérations en C++

Définition du nœud

struct NoeudArbre {
    char donnee;
    NoeudArbre* gauche;
    NoeudArbre* droit;
};
typedef NoeudArbre* ArbreBinaire;

Construction de l'arbre (parcours pré-ordre)

void construireArbreBinaire(ArbreBinaire& racine) {
    char valeur;
    std::cin >> valeur;
    if (valeur == '#') {
        racine = nullptr; // Marqueur de fin ou arbre vide
    } else {
        racine = new NoeudArbre;
        racine->donnee = valeur;
        construireArbreBinaire(racine->gauche);
        construireArbreBinaire(racine->droit);
    }
}

Parcours infixe récursif

void parcoursInfixe(ArbreBinaire abr) {
    if (abr != nullptr) {
        parcoursInfixe(abr->gauche);
        // Traitement du nœud courant (ex: affichage)
        std::cout << abr->donnee << " ";
        parcoursInfixe(abr->droit);
    }
}

Compter les nœuds

int compterNoeuds(ArbreBinaire abr) {
    if (abr == nullptr) {
        return 0;
    }
    return 1 + compterNoeuds(abr->gauche) + compterNoeuds(abr->droit);
}

Calculer la profonderu

int calculerProfondeur(ArbreBinaire abr) {
    if (abr == nullptr) {
        return 0;
    }
    int profGauche = calculerProfondeur(abr->gauche);
    int profDroite = calculerProfondeur(abr->droit);
    return 1 + std::max(profGauche, profDroite);
}

Copie de l'arbre

void copierArbre(const ArbreBinaire source, ArbreBinaire& dest) {
    if (source == nullptr) {
        dest = nullptr;
    } else {
        dest = new NoeudArbre;
        dest->donnee = source->donnee;
        copierArbre(source->gauche, dest->gauche);
        copierArbre(source->droit, dest->droit);
    }
}

Cette fonction récursive copie l'intégralité de la structure de l'arbre source dans un nouvel arbre destination. Il est crucial de gérer le cas où le nœud source est nul pour initialiser corectement le nœud destination correspondant.