Pedro Ribeiro — Systems Engineering Vault

4 min read

Graph View

title: Info
Ce document explique la traversée **post-order** d'un arbre binaire, une méthode où chaque nœud est traité **après** ses sous-arbres. La traversée suit l'ordre **gauche → droite → racine**, ce qui est particulièrement utile pour des opérations nécessitant un traitement des enfants avant leur parent, comme la suppression ou l'évaluation d'arbres d'expression.

🏆 Contexte et Objectif

La traversée post-order est utilisée pour explorer et traiter un arbre binaire dans l’ordre où chaque sous-arbre est traité avant la racine. Elle est utile pour :

  1. Évaluer des expressions mathématiques dans un arbre d’expression.
  2. Supprimer ou libérer un arbre récursivement.
  3. Résoudre des problèmes nécessitant un traitement bottom-up (de bas en haut).

🎨 Représentation Visuelle

Prenons l’arbre suivant :

          8
         / \
        3   10
       / \
      1   6

Étapes de la traversée post-order :

  1. Traverser récursivement le sous-arbre gauche.
  2. Traverser récursivement le sous-arbre droit.
  3. Visiter la racine.

Résultat attendu :

1, 6, 3, 10, 8

💻 Code Complet Ultra-Commenté

Fichier suggéré : 18-binary-tree-postorder.c

#include <stdlib.h> // malloc, free
#include <stdio.h>  // printf, perror
 
// Définition d’un nœud pour l'arbre binaire
typedef struct s_btree
{
    int             data;          // Donnée du nœud
    struct s_btree  *left;         // Pointeur vers l'enfant gauche
    struct s_btree  *right;        // Pointeur vers l'enfant droit
}               t_btree;
 
// Fonction pour créer un nouveau nœud
t_btree *create_node(int data)
{
    t_btree *node = malloc(sizeof(t_btree));
    if (!node)
    {
        perror("Erreur d’allocation mémoire pour le nœud");
        exit(EXIT_FAILURE);
    }
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}
 
// Fonction pour insérer une valeur dans un arbre binaire de recherche
t_btree *insert_node(t_btree *root, int data)
{
    if (root == NULL)
        return create_node(data);
 
    if (data < root->data)
        root->left = insert_node(root->left, data);
    else if (data > root->data)
        root->right = insert_node(root->right, data);
 
    return root;
}
 
// Fonction de traversée post-order (gauche → droite → racine)
void postorder_traversal(t_btree *root)
{
    if (root == NULL)
        return;
 
    postorder_traversal(root->left);  // Traversée du sous-arbre gauche
    postorder_traversal(root->right); // Traversée du sous-arbre droit
    printf("%d ", root->data);        // Traiter la racine
}
 
// Fonction pour libérer la mémoire de l’arbre
void free_tree(t_btree *root)
{
    if (root == NULL)
        return;
 
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}
 
// Fonction main pour démonstration
int main(void)
{
    t_btree *root = NULL;
 
    // Insertion des valeurs dans l'arbre
    root = insert_node(root, 8);
    root = insert_node(root, 3);
    root = insert_node(root, 10);
    root = insert_node(root, 1);
    root = insert_node(root, 6);
 
    // Traversée post-order de l'arbre
    printf("Arbre binaire (traversée post-order) : ");
    postorder_traversal(root);
    printf("\n");
 
    // Libération de la mémoire
    free_tree(root);
 
    return 0;
}

🔎 Analyse Ligne par Ligne et Concepts Clés

1. Fonction postorder_traversal

void postorder_traversal(t_btree *root)
{
    if (root == NULL)
        return;
 
    postorder_traversal(root->left);  // Traversée du sous-arbre gauche
    postorder_traversal(root->right); // Traversée du sous-arbre droit
    printf("%d ", root->data);        // Traiter la racine
}
  • Base Case: Si root == NULL, on ne fait rien (fin de la branche).
  • Recursive Traversal:
    • Sous-arbre gauche: Explore tous les enfants du côté gauche.
    • Sous-arbre droit: Explore tous les enfants du côté droit.
    • Racine: Traite le nœud courant après avoir exploré ses enfants.

2. Fonction main

  1. Construction de l’arbre: Les valeurs {8, 3, 10, 1, 6} sont insérées en respectant les règles du BST.
  2. Traversée et Affichage: La fonction postorder_traversal parcourt l’arbre en suivant l’ordre gauche → droite → racine.

🧭 Complexité

OpérationComplexitéExplication
Traversée post-orderO(n)Chaque nœud est visité une seule fois.
Construction de l’arbreO(h) pour chaque insertionh est la hauteur de l’arbre.
  • Cas optimal (arbre équilibré): La hauteur h est logarithmique (h = log(n)), donc l’insertion est efficace.
  • Cas dégénéré (arbre déséquilibré): Si l’arbre devient une liste chaînée (h = n), l’insertion et la traversée deviennent linéaires.

🧠 Bonnes Pratiques et Conseils

  1. Cas Limites :

    • Si l’arbre est vide (root == NULL), la traversée ne produit aucune sortie.
    • Toujours vérifier si malloc réussit lors de la création de nœuds.

  2. Extensibilité :

    • Ajouter d’autres traversées (in-order, pre-order, level-order) pour répondre à différents besoins.

  3. Applications Pratiques :

    • Évaluation d’arbres d’expression pour résoudre des équations.
    • Suppression d’un arbre entier, car chaque nœud est visité après ses enfants.

✨ Conclusion

La traversée post-order est essentielle pour des tâches nécessitant un traitement des enfants avant leur parent, comme la libération de mémoire ou l’évaluation d’expressions. Son implémentation récursive est simple et respecte les conventions de la 42 School, tout en offrant une base robuste pour des manipulations avancées des arbres binaires.

Bravo, vous avez maîtrisé la traversée post-order ! 🌳

Graph View

Backlinks