Création d'arbre de Fibonacci
Arbre de Fibonacci
Il existe les nombres de Fibonacci, ici nous allons définir une famille d'arbres binaires !
Un arbre \(F_n\) de Fibonacci est un arbre binaire défini par récurrence pour \(n\in \mathbb N\) par
- \(F_0\) est un arbre binaire vide.
- \(F_1\) est un arbre binaire n'ayant qu'un seul nœud.
- Pour \(n>1\), \(F_n\) est un arbre binaire dont le sous-arbre à gauche est un arbre \(F_{n-1}\) et le sous-arbre à droite est un arbre \(F_{n-2}\).
Propriété : Pour \(n\in \mathbb N\), \(F_n\) est de hauteur \(n\).
Ces arbres sont utiles en informatique pour leur caractéristique d'équilibre ; notion que nous reverrons.
L'arbre de Fibonacci \(F_1\)
L'arbre de Fibonacci \(F_2\)
L'arbre de Fibonacci \(F_3\)
L'arbre de Fibonacci \(F_4\)
L'arbre de Fibonacci \(F_5\)
L'arbre de Fibonacci \(F_6\)
L'arbre de Fibonacci \(F_7\)
L'arbre de Fibonacci \(F_8\)
Fibonacci(4)
graph TB
A("8")
B("5")
C("3")
D("3")
E("2")
F("2")
G((" "))
H("2")
I((" "))
J((" "))
K((" "))
L((" "))
M((" "))
N((" "))
O((" "))
A --> B
A --> C
B --> D
B --> E
C --> F
C --> G
D --> H
D --> I
E --> J
E --> K
F --> L
F --> M
H --> N
H --> OMéthode __eq__ de la classe Noeud
class Noeud:
def __init__(self, valeur, gauche=None, droite=None):
self.valeur = valeur
self.gauche = gauche
self.droite = droite
def __eq__(self, ab):
"""
Test d'égalité récursif entre arbres binaires
self est non vide, ab est peut-être vide
"""
if ab is None:
return False
else:
return (
(self.valeur == ab.valeur)
and (self.gauche == ab.gauche)
and (self.droite == ab.droite)
)
Cette méthode permet de vérifier l'égalité entre deux arbres binaires non vides donnés par leur nœud racine. L'appel fonctionne aussi si l'un des deux ou les deux sont vides !
Les tests == internes se font alors avec des appels à __eq__ (de trois classes distinctes)
- soit de la même classe
Noeud, cette méthode est donc récursive - soit de la classe de
None - soit de la classe des valeurs...
Relisez ceci attentivement et demandez des explications si nécessaire !
Arbre de Fibonacci portant le nombre de nil
Coder une fonction Fibonacci qui prend en paramètre un entier h et qui renvoie l'arbre de Fibonacci de hauteur h et dont chaque nœud porte une étiquette qui indique le nombre total de nil dans ses sous-arbres.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)