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

Il est possible de représenter un arbre donné par un tableau. 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 de cellule d'arbre (on peut dire aussi récursive, le nom de la structure, tree_cell apparaissant à la fois en-tête et à l'intérieur de sa définition, de façon analogue à une fonction récursive) :

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

Un arbre sera désigné à l'aide d'un << pointeur de tree_cell >>, type que l'on abrège en tree. Un arbre vide est représenté par un pointeur nul (NULL). Si t est un arbre, *t est une cellule dont les champs sont (*t).label, (*t).left et (*t).right,

En outre, le groupement << (*). >> est tellement usuel (et ce placement obligatoire des parenthèses tellement agaçant) qu'il existe une abréviation : on écrit t->label au lieu de (*t).label. On utilisera désormais cette écriture simplifiée. La construction d'une cellule se fait par allocation dynamique²⁵ :

tree tree_cons(const data& x, tree l, tree r) {
  tree t = new 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 = new T;
  // initialisation des champs de *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 20 peut ainsi être construit par (le type cell_data étant int) :

  tree 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 :

bool is_empty_tree(tree p) {
  return (p == NULL);
}