Les arbres (binaires) seront définis par une classe : un arbre peut être l’arbre vide (null) ou bien une valeur (noeud), un sous-arbre gauche et un sous-arbre droit.

class Arbre{
    public int noeud;
    public Arbre gauche;
    public Arbre droit;

    public Arbre(int noeud, Arbre gauche, Arbre droit) {
        this.noeud  = noeud;
        this.gauche = gauche;
        this.droit  = droit;
    }
}

On peut alors créer et manipuler ces arbres :

Arbre a = new Arbre(4,
            new Arbre(2,
                new Arbre(1, null, null),
                new Arbre(3, null, null)
        ),
            new Arbre(6,
                null,
                new Arbre(7, null, null)
        )
    );

// On peut tester si un arbre est vide 
System.out.println(a == null);

// On peut accéder à la valeur, et à chaque sous-arbre
System.out.println(a.noeud);
if (a.gauche == null) {
    System.out.println("OK");
}

Exercices

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

      4
     / \
    2   6
   / \   \
  1   3   7

1. Calcul de la taille d’un arbre (nombre de nœuds dans l’arbre. Sur l’exemple a ci-dessus, la taille est 6).
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 a, la profondeur est 3.
3. Recherche d’un élément dans un arbre : recherche. L’élément 5 n’est pas dans l’arbre a. 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 : 4 2 1 3 6 7
• Postfixe : 1 3 2 7 6 4
• Infixe : 1 2 3 4 6 7
• Largeur : 4 2 6 1 3 7

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. Parcours en profondeur préfixe : pprefix
10. Parcours en profondeur postfixe : ppostfix
11. Parcours en profondeur infixe : pinfix
12. Parcours en largeur : plargeur