Sujet 01
Dans cet exercice, un arbre binaire de caractères non vide est stocké sous la forme d’un
dictionnaire où les clefs sont les caractères des nœuds de l’arbre et les valeurs, pour chaque
clef, la liste des caractères des fils gauche et droit du nœud. On utilise la valeur '' pour
représenter un fils vide.
Par exemple, l’arbre :
est stocké dans :
Par exemple, l’arbre :
a = {'F':['B','G'], 'B':['A','D'], 'A':['',''],
'D':['C','E'],'C':['',''], 'E':['',''],
'G':['','I'], 'I':['','H'],'H':['','']
}
Écrire une fonction récursive
On observe que, par exemple,
taille prenant en paramètres un arbre binaire arbre non vide sous la forme d’un dictionnaire et un caractère lettre qui est la valeur du sommet de l’arbre, et qui renvoie la taille de l’arbre à savoir le nombre total de nœuds. On observe que, par exemple,
arbre[lettre][0], respectivement arbre[lettre][1], permet d’atteindre la clé du sous-arbre gauche, respectivement droit, de l’arbre arbre de sommet lettre.
Exemples :
>>> taille(a, 'F')
9
>>> taille(a, 'B')
5
>>> taille(a, 'I')
2