Arbres et graphes en C

Les arbres et les graphes sont des structures de données non linéaires utilisées pour représenter des données hiérarchiques et des réseaux.

Dans cette leçon, vous apprendrez :

• Comment sont structurés les arbres et les graphes.
• Comment implémenter un arbre binaire en C.
• Comment représenter des graphes à l’aide de listes et de matrices d’adjacence.

Qu’est-ce qu’un arbre ?

Un arbre est une structure de données hiérarchique composée de nœuds.

Termes clés :

• Racine - Le nœud situé au sommet.
• Parent et enfant - Des nœuds directement reliés.
• Feuille - Un nœud sans enfant.

Exemple : Node d’arbre binaire

En C, un Node d’arbre binaire est défini à l’aide d’un struct contenant des pointeurs vers l’enfant gauche et l’enfant droit.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *left, *right;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int main() {
    struct Node *root = createNode(10);
    return 0;
}

Parcours d’arbre binaire

Méthodes de parcours :

• Inorder (LNR) - Gauche, Node, droite.
• Preorder (NLR) - Node, gauche, droite.
• Postorder (LRN) - Gauche, droite, Node.

Exemple : parcours inorder

Ce programme effectue un parcours inorder d’un arbre binaire.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *left, *right;
};

void inorder(struct Node *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct Node *root = malloc(sizeof(struct Node));
    root->data = 10;
    root->left = NULL;
    root->right = NULL;
    inorder(root);
    return 0;
}

Qu’est-ce qu’un graphe ?

Un graphe est un ensemble de nœuds (sommets) reliés par des arêtes.

Les graphes peuvent être :

• Orientés - Les arêtes ont une direction.
• Non orientés - Les arêtes n’ont pas de direction.

Représentation des graphes

Les graphes peuvent être représentés à l’aide de :

• Matrice d’adjacence - Un tableau à deux dimensions représentant les connexions.
• Liste d’adjacence - Une liste dans laquelle chaque nœud pointe vers ses voisins.

Parcours de graphe

Méthodes de parcours courantes :

• Parcours en largeur (BFS) - Visite tous les voisins avant d’aller plus en profondeur.
• Parcours en profondeur (DFS) - Explore aussi profondément que possible avant de revenir en arrière.

Résumé

Dans cette leçon, vous avez appris :

• Comment les arbres et les graphes sont structurés.
• Comment effectuer des parcours d’arbre.
• Comment les graphes sont représentés et parcourus.

Cette section sur les structures de données en C est terminée !