TP9

Définitions sur les graphes

Un graphe fini G = (V,E) est défini par l’ensemble fini V ={v_1, v_2, . . . , v_n} dont les éléments sont appelés sommets (Vertices en anglais), et par l’ensemble fini E={e_1, e_2, . . . , e_m} dont les éléments sont appelés arêtes (Edges en anglais).

Une arête e de l’ensemble E est définie par une paire non ordonnée de sommets, appelés les extrémités de e. Si l’arête e relie les sommets a et b, on dira que ces sommets sont adjacents.

On appelle ordre d’un graphe le nombre de sommets n de ce graphe. On appelle degré d'un sommet le nombre de sommets qui lui sont adjacents.

Un graphe est connexe s’il est possible, à partir de n’importe quel sommet, de rejoindre tous les autres en suivant les arêtes. Un graphe non connexe se décompose en composantes connexes. Sur le graphe ci-dessus, les composantes connexes sont {1,2,3,4} et {5,6}.

On appelle arbre tout graphe connexe sans cycle. Une feuille est un sommet de degré 1 dans un arbre. Les autres sommets sont appelés des noeuds.

On appelle arbre binaire un arbre dans lequel chaque sommet a au plus deux voisins. Sur une représentation visuel d'un arbre binaire, tout noeuds a donc un sous arbre gauche et un sous arbre droit. Pour exemple, sur la figure ci-dessous, le sous-arbre gauche du noeud 1 est en rouge et son sous arbre droit est en vert.

Un arbre binaire de recherche est un arbre dans lequel on associe une valeur numérique à chaque noeud, de telle sorte que si on considère un noeuds de l'arbre, toutes les valeurs qui sont dans son sous arbre gauche lui sont inférieures et celles de sont sous arbre droit lui sont supérieures. On définira arbitrairement un noeuds à l'origine de l'arbre qu'on appelera la racine.

Sur l'exemple ci-dessus, la racine est a une valeur de 8, et on voit que quelque soit le noeuds qu'on considère, toutes les valeurs du sous-arbre gauche y sont inférieures (et réciproquement pour le sous arbre droit).

Représentation des arbres

Pour représenter un arbre binaire de recherche d'un point de vue algorithmique, on utilisera une structure contenant trois champs :

  • - sg : une structure du même type contenant le sous arbre gauche
  • - val : la valeur de la racine de cet arbre
  • - sd : une structure du même type contenant le sous arbre droit

Par exemple, si on représente grossièrement une structure par un ensmble de valeur entre crochet, l'arbre binaire de recherche ci-dessus sera représenté par :
[[[Null,1,Null],3,[[Null,4,Null],6,[Null,7,Null]],8,[Null,10,[[Null,13,Null],14,Null]]

Travail demandé

  1. Donnez le code de la structure struct_tree permettant de définir un arbre. Utilisez un alias de type pour définir le type tree.
  2. Écrire la fonction void init_tree(tree** t) permettant d'initialiser une structure d'arbre.
  3. Programmer une fonction bool is_leaf(tree* t) permettant de dire si un arbre est une feuille ou non.
  4. Donnez le code de la fonction récursive void insert_tree(tree** t, float v) qui insère la valeur v dans l'arbre t.
  5. Définir la fonction récursive int nb_node(tree* t) donnant le nombre de nœud d'un ABR.
  6. Définir la fonction récursive int height_tree(tree* t) donnant la hauteur d'un ABR.
  7. Écrire la fonction récursive void print_tree(tree* t) qui permet d'afficher les valeurs contenue dans un arbre par ordre croissant.
  8. Donnez le code de la fonction récursive bool assert_tree(tree* t) permettant de vérifier qu'un arbre supposé binaire est effectivement organisé comme un ABR.
  9. Programmer la fonction récursive float max_tree(tree* t) qui renvoie la plus grande valeur contenue dans un arbre.
  10. Faire de même pour la fonction float min_tree(tree* t).
  11. Écrire la fonction récursive bool search_tree(tree* t, float v) qui renvoie un booléen indiquant si la valeur v se trouve dans l'arbre t.
  12. Programmer la fonction récursive void delete_val_in_tree(tree** t, flaot v) permettant de supprimer la valeur v de l'arbre t.
  13. Programmer la fonction récursive void delete_tree(tree* t) permettant de supprimer complètement un arbre. On ne réutilisera pas la fonction précédente.

Correction : tp9.c.