Notation de Neveu
🏷️ On considère ici des arbres étiquetés, et ordonnés.
Le cadre
Jusqu'à présent, tous les arbres avaient des enfants rangés dans l'ordre indiqué par une liste.
Plus tard, la notion d'arbre non ordonné sera abordée. En particulier lorsqu'on le définit avec les ancêtres de chaque nœud (sauf la racine) au lieu de la filiation qui donne une liste.
Pour un arbre ordonné, les sous-arbres sont alors indicés, et comme avec Python, on considère que les indices commencent à zéro.
Indiquer un nœud d'un arbre
Pour les besoins de cet exercice, on définit une adaptation de la notation de Neveu.
Pour un arbre ordonné, on peut avec une liste d'indices rejoindre n'importe quel nœud.
Avec l'arbre suivant
graph TB
N0(5)
N0 --> N1(9)
N0 --> N2(5)
N0 -->|2|N3(11)
N1 --> N4(4)
N2 --> N5(1)
N2 --> N6(8)
N3 --> |0|N7(8)
N3 --> N10(2)
N5 --> N8(6)
N7 --> |0|N9{3}
N9 --> M(5)Et la liste [0, 0, 2] on peut indiquer le nœud ayant l'étiquette 3.
En effet, en lisant la liste en partant de la fin et en partant de la racine :
- On prend le sous-arbre d'indice 2 (celui ayant une racine de 11).
- On prend la sous-arbre d'indice 0 (il porte une étiquette 8).
- On prend la sous-arbre d'indice 0 (il porte une étiquette 3).
Exercice
Coder une fonction neveu qui prend un arbre étiqueté et une liste filiation en paramètres et qui renvoie l'étiquette du nœud de l'arbre indiqué par la filiation suivant la notation de Neveu.
On garantit que les paramètres sont cohérents et qu'il n'y a aucune vérification à effectuer.
La liste filiation pourra être détruite lors de l'appel à neveu.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)