On trouve dans la littérature différentes définitions d'un arbre binaire.
Nous reprenons ici la définition de Donald Knuth1: un arbre binaire est un ensemble fini de nœuds. Cet ensemble est soit vide, soit constitué d'un nœud appelé racine et des éléments de deux arbres binaires disjoints appelés sous-arbres gauche et droit de la racine.
On représente un arbre binaire comme ci-dessous:
Cet arbre binaire a une racine qui a deux sous-arbres non vides.
Le sous-arbre gauche est composé d'une racine et de ses deux sous-arbres qui sont vides.
Le sous-arbre droit est composé d'une racine qui a un sous-arbre gauche vide et un sous-arbre droit
composé d'une racine qui a un sous-arbre droit vide et un sous-arbre gauche composé d'une racine
et de ses deux sous-arbres vides.
La taille d'un arbre binaire est son nombre de nœuds. On peut la définir récursivement.
Pour cela, on note \(t\) la fonction taille et, pour un arbre binaire non vide \(ab\), \(sag\) et \(sad\) son sous-arbre gauche et son sous-arbre droit.
Alors :
\[t(ab) = \begin{cases}0 \text{ si } ab \text{ est vide}\\ \\1+t(sag)+t(sad) \text{ sinon }\end{cases}\]
La hauteur d'un arbre binaire est aussi définie récursivement, en notant \(h\) la fonction hauteur, par :
\[h(ab) = \begin{cases}0 \text{ si } ab \text{ est vide}\\ \\1+\max(h(sag)~;~h(sad)) \text{ sinon }\end{cases}\]
Exemple
Cet arbre binaire a pour taille 5 et pour hauteur 4. On a numéroté les nœuds.
Nous utilisons la programmation orientée objet pour implémenter la structure d'arbre binaire. Dans la classe ArbreBinaire, la valeur None indique l'absence de valeur.
Par exemple, l'arbre binaire vide n'a pas de racine et donc pas de sous-arbre.
Il est demandé de compléter les deux méthodes tailleet hauteur dans le code de la classe ArbreBinaire.
Taille de l'arbre
Compléter la méthode taille de la classe ArbreBinaire.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Donald Knuth est un informaticien et mathématicien américain qui a reçu, entre autres distinctions, le prix Turing en 1974. Son ouvrage le plus connu est The Art Of Comuter Programming. ↩
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)