On s'intéresse dans cet exercice aux arbres binaires presque complets. Un tel arbre binaire est soit :
un arbre vide ;
un arbre binaire dont tous les niveaux sont remplis à l'exception éventuelle du dernier qui, s'il n'est pas entièrement rempli, est « tassé » à gauche : tous les nœuds présents au dernier niveau se trouvent sur la gauche de l'arbre binaire.
Un arbre binaire presque complet
flowchart TD
a((a)) --> b((b))
a --> c((c))
b --> d((d))
b --> e((e))
c --> f((f))
c ~~~ g(( ))
style g fill:none,stroke:none,color:none
classDef noeud font-family:consolas;
class a,b,c,d,e,f noeud;
On n'a pas représenté les arbres binaires vides.
Cet arbre binaire est presque complet : les deux premiers niveaux sont entièrement remplis, les nœuds du dernier niveau se trouvent sur la gauche.
Un arbre binaire presque complet de taille \(n\) peut être représenté en machine par un tableau de \(n+1\) valeurs. En indexant les valeurs à partir de \(0\), on trouve :
une valeur quelconque à l'indice \(0\) ;
la valeur portée par la racine à l'indice \(1\).
Pour les autres nœuds, on considère les règles suivantes. Si la valeur d'un nœud est stockée à l'indice \(k\) :
si son sous-arbre gauche est non-vide, sa valeur est stockée à l'indice \(2k\) ;
si son sous-arbre droit est non-vide, sa valeur est stockée à l'indice \(2k+1\).
Avec Python, on peut donc représenter les arbres binaires presque complets à l'aide de listes. On place la valeur None à l'indice 0.
L'arbre vide est donc représenté par la liste [None].
Représentation de l'arbre binaire vu plus haut
L'arbre binaire dessiné plus haut a une taille de \(6\). Il est donc représenté par une liste de longueur 7 :
# indices 0 1 2 3 4 5 6arbre=[None,'a','b','c','d','e','f']
Le 'b' se trouve a l'indice 2. On trouve bien 'd' à l'indice 2*2=4 et 'e' à l'indice 2*2+1=5.
1. Taille de l'arbre binaire
Écrire la fonction taille qui prend en paramètre une liste représentant un arbre binaire presque complet et renvoie sa taille.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)