Les arbres (binaires) seront définis par un nouveau type : un arbre peut être l’arbre vide (Vide) ou bien une valeur (Noeud), un sous-arbre gauche et un sous-arbre droit. La valeur pourra être de n’importe quel type a.

data Arbre a = Vide | Noeud (Arbre a) a (Arbre a)

On peut alors créer et manipuler ces arbres :

bonsai = Noeud
            (Noeud 
                (Noeud Vide 8 Vide)
                3
                (Noeud
                    (Noeud Vide 1 Vide)
                    12
                    Vide))
            7
            (Noeud
                Vide
                4
                (Noeud Vide 2 Vide))

Exercices

L’exemple bonsai ci-dessus se dessine comme suit :

      7
     / \
    3   4
   / \   \
  8  12   2
    /
   1

1. Calcul de la taille d’un arbre (nombre de nœuds dans l’arbre. Sur l’exemple a ci-dessus, la taille est 7).
2. Calcul de la profondeur d’un arbre. Il s’agit de la hauteur, la distance entre la racine et la feuille la plus éloignée. On conviendra que la profondeur de l’arbre vide est 0, et celle d’un arbre à 1 seul nœud est 1. Sur l’exemple bonsai, la profondeur est 4.
3. Recherche d’un élément dans un arbre : recherche. L’élément 5 n’est pas dans l’arbre bonsai. Mais l’élément 2 y est. L’arbre n’est pas supposé trié, donc 5 peut aussi bien être dans le sous-arbre gauche ou dans le sous-arbre droit.
4. Calcul de la complexité de ces fonctions.

On appelle arbre binaire de recherche (abr) un arbre trié suivant la convention que tous les nœuds du sous arbre gauche sont inférieurs au nœud racine et tous les éléments du sous arbre droit sont stritement supérieurs au nœud racine, ceci récursivement.

5. Test qu’un arbre est un abr : estABR
6. Recherche dans un arbre binaire de recherche : rechercheABR
7. Insertion dans un arbre binaire de recherche : insertionABR
8. Calcul de la complexité de ces fonctions

Les parcours d’arbre consistent à explorer et afficher tous les nœuds de l’arbre suivant un ordre prédéfini. On peut

• soit afficher d’abord la racine, puis parcourir le sous arbre gauche puis parcourir le sous arbre droit (parcours préfixe)
• soit parcourir le sous arbre gauche, puis le sous arbre droit puis enfin afficher la racine (parcours postfixe)
• soit parcourir le sous arbre gauche, puis afficher la racine, puis parcourir le sous arbre droit (parcours infixe)
• Soit afficher les nœuds par étage, de gauche à droite (d’abord la racine, puis la racine du sous arbre gauche, puis la racine du sous arbre droit, puis la racine du sous arbre gauche du sous arbre gauche, …).

Sur l’exemple a ci-dessus, les différents parcours donnent les retours suivants :

• Préfixe : 7 3 8 12 1 4 2
• Postfixe : 8 1 12 3 2 4 7
• Infixe : 8 3 1 12 7 4 2
• Largeur : 7 3 4 8 12 2 1

Si l’arbre est l’arbre d’évaluation d’une expression arithmétique, son parcours infixe donne l’expression sous forme naturelle ; le parcours préfixe donne la sous forme fonctionnelle ; le parcours postfixe la donne en notation polonaise inverse.

Parcours infixe : (3+2)*(4*3)

Parcours préfixe : mult(add(3, 2), mult(4, 3))

Parcours postfixe : 3 2 + 4 3 * *

9. Écrire une fonction réalisant le parcours en profondeur préfixe : pprefix
10. Écrire une fonction réalisant le parcours en profondeur postfixe : ppostfix
11. Écrire une fonction réalisant le parcours en profondeur infixe : pinfix
12. Écrire une fonction réalisant le parcours en largeur : plargeur