Construction d'arbre binaire presque complet à gauche
Définition
Un arbre binaire est (presque) complet à gauche s'il possède toutes ses feuilles presque à la même profondeur (à 1 près). De plus les feuilles manquantes éventuelles sont toutes du même côté, à droite.
Propriété
Lors d'un parcours en largeur d'un arbre presque complet à gauche, on rencontre tous les nœuds, ensuite les nil.
Réciproquement, on peut reconstruire un unique arbre binaire presque complet à gauche à partir d'une liste d'étiquettes.
Un arbre presque complet à gauche
Pour alléger, il est inutile de dessiner certains nil dans ce cas... Ils existent néanmoins !
graph TB
N0("42")
N0 --> N00("13")
N0 --> N01("7")
N00 --> N000("5")
N00 --> N001("21")
N01 --> N010("18")
N01 --> N011("17")
N000 --> N0000("2")
N000 --> N0001("9")
N001 --> N0010("4")
N001 --> N0011("1")
N010 --> N1000("6")
N010 --> N1001(" ")
N011 --> N1010(" ")
N011 --> N1011(" ")liste_largeur = [42, 13, 7, 5, 21, 18, 17, 2, 9, 4, 1, 6]
Ci-dessus, la liste des étiquettes issue du parcours en largeur de l'arbre. On peut alors reconstruire sans équivoque cet arbre binaire presque complet à gauche.
Exercice
Coder une fonction construit_complet
- qui prend en paramètre
valeursla liste des étiquettes issues du parcours en largeur de l'arbre binaire presque complet à gaucheabque l'on souhaite construire ; - et qui renvoie
abl'unique arbre binaire presque complet à gauche associé, représenté à l'aide de la classeNoeud.
Classe Noeud
class Noeud:
def __init__(self, valeur, gauche=None, droite=None):
self.valeur = valeur
self.gauche = gauche
self.droite = droite
def __repr__(self):
"""Pour afficher la définition de l'arbre binaire ab,
en console ; il suffit de faire :
>>> ab
"""
...
def __str__(self):
"Pour afficher un petit arbre binaire en console"
...
def __eq__(self, autre):
"Test d'égalité récursif entre arbres binaires"
...
Un arbre binaire est donné soit par None s'il est vide, soit par son nœud racine.
Méthode __repr__
Cette méthode permet d'afficher une façon de définir un arbre la classe Noeud
On peut alors utiliser >>> ab (ou repr(ab)) pour afficher une définition de l'arbre dans la console Python.
Cet appel reste valable même si ab est vide. Auquel cas, la méthode __repr__ de None est appelée (mais pas celle de la classe Noeud).
Méthode __str__
Cette méthode permet d'afficher un arbre défini avec la classe Noeud
On peut alors utiliser print(ab) (ou str(ab)) pour afficher ab dans la console Python. Appel sans erreur, même si ab est vide.
Méthode __eq__
Cette méthode permet de vérifier l'égalité entre deux arbres binaires.
Les tests == internes se font avec un appel à __eq__ de la même classe Noeud (ou de None), donc cette méthode est récursive.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)