Structures de données chaînées : les arbres

    

Il est possible de représenter un arbre donné par un tableau statique. Cependant, si l'on veut créer dynamiquement des arbres, leur ajouter ou leur supprimer des sommets, il est préférable de travailler sur le tas. L'idée est de reproduire en mémoire l'organisation d'un arbre (soit vide, soit formé d'une étiquette et de deux sous-arbres) en construisant un objet chaîné . L'implémentation de ces objets se fait à l'aide d'une structure auto-référencée (on peut dire aussi récursive , le nom de la structure, struct tree_cell apparaissant à la fois en-tête et à l'intérieur de sa définition, de façon analogue à une fonction récursive) :  

typedef struct tree_cell {
  data label;
  struct tree_cell *left;
  struct tree_cell *right;
} tree_cell;

  

Figure: La structure tree_cell

Un arbre sera désigné à l'aide d'un pointeur de tree_cell. Un arbre vide est représenté par un pointeur nul  (NULL). La construction d'une cellule se fait par allocation dynamique :

tree_cell *tree_cons(data x, tree_cell *l, tree_cell *r) {
  tree_cell *t = malloc(sizeof(tree_cell));

  t->label = x;
  t->left = l;
  t->right = r;
  return t;
}

 

Cette fonction est un constructeur d'objet . Alors que les objets statiques ou automatiques sont construits lors de la définition du nom qui les désigne, les objets dynamiques doivent être construits par un appel de fonction. La forme générale d'un constructeur d'objet dynamique de type T est :

T *constructeur( ... ) {
  T *t = malloc(sizeof(T));
  ...
  return t;
}

Un constructeur d'objet peut alors être utilisé lors de la définition d'un objet :

  T *t = constructeur( ... );

L'arbre de la figure 22 peut ainsi être construit par (le type cell_data étant int) :

  tree_cell *c = tree_cons(1, 
                      tree_cons(2, 
                           tree_cons(4, 
                                NULL, 
                                tree_cons(8,NULL,NULL)),
                           tree_cons(5,NULL,NULL))
                      tree_cons(3,
                           tree_cons(6,
                                tree_cons(9,NULL,NULL),
                                tree_cons(10,
                                     tree_cons(12,NULL,NULL),
                                     tree_cons(13,NULL,NULL))),
                           tree_cons(7,
                                tree_cons(11,NULL,NULL),
                                NULL)))

Un arbre vide est testé par :

int is_empty_cell(tree_cell *p) {
  return (p == NULL);
}

Au lieu de << return (p == NULL); >>, on peut écrire de façon plus concise, mais moins claire, << return (!p); >>. Il est indispensable de tester si un arbre est vide avant d'accéder à ses sous-arbres.