Diamètre d'un arbre
😀 On considère ici des arbres non étiquetés.
Définition du diamètre d'un arbre
Le diamètre d'un arbre est la plus grande distance entre deux nœuds.
Un tel chemin n'est pas nécessairement unique et il ne passe pas nécessairement par la racine. Pour l'arbre réduit à un nœud le diamètre vaut zéro.
Cette notion est générale aux graphes, dont les arbres enracinés font partie.
Arbre de diamètre 6
graph TB
R{ } --- N1{ }
R --- N3{ }
N1 --- N4{ }
N1 --- N5{ }
N3 --- N6{ }
N3 --- N7{ }
N3 --- N8{ }
N4 --- N9{ }
N6 --- N10{ }
N6 --- N11{ }
N6 --- N12{ }
N6 --- N13{ }Exercice
Coder une fonction diamètre qui prend un arbre non étiqueté en paramètre et qui renvoie son diamètre.
Les fonctions de tri sont interdites dans cet exercice, à vous de faire sans.
🥼 Indice
On peut résoudre efficacement ce problème par programmation dynamique.
On pensera alors à créer une fonction auxiliaire récursive qui renvoie un tuple (hauteur, diamètre).
On pourra alors écrire
def diamètre(arbre):
"Renvoie le diamètre de l'arbre"
h, d = auxiliaire(arbre)
return d
Guide
def diamètre(arbre):
"Renvoie le diamètre de l'arbre"
def auxiliaire(arbre):
"Renvoie le couple (hauteur, diamètre)"
enfants = arbre
h_max, d_max = ..., ...
for enfant in enfants:
h, d = auxiliaire(enfant)
...
...
return ..., ...
h, d = auxiliaire(arbre)
return d
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)