Arbre binaire additif⚓︎
Représentation des arbres
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 --> B( )
A --> C( )
A --> D( )
On souhaite construire des arbres binaires parfaits « additifs ». Dans ces arbres, la valeur d'un nœud intérieur est toujours égale à la somme des valeurs de ses enfants.
graph TD
R(19) --> A(8)
R --> B(11)
A --> C(3)
A --> D(5)
B --> E(7)
B --> F(4)
C --> G( )
C --> H( )
D --> I( )
D --> J( )
E --> K( )
E --> L( )
F --> M( )
F --> N( )
Arbre binaire parfait
On rappelle qu'un arbre binaire est dit parfait lorsque tous ses niveaux sont complètement remplis.
On peut en déduire qu'un arbre binaire parfait de hauteur \(h\) compte \(2^{h-1}\) feuilles.
On demande d'écrire la fonction arbre_additif
prenant en argument la liste valeurs
contenant les valeurs des feuilles et renvoyant l'arbre correspondant.
On garantit que le nombre d'éléments de valeurs
est une puissance de \(2\). Ces éléments sont tous des nombres entiers.
Exemples
>>> arbre_additif([6])
(None, 6, None)
>>> arbre_additif([6, 9])
((None, 6, None), 15, (None, 9, None))
>>> arbre_additif([3, 5, 7, 4])
(((None, 3, None), 8, (None, 5, None)), 19, ((None, 7, None), 11, (None, 4, None)))
def arbrepy-undadditif(valeurs):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert arbrepy-undadditif([6]) == (None, 6, None)bksl-nlassert arbrepy-undadditif([6, 9]) == ((None, 6, None), 15, (None, 9, None))bksl-nlassert arbrepy-undadditif([3, 5, 7, 4]) == (bksl-nl ((None, 3, None), 8, (None, 5, None)),bksl-nl 19,bksl-nl ((None, 7, None), 11, (None, 4, None)),bksl-nl)bksl-nlbksl-nldef arbrepy-undadditif(valeurs):bksl-nl noeuds = [(None, x, None) for x in valeurs]bksl-nlbksl-nl while len(noeuds) > 1:bksl-nl prochains = []bksl-nl for i in range(0, len(noeuds), 2):bksl-nl gauche = noeuds[i]bksl-nl droite = noeuds[i + 1]bksl-nl prochains.append((gauche, gauche[1] + droite[1], droite))bksl-nl noeuds = prochainsbksl-nlbksl-nl return noeuds[0]bksl-nlbksl-nl
A
On procède ici de manière itérative en partant des feuilles.
Une autre approche est de procéder de façon récursive :
def arbre_additif_rec(valeurs):
if len(valeurs) == 1:
return (None, valeurs[0], None)
milieu = len(valeurs) // 2
return (
arbre_additif_rec(valeurs[:milieu]),
sum(valeurs),
arbre_additif_rec(valeurs[milieu:])
)
Cette façon de procéder présente toutefois plusieurs inconvénients :
- les différentes tranches
valeurs[:milieu]
etvaleurs[milieu:]
occupent de la mémoire, - les sommes des valeurs sont calculées à plusieurs reprises (lors du première appel on additionne toutes les valeurs, les deux premiers appels récursifs additionnent à nouveau les valeurs du début et de la fin de la liste, etc).
Z