E.1 – Algorithmes sur les arbres binaires et sur les arbres binaires de recherche.

Calculer la taille et la hauteur d’un arbre binaire.

La taille et la hauteur d’un arbre binaire se déterminent de façon récursive.

La taille est le nombre total de nœuds d’un arbre binaire.

La hauteur et le nombre de nœuds par lesquels il faut passer pour aller de la racine (incluse) jusqu’à une feuille parmi celles qui sont les plus éloignées de la racine.

Calcul de la taille

Si l’arbre binaire est vide la taille est égale à ‘zéro’ (0).

Sinon taille(ab) = 1 + taille(sag) + taille(sad)

Exercice – Écrire une fonction récursive ‘taille’ qui renvoie la taille d’un arbre binaire.

Calcul de la hauteur

Si l’arbre binaire est vide la hauteur est égale à ‘zéro’ (0).

Sinon hauteur(ab) = 1 + la plus grande des deux valeurs entre ‘taille(sag)’ et ‘taille(sad)’

Article sous licence << Cliquez pour plus d’informations <<