Implémenter la structure de données d'arbre binaire en C++

En C++, un arbre binaire peut être représenté par un nœud struct contenant une valeur et deux liens vers ses enfants. L’exemple ci-dessous construit un petit arbre, compte ses nœuds, mesure sa hauteur en arêtes et affiche ses valeurs selon un parcours infixe.

Représenter un arbre binaire avec une structure de nœud

Un nœud d’arbre binaire possède au plus deux enfants, généralement appelés left et right. Un struct est un type de classe dont les membres sont publics par défaut, ce qui le rend pratique pour cette petite structure de données. Chaque nœud stocke un entier et possède ses nœuds enfants au moyen de std::unique_ptr ; un pointeur nul indique qu’un lien vers un enfant est absent. Cela ne signifie pas à lui seul que le nœud est une feuille : une feuille est un nœud dont les deux liens vers ses enfants sont nuls.

Un arbre binaire strict possède, à chaque nœud, soit zéro, soit deux enfants. Un arbre binaire parfait est strict et toutes ses feuilles se trouvent à la même profondeur. L’arbre construit ci-dessous est strict, mais pas complet : son dernier niveau comporte un emplacement vide avant des nœuds situés plus à droite. Ces termes décrivent des formes différentes et ne sont pas interchangeables.

Construire un petit arbre binaire

Le programme crée cette forme déterministe, avec des valeurs choisies pour faciliter le suivi du parcours : 8 (left: 3, right: 10 (left: 9, right: 14)).

std::make_unique crée chaque nœud et renvoie un pointeur propriétaire. Déplacer un pointeur dans un lien vers un enfant transfère la propriété : la racine possède donc l’arbre entier, et ses nœuds sont automatiquement libérés lorsque la racine sort de portée. Cela évite le nettoyage manuel nécessaire avec des allocations brutes utilisant new.

Exécutez cet exemple. Les libellés affichés par le programme, notamment « size », « height » et « inorder », restent en anglais dans le code inchangé.

#include <iostream>
#include <memory>

struct BinTreeNode {
    int data;
    std::unique_ptr<BinTreeNode> left;
    std::unique_ptr<BinTreeNode> right;

    explicit BinTreeNode(int value) : data(value) {}
};

int treeSize(const BinTreeNode* node) {
    if (node == nullptr) {
        return 0;
    }
    return 1 + treeSize(node->left.get()) + treeSize(node->right.get());
}

int treeHeight(const BinTreeNode* node) {
    if (node == nullptr) {
        return -1;
    }
    const int leftHeight = treeHeight(node->left.get());
    const int rightHeight = treeHeight(node->right.get());
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

void printData(const BinTreeNode* node) {
    if (node == nullptr) {
        return;
    }
    printData(node->left.get());
    std::cout << node->data << ' ';
    printData(node->right.get());
}

int main() {
    auto root = std::make_unique<BinTreeNode>(8);
    root->left = std::make_unique<BinTreeNode>(3);
    root->right = std::make_unique<BinTreeNode>(10);
    root->right->left = std::make_unique<BinTreeNode>(9);
    root->right->right = std::make_unique<BinTreeNode>(14);

    std::cout << "size = " << treeSize(root.get()) << '\n';
    std::cout << "height = " << treeHeight(root.get()) << '\n';
    std::cout << "inorder = ";
    printData(root.get());
    std::cout << '\n';
}

Les fonctions reçoivent un pointeur vers un nœud sans en prendre la propriété. En les appelant avec root.get(), elles peuvent accéder à l’arbre tandis que le unique_ptr propriétaire reste responsable de sa durée de vie. Les mêmes définitions récursives fonctionnent quelle que soit la forme de l’arbre.

Compter les nœuds et calculer la hauteur de l’arbre

treeSize renvoie zéro pour un sous-arbre absent. Sinon, la fonction compte le nœud courant et ajoute les tailles des deux sous-arbres enfants. treeHeight renvoie -1 pour un sous-arbre absent, puis ajoute un à la plus grande hauteur des deux sous-arbres. Avec cette convention, la hauteur correspond au nombre d’arêtes sur le plus long chemin entre la racine et une feuille : une feuille a une hauteur de 0, et l’arbre ci-dessus a une hauteur de 2. Certaines définitions comptent plutôt les nœuds, auquel cas une feuille a une hauteur de 1 ; choisissez une convention et appliquez-la de façon cohérente.

Afficher les nœuds avec un parcours infixe

printData parcourt le sous-arbre gauche, affiche la valeur courante, puis parcourt le sous-arbre droit. C’est un parcours infixe ; dans un arbre binaire de recherche, il affiche les valeurs dans l’ordre trié, tandis que dans un arbre binaire général, il respecte simplement cet ordre de parcours. Consultez le guide du parcours infixe pour en savoir plus.

Pour suivre la récursion, observez la fonction à chaque nœud : elle descend d’abord vers la gauche jusqu’à ce qu’il n’y ait plus d’enfant, affiche la valeur en remontant vers le parent, puis traite le sous-arbre droit. Les valeurs de l’exemple apparaissent donc dans l’ordre 3 8 9 10 14. L’arbre compte cinq nœuds et sa hauteur, mesurée en arêtes, est de deux. Le programme est autonome ; vous pouvez adapter le type des valeurs stockées dans les nœuds ou ajouter des opérations, tout en gardant à l’esprit la propriété des nœuds et la convention de hauteur choisie.