:: Enseignements :: Licence :: L2 :: 2008-2009 :: Structures de données ::

Arbres binaires

Définir le type nécessaire à la gestion d'un arbre binaire dont les valeurs stockées dans les sommets sont des entiers. On rappelle que leur implantation peut être illustrée par le schéma ci-dessous.

Écrire la fonction d'allocation d'un arbre binaire construction_ab qui prend en argument un entier (valeur stockée à la racine) et ses sous-arbres gauches et droit.
Écrire la fonction d'allocation d'une feuille d'un arbre binaire construction_feuille qui prend en argument un entier (valeur stockée à la racine).
Écrire une fonction destruction_ab réalisant la désallocation d'un arbre binaire.
Écrire les deux fonctions inserer_ab_gauche et inserer_ab_droit qui permettent d'insérer un sous-arbre gauche et droit, respectivement, à la racine de l'arbre binaire passé en arguemnt.
Écrire les deux fonctions detache_ab_gauche et detache_ab_droit qui retourne le sous-arbre gauche ou droit de la racine d'un arbre binaire passé en argument. Au retour de chacune de deux fonctions, le pointeur sur le sous-arbre gauche (ou droit) de la racine est NULL.
Écrire une fonction compte_sommets qui retourne le nombre de sommets dans un arbre binaire passé en argument.
Écrire une fonction compte_feuilles qui retourne le nombre de feuilles dans un arbre binaire passé en argument.
Écrire une fonction hauteur qui retourne la hauteur d'un arbre binaire passé en argument.
Écrire une fonction affichage qui affiche un arbre binaire passé en argument sous la forme (valeur, GAUCHE, DROIT), où valeur est l'entier stocké dans le sommet racine et GAUCHE (resp. DROIT) est l'affichage du sous-arbre gauche (resp. droit).