On souhaite construire des arbres binaires parfaits « additifs ». Dans ces arbres :
tous les niveaux sont entièrement remplis ;
la valeur d'un nœud intérieur est toujours égale à la somme des valeurs de ses enfants.
Un exemple d'arbre binaire additif
graph TD
R(19) --> A(8)
R --> B(11)
A --> C(3)
A --> D(5)
B --> E(7)
B --> F(4)
C -.-x G( )
C -.-x H( )
D -.-x I( )
D -.-x J( )
E -.-x K( )
E -.-x L( )
F -.-x M( )
F -.-x N( )
style G display:none;
style H display:none;
style I display:none;
style J display:none;
style K display:none;
style L display:none;
style M display:none;
style N display:none;
Cet arbre est :
parfait (tous ses niveaux sont remplis) ;
additif (on a \(3 + 5 = 8\) ; \(7 + 4 = 11\) ; \(8 + 11 = 19\)).
On demande d'écrire la fonction arbre_additif qui prend en argument la liste valeurs contenant les valeurs des feuilles et renvoie l'arbre correspondant représenté à l'aide de tuples.
On garantit que le nombre d'éléments de valeurs est une puissance de \(2\) strictement positive. Ces éléments sont tous des nombres entiers.
Représentation des arbres en machine
On représente les arbres binaires ainsi :
l'arbre vide est représenté par None,
un arbre non vide est représenté par un tuple (sous-arbre gauche, valeur, sous-arbre droit).
Ainsi le tuple ((None, 6, None), 15, None) représente l'arbre suivant :
graph TD
R(15) --> A(6)
R -.-x B( )
A -.-x C( )
A -.-x D( )
style B display:none;
style C display:none;
style D display:none;
L'algorithme peut être construit autour d'un parcours en largeur partant du dernier niveau de l'arbre (les feuilles) et remontant, niveau par niveau, jusqu'à la racine.
Avec deux list...
On peut, par exemple, débuter en construisant une liste contenant les feuilles. On calcule ensuite la liste contenant les nœuds du niveau supérieur.
Ce calcul effectué, on remplace la liste des nœuds par la nouvelle et on répète la démarche jusqu'à atteindre la racine.
... ou avec une file
On pourra aussi utiliser une structure de file afin de mettre œuvre un parcours en largeur « remontant » l'arbre.
On fournit à ce titre les fonctions creer_file, enfiler et defiler d'ores et déjà chargées en mémoire et utilisables sans effectuer d'imports.
🐍 Console Python
>>> f=creer_file()# création d'une file vide>>> enfiler(f,0)# on enfile la valeur 0 dans f>>> enfiler(f,1)# on enfile la valeur 1 dans f>>> enfiler(f,2)# on enfile la valeur 2 dans f>>> defiler(f)# on défile, et l'on récupère, une valeur de f0>>> defiler(f)# on défile, et l'on récupère, une valeur de f1>>> defiler(f)# on défile, et l'on récupère, une valeur de f2>>> len(f)# nombre d'éléments dans f0
###(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
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)