Structures de données chaînées

   

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. On va les implémenter à l'aide de la structure auto-référencée suivante :

struct tree_cell {
  cell_data label;
  struct tree_cell *left;
  struct tree_cell *right;
};

  
Figure: La structure tree_cell

En utilisant une abréviation de type, il est plus commode d'écrire :

typedef struct tree_cell {
  cell_data label;
  struct tree_cell *left, *right;
} 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 *cons(cell_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. L'arbre de la figure peut être construit par :

  tree_cell *c = cons(1, 
                      cons(2, 
                           cons(4, 
                                NULL, 
                                cons(8,NULL,NULL)),
                           cons(5,NULL,NULL))
                      cons(3,
                           cons(6,
                                cons(9,NULL,NULL),
                                cons(10,
                                     cons(12,NULL,NULL),
                                     cons(13,NULL,NULL))),
                           cons(7,
                                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); >>.