My IT Utilities

Parcours d'arbre binaire

Générez un arbre binaire de recherche et parcourez pas à pas les parcours préfixe, infixe ou postfixe avec une fonction C++ récursive.

Tout est simulé dans ce navigateur ; rien n'est envoyé à un serveur.

Visite le nœud, puis le sous-arbre gauche, puis le droit.

La fonction est appelée avec le nœud 60

La fonction est appelée avec le nœud 60

Arbre binaire

60458568215532

Sortie

Aucun nœud n'a encore été visité

  • Non visité
  • En cours
  • Dans la pile
  • Visité

Étape 1 / 44

Code

#include <iostream>
using namespace std;
class Node { // Un nœud contient sa valeur et des pointeurs vers ses deux enfants
private: // Attributs privés : seules les méthodes y touchent
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
void preorder(Node* node) { // Parcourt le sous-arbre dont la racine est node
if (node == nullptr) return; // Cas de base : un sous-arbre vide n'a rien à visiter
cout << node->getValue() << " "; // Visite le nœud : traite sa valeur
preorder(node->getLeft()); // Parcourt le sous-arbre gauche
preorder(node->getRight()); // Parcourt le sous-arbre droit
} // Retourne à l'appelant
Node* insert(Node* root, int v) { // Insère v dans l'arbre de recherche et renvoie la racine
if (root == nullptr) return new Node(v); // Emplacement vide : le nouveau nœud va ici
if (v < root->getValue()) // Les valeurs plus petites vont à gauche et les plus grandes à droite
root->setLeft(insert(root->getLeft(), v));
else
root->setRight(insert(root->getRight(), v));
return root;
}
Node* buildTree() { // Construit l'arbre en insérant les valeurs une par une
int values[] = {60, 45, 85, 68, 21, 55, 32}; // Les valeurs de l'arbre affiché, dans l'ordre d'insertion
Node* root = nullptr;
for (int v : values) root = insert(root, v);
return root;
}
int main() {
Node* root = buildTree(); // L'arbre de l'animation, déjà construit
preorder(root); // Premier appel, depuis main
cout << endl; // Fin du parcours
return 0;
}

Cet outil génère un arbre binaire de recherche (ABR) avec des valeurs aléatoires et le parcourt pas à pas avec une fonction C++ récursive. Vous choisissez le parcours préfixe, infixe ou postfixe et voyez sur le même arbre quand chaque nœud est visité : avant ses enfants, entre eux ou après eux. Les nœuds sont colorés selon leur état (non visité, en cours, dans la pile ou visité), une bande de sortie montre les valeurs dans l'ordre de visite et le code surligne la ligne exécutée. Les appels avec nullptr sont aussi affichés, c'est le cas de base qui arrête la récursivité. La taille va de 3 à 15 nœuds. Tout est simulé dans votre navigateur.

Comment l'utiliser

  1. Choisissez le parcours : Préfixe, Infixe ou Postfixe.
  2. Ajustez la taille de l'arbre avec le curseur ou appuyez sur Générer un nouvel arbre ; l'animation revient à la première étape.
  3. Appuyez sur Lecture ou avancez avec les boutons d'étape précédente et suivante, et changez la vitesse si besoin.
  4. Observez les nœuds colorés, la bande de sortie avec les valeurs visitées et la ligne de code C++ surlignée.

Questions fréquentes

Qu'est-ce qu'un arbre binaire et qu'est-ce qu'un arbre binaire de recherche ?
Un arbre binaire est une structure où chaque nœud a au plus deux enfants, gauche et droit. Dans un arbre binaire de recherche (ABR), les valeurs du sous-arbre gauche sont aussi inférieures à celle du nœud et celles du sous-arbre droit supérieures.
Quelle différence entre préfixe, infixe et postfixe ?
Ce qui change, c'est le moment où le nœud est visité par rapport à ses enfants. En préfixe, le nœud est visité d'abord, puis les sous-arbres gauche et droit ; en infixe, le sous-arbre gauche, le nœud et le sous-arbre droit ; en postfixe, le sous-arbre gauche, le sous-arbre droit et le nœud en dernier. Le préfixe sert à copier un arbre, l'infixe à lire un ABR dans l'ordre et le postfixe à libérer ou évaluer un arbre, car les enfants sont traités avant leur parent.
Pourquoi le parcours infixe d'un ABR sort-il trié ?
Parce que dans un ABR, tout ce qui est à gauche d'un nœud est plus petit et tout ce qui est à droite plus grand. Visiter le sous-arbre gauche, puis le nœud, puis le sous-arbre droit produit les valeurs de la plus petite à la plus grande.
Comment implémenter un parcours récursif en C++ ?
Avec une fonction qui prend un pointeur vers un nœud. Si le pointeur vaut nullptr, elle retourne sans rien faire : c'est le cas de base. Sinon, elle visite le nœud et s'appelle avec l'enfant gauche et l'enfant droit, dans l'ordre que le parcours exige.

Outils associés