Comment écrire une fonction récursive sur un arbre binaire ?
if (t == null) return valeurBase; puis en combinant les résultats sur t.left et t.rightÉcrire une fonction qui traite récursivement tous les nœuds d'un arbre binaire.
Écrire une fonction taille(ArbreBin t) qui retourne le nombre de nœuds dans un arbre binaire.
Écrire une fonction qui traite récursivement tous les nœuds d'un arbre binaire.
La récursion sur un arbre binaire suit la structure récursive de sa définition : cas de base = arbre vide (null), cas général = combiner la valeur du nœud courant avec les résultats des appels récursifs sur les deux sous-arbres.
t == null, l'arbre est vide — retourner immédiatement la valeur neutre pour l'opération considérée (0 pour une somme, true pour une propriété, etc.) : if (t == null) return valeurBase;.typeRetour gauche = fonction(t.left);.typeRetour droit = fonction(t.right);.t.value, gauche et droit pour produire et retourner le résultat final.Écrire une fonction taille(ArbreBin t) qui retourne le nombre de nœuds dans un arbre binaire.
t == null, l'arbre est vide — retourner immédiatement la valeur neutre pour l'opération considérée (0 pour une somme, true pour une propriété, etc.) : if (t == null) return valeurBase;.Un arbre vide contient 0 nœud : c'est le cas de base.
static int taille(ArbreBin t) {
if (t == null) return 0;
typeRetour gauche = fonction(t.left);.On calcule récursivement la taille du sous-arbre gauche :
int gauche = taille(t.left);
typeRetour droit = fonction(t.right);.On calcule récursivement la taille du sous-arbre droit :
int droit = taille(t.right);
t.value, gauche et droit pour produire et retourner le résultat final.La taille totale est la somme des deux sous-arbres plus 1 pour le nœud courant :
return 1 + gauche + droit;
}
// taille(new ArbreBin(1, new ArbreBin(3, null, null), new ArbreBin(5, null, null))) == 3
taille(t) retourne 0 si t == null, sinon 1 + taille(t.left) + taille(t.right).
Écrire une fonction somme(ArbreBin t) qui retourne la somme de toutes les valeurs d'un arbre binaire d'entiers.
Écrire une fonction hauteur(ArbreBin t) qui retourne la hauteur d'un arbre binaire (longueur du chemin le plus long de la racine à une feuille).
Crée ton compte pour accéder à la fiche et aux exercices