Taille, hauteur et feuilles d'un arbre binaire

Diviser pour régner · niveau 1 (application)

Énoncé

Avec la classe AB du cours, écrire trois fonctions récursives :

int taille(AB a), le nombre de valeurs de $a$ ;
int h(AB a), sa hauteur, avec la convention $h (()) = - 1$ ;
int feuilles(AB a), son nombre de feuilles.

Donner leur complexité. Tester sur $a = (1 (2 () ()) (1 () ()))$ .

Corrigé

Chaque fonction applique la même décomposition : un arbre vide, ou une racine et deux sous-arbres.


static int taille(AB a) {
    if (vide(a)) return 0;
    return 1 + taille(sag(a)) + taille(sad(a));
}
static int h(AB a) {
    if (vide(a)) return -1;
    return 1 + Math.max(h(sag(a)), h(sad(a)));
}
static int feuilles(AB a) {
    if (vide(a)) return 0;
    if (vide(sag(a)) && vide(sad(a))) return 1;   // a est une feuille
    return feuilles(sag(a)) + feuilles(sad(a));
}


a : taille 3, h 1, feuilles 2
b : taille 9, h 3, feuilles 5
() : taille 0, h -1, feuilles 0

( $b$ est l'arbre de racine $4$ du cours.) Chaque nœud donne lieu à un appel, et chaque arbre vide aussi ; un arbre de $n$ valeurs a $n + 1$ sous-arbres vides. Le corps de chaque fonction est en temps constant : $Θ (n)$ .