Arbres (1) Profondeur d'un nœud
Définition d'un arbre⚓︎
Un arbre est un ensemble d'éléments appelés nœuds, parmi lesquels on en distingue un appelé racine, avec une structure hiérarchique définie par une relation de parenté:
- un nœud seul est un arbre qui a pour racine ce nœud;
- avec un nœud \(n\) et \(k\) arbres de racines respectives \(n_1, n_2, ..., n_k\), on construit un nouvel arbre de racine \(n\) qui est le parent des nœuds \(n_1, n_2, ..., n_k\).
Chaque nœud, excepté la racine, a donc exactement un parent.
On suppose qu'il n'y a pas d'ordre sur les sous-arbres et on dit alors que l'arbre n'est pas ordonné.
Représentation d'un arbre⚓︎
Exemple du même arbre représenté de deux manières différentes. Les huits nœuds sont représentés par des cercles:
graph TB
r(( )) --- n1(( ))
r(( )) --- n2(( ))
r(( )) --- n3(( ))
n1(( )) --- n4(( ))
n3(( )) --- n5(( ))
n3(( )) --- n6(( ))
n3(( )) --- n7(( ))
r1(( )) --- n12(( ))
r1(( )) --- n13(( ))
r1(( )) --- n11(( ))
n13(( )) --- n15(( ))
n13(( )) --- n16(( ))
n13(( )) --- n17(( ))
n11(( )) --- n14(( ))Les nœuds sont numérotés de 0 à 7:
graph TB
r((0)) --- n1((1))
r --- n2((2))
r --- n3((3))
n1 --- n4((4))
n3 --- n5((5))
n3 --- n6((6))
n3 --- n7((7))Implémentation⚓︎
Les \(n\) nœuds d'un arbre sont numérotés de \(0\) à \(n-1\). L'ordre de numérotation n'a aucune importance. Lorsque les nœuds ont été numérotés, l'arbre peut être implémenté par un tableau dans lequel les indices représentent les numéros des nœuds. La valeur à l'indice \(i\) représente le numéro (et l'indice) du parent du nœud \(i\).
Si un élément à l'indice \(i\) vaut \(i\), cela signifie que le nœud numéro \(i\) n'a pas de parent: c'est donc la racine. La racine est donc l’unique nœud ayant une valeur égale à son indice.
Par exemple, l'arbre dessiné ci-dessus est représenté par le tableau [0, 0, 0, 0, 1, 3, 3, 3].
Le même arbre peut être implémenté par des tableaux différents selon l'ordre de numérotation choisi. Les tableaux [1, 2, 2, 2], [0, 0, 0, 1] et [3, 3, 1, 3] correspondent aux numérotations choisies dans les trois représentations ci-dessous:
graph TB
r((2)) --- n1((1))
r --- n2((3))
n1 --- n3((0))
r1((0)) --- n11((1))
r1 --- n12((2))
n11 --- n13((3))
r2((3)) --- n21((0))
r2 --- n22((1))
n22 --- n23((2))Un chemin est une suite de nœuds telle que chaque nœud est le parent du nœud suivant. La longueur d'un chemin est le nombre d'arêtes parcourues le long du chemin.
La profondeur d'un nœud est la longueur du chemin (unique) allant de la racine jusqu'à ce nœud.
On demande d'écrire une fonction profondeur qui prend en paramètres un arbre (représenté par un tableau comme ci-dessus) et le numéro d'un nœud, et renvoie la profondeur de ce nœud.
Exemples
>>> profondeur([1, 2, 2, 2], 0)
2
>>> profondeur([1, 2, 2, 2], 1)
1
>>> profondeur([0, 0, 0, 0, 1, 3, 3, 3], 6)
2
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)