Structures de Données, Algorithmes 2

TP n° 1

(Arbres I)

Notions abordées : arbres binaires, spécification algébriques, arbres quadratiques.

Implémentation des arbres binaires en C.

1. Définir le type arbre_binaire.
2. Définir les constructeurs :  Vide() et Enrac(ag,r,ad).
3. Définir les sélecteurs : arbre_gauche(a), arbre_droit(a), racine(a).
4. Définir l'observateur : vide(a).

Définition d'autres opérations classiques.

1. Définir une fonction hauteur(a) qui retourne la hauteur d'un arbre.
2. Définir une fonction taille(a) qui retourne le nombre de nœuds internes.
3. Définir une fonction nb_feuilles(a) qui retourne le nombre de feuilles.
4. Définir une fonction parcours_prefixe(a) qui affiche les éléments dans l'ordre du parcours en profondeur d'abord préfixe.
5. Même question avec le parcours infixe.
6. Même question avec le parcours postfixe.

Implémentation des arbres quadratiques en C.

1. Définir le type arbre_quad.
   
2. Définir les constructeurs :  Feuille(f) et Enrac(so,no,ne,se) (so=sud ouest, no=nord ouest, ne=nord est, se=sud est).
3. Définir les sélecteurs : arbre_so(a), arbre_no(a), arbre_ne(a), arbre_se(a), etiquette(a).
4. Définir l'observateur : feuille(a) qui teste si un arbre quadratique est une feuille.
   

Opérations sur les images carrées en noir et blanc.

    On représente les images carrées en noir et blanc par un arbre quadratique dont les éléments sont des booléens (blanc = vrai, noir = faux).

1. Définir une fonction image_egal(i1,i2) qui teste si deux images sont identiques.
2. Opérations ensemblistes -- Définir les fonctions union(i1,i2) et intersection(i1,i2) qui retournent l'image obtenue en superposant deux images et en mettant du noir respectivement là où il y a du noir dans l'un des deux images et là où il y a du noir dans les deux images.
3. Définir une fonction est_noir(i,x,y) qui teste si dans l'image i, le pixel de coordonnées (x,y) est noir. (Le pixel au coin au sud-ouest a pour coordonnées (0,0) et le pixel au coin au nord-est a pour coordonnées (n-1,n-1) où n x n est la taille de l'image en pixels). (On suppose que l'image est telle que le plus petit carré monochrome qui la compose est de taille supérieure ou égale à 1 pixel).
4. Définir une fonction noircir(i,x,y) qui modifie une image en noircissant le pixel de coordonnées (x,y).