Représentation des Arbres Binaires

Représentation par Nœuds Liés (Pointeurs)

La méthode la plus courante pour représenter un arbre binaire est d'utiliser des nœuds liés. Chaque nœud contient les éléments suivants :

• Une valeur (l'information stockée dans le nœud).
• Un pointeur vers son enfant gauche (ou null s'il n'a pas d'enfant gauche).
• Un pointeur vers son enfant droit (ou null s'il n'a pas d'enfant droit).

En Python, cela pourrait être représenté par une classe :

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

En C++ :

struct Node {
    int value;
    Node* left;
    Node* right;
};

Pour créer l'arbre de l'exemple précédent :

root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.left.right = Node('E')

Représentation par Tableau (Implicite)

Il est également possible de représenter un arbre binaire en utilisant un tableau, bien que cette méthode soit moins courante et plus adaptée aux arbres binaires complets.

L'idée est de stocker les nœuds de l'arbre dans un tableau, en utilisant les indices pour représenter les relations parent-enfant. La racine est à l'indice 1 (ou 0, selon la convention), et les enfants d'un nœud à l'indice i sont situés aux indices 2*i (enfant gauche) et 2*i + 1 (enfant droit).

Exemple : Reprenons l'arbre précédent :

        A
       / \
      B   C
     / \
    D   E
  

La représentation en tableau serait :

index: 0  1  2  3  4  5  6
value:   A  B  C  D  E  -  -

Les enfants de 'B' (indice 2) sont 'D' (indice 4 = 2*2) et 'E' (indice 5 = 2*2 + 1).

Avantages : Simple à implémenter, efficace en espace pour les arbres binaires complets.

Inconvénients : Gaspillage d'espace pour les arbres non complets, complexité pour les opérations de modification de l'arbre.

Ce qu'il faut retenir

• Les arbres binaires peuvent être représentés en utilisant des nœuds liés (pointeurs) ou un tableau.
• La représentation par nœuds liés est la plus courante et flexible.
• La représentation par tableau est plus adaptée aux arbres binaires complets, mais peut gaspiller de l'espace.