"""Module implémentant un Arbre Binaire (AB) sous forme d'objets.
Les noeuds ont une clé et des données associées.
Types
-----
Contenu = tuple(Clé, Data)
AB = ABV|AB NON VIDE
ABV = AB(None, None, None)
AB NON VIDE = AB(Contenu, AB, AB)
Noeud = AB(Contenu, AB, AB) --> dans cette implémentation, pas de distinction
Primitives
----------
+ contenu(noeud:'Noeud') -> tuple
+ cle(noeud:'Noeud') -> 'clé'
+ data(noeud:'Noeud') -> 'data'
+ nv_ABV() -> 'AB VIDE'
+ nv_AB(valeur:'tuple(cle,data)', g:'AB|None'=None, d:'AB|None'=None) -> 'AB NON VIDE'
+ est_ABV(arbre:'AB') -> bool
+ racine(arbre:'AB NON VIDE') -> 'Noeud'
+ gauche(arbre:'AB NON VIDE') -> 'AB'
+ droite(arbre:'AB NON VIDE') -> 'AB'
"""
# Importations
# Constantes
HTML = True # Affichage : True pour passer par HTML, False pour passer par console
AFFICHAGE_ABV = False # Pour afficher les sous-arbres vides
# Déclaration de la classe AB
class AB:
"""Implémentation d'un Arbre Binaire sous forme objet simple"""
def __init__(self, valeur=None, gauche=None, droite=None):
assert valeur or (valeur == None and gauche == None and droite == None)
self.v = valeur
self.g = gauche
self.d = droite
if valeur and gauche is None:
self.g = AB()
if valeur and droite is None:
self.d = AB()
def relier_a_gauche(self:'AB NON VIDE', sous_arbre:'AB'):
"""Méthode qui définit sous_arbre comme le sous-arbre gauche de l'arbre actif"""
self.g = sous_arbre
def relier_a_droite(self:'AB NON VIDE', sous_arbre:'AB'):
"""Méthode qui définit sous_arbre comme le sous-arbre droite de l'arbre actif"""
self.d = sous_arbre
def definir_donnees_racine(self:'AB', element:'Element NON VIDE'):
"""Méthode qui place l'élément NON VIDE en tant que racine de l'arbre"""
self.v = element
def vider(self:'AB'):
"""Méthode qui transforme l'arbre en AB VIDE"""
self.v = None
self.g = None
self.d = None
def __str__(self):
'''Méthode spéciale gérant un affichage représentatif de l'arbre'''
NOM_FICHIER = "arbre.html"
def creer_page(nom_fichier:str, code_mermaid:list):
html_template_debut = """
Réprésentation de l'arbre
Arbre
"""
html_template_fin = """
"""
f = open(nom_fichier, 'w')
f.write(html_template_debut)
print("\nCréation du fichier HTML ", end="")
for ligne in code_mermaid:
f.write(ligne)
print(".", end="")
f.write(html_template_fin)
print("\nFin")
f.close()
def version_mermaid(arbre):
# A Création du code JAVASCRIPT MERMAID
list_mermaid = ['flowchart TD;\n']
print("Récupération des pokemons")
if not est_ABV(arbre):
remplir(arbre, list_mermaid)
else:
list_mermaid.append("N0((∅));")
# B Création du code HTML
creer_page(NOM_FICHIER, list_mermaid)
del list_mermaid
# C Affichage de la page
fichier = os.getcwd()+'/' + NOM_FICHIER
webbrowser.open(fichier)
return "Fichier envoyé vers le navigateur"
def remplir(arbre:'ABR', lm:list, n=None) -> None:
'''Exploration en profondeur en préfixe RGD'''
if not est_ABV(arbre):
if n == None:
nom = f"{contenu(racine(arbre))[1]['Name']}"
cle = f"{contenu(racine(arbre))[0]}"
lm.append(f"N{1}(({contenu(racine(arbre))[0]}));\n")
n = 1
if not est_ABV(gauche(arbre)):
nom = f"{contenu(racine(gauche(arbre)))[1]['Name']}"
cle = f"{contenu(racine(gauche(arbre)))[0]}"
lm.append(f"N{n*2}(({contenu(racine(gauche(arbre)))[0]}));\n")
lm.append(f"N{n} --> N{n*2};\n")
remplir(gauche(arbre), lm, n*2)
elif AFFICHAGE_ABV or not est_ABV(droite(arbre)):
lm.append(f"N{n} --> N{n*2}[∅];\n")
if not est_ABV(droite(arbre)):
nom = f"{contenu(racine(droite(arbre)))[1]['Name']}"
cle = f"{contenu(racine(droite(arbre)))[0]}"
lm.append(f"N{n*2+1}(({contenu(racine(droite(arbre)))[0]}));\n")
lm.append(f"N{n} --> N{n*2+1};\n")
remplir(droite(arbre), lm, n*2+1)
elif AFFICHAGE_ABV or not est_ABV(gauche(arbre)):
lm.append(f"N{n} --> N{n*2+1}[∅];\n")
print(".", end="")
def version_BT(arbre):
if arbre.v is None:
return None
g = version_BT(arbre.g)
d = version_BT(arbre.d)
return Node(arbre.v[0], g, d)
if HTML:
try:
webbrowser
os
except:
import webbrowser
import os
return str(version_mermaid(self))
else:
try:
binarytree
except:
from binarytree import Node
return str(version_bt(self))
# Fonctions Primitives (toutes à coût constant)
def contenu(noeud:'Noeud') -> tuple:
"""Renvoie le contenu du noeud fourni, un couple (clé, data)"""
return noeud.v
def cle(noeud:'Noeud') -> 'Clé':
"""Renvoie la clé du noeud"""
return noeud.v[0]
def data(noeud:'Noeud') -> 'Data':
"""Renvoie les données associées à ce noeud"""
return noeud.v[1]
def nv_ABV() -> 'AB VIDE':
"""Renvoie un nouvel Arbre Binaire Vide"""
return AB()
def nv_AB(valeur:'tuple(cle,data)', g:'AB|None'=None, d:'AB|None'=None) -> 'AB NON VIDE':
"""Renvoie un nouvel Arbre Binaire dont la racine porte valeur et qui mène aux sous-arbres g et d"""
return AB(valeur, g, d)
def est_ABV(arbre:'AB') -> bool:
"""Prédicat qui renvoie True si l'arbre est vide"""
return arbre.v is None and arbre.g is None and arbre.d is None
def racine(arbre:'AB NON VIDE') -> 'Noeud':
"""Renvoie le noeud-racine de l'Arbre Binaire NON VIDE"""
return arbre # dans cette implémentation, un AB non vide est un pointeur vers sa racine
def gauche(arbre:'AB NON VIDE') -> 'AB':
"""Renvoie le sous-arbre gauche de l'Arbre Binaire NON VIDE"""
return arbre.g
def droite(arbre:'AB NON VIDE') -> 'AB':
"""Renvoie le sous-arbre droite de l'Arbre Binaire NON VIDE"""
return arbre.d
def inserer_gauche(arbre:'ABR NON VIDE', g:'ABR|ABV') -> None:
'''Place g en tant que sous-arbre gauche de arbre NON VIDE'''
arbre.relier_a_gauche(g)
def inserer_droite(arbre:'ABR NON VIDE', d:'ABR|ABV') -> None:
'''Place d en tant que sous-arbre droite de arbre NON VIDE'''
arbre.relier_a_droite(d)
# Déclarations des fonctions (utilisent les primitives, les coûts ne sont pas nécessairement constants)
def parcours_prefixe(arbre:'ABR') -> None:
'''Exploration (et affichage) en profondeur en préfixe RGD'''
if not est_ABV(arbre):
print(cle(racine(arbre)))
parcours_prefixe(gauche(arbre))
parcours_prefixe(droite(arbre))
def parcours_infixe(arbre:'ABR') -> None :
'''Exploration (et affichage) en profondeur en infixe GRD'''
if not est_ABV(arbre):
parcours_infixe(gauche(arbre))
print(cle(racine(arbre)))
parcours_infixe(droite(arbre))
def parcours_suffixe(arbre:'ABR') -> None:
'''Exploration (et affichage) en profondeur en postfixe GDR'''
if not est_ABV(arbre):
parcours_suffixe(gauche(arbre))
parcours_suffixe(droite(arbre))
print(cle(racine(arbre)))
def inserer_noeud_dans_ABR(arbre:'ABR NON VIDE', nd:'Noeud') -> None:
'''Insére le noeud au bon endroit dans l'ABR NON VIDE'''
# Etape 1 : initialisation
destination = arbre
# Etape 2 : on cherche jusqu'à trouver une destination vide
while not est_ABV(destination):
arbre_parent = destination
if cle(nd) < cle(racine(arbre_parent)):
destination = gauche(arbre_parent)
else:
destination = droite(arbre_parent)
# Etape 3 : nd devient un sous-arbre de arbre_parent
if cle(nd) < cle(racine(arbre_parent)):
inserer_gauche(arbre_parent, nd)
else:
inserer_droite(arbre_parent, nd)
def recherche(arbre:'ABR', cr: 'clé') -> 'ABR':
"""Recherche un noeud portant la bonne clé et renvoie sa référence"""
reponse = nv_ABV()
while not est_ABV(arbre):
if cr == cle(racine(arbre)):
reponse = arbre
arbre = nv_ABV()
elif cr < cle(racine(arbre)):
arbre = gauche(arbre)
elif cr > cle(racine(arbre)):
arbre = droite(arbre)
return reponse
# Programme de test du module
if __name__ == "__main__":
arbre = nv_AB((20, None))
inserer_noeud_dans_ABR(arbre, nv_AB((15, None)))
inserer_noeud_dans_ABR(arbre, nv_AB((25, None)))
inserer_noeud_dans_ABR(arbre, nv_AB((19, None)))
inserer_noeud_dans_ABR(arbre, nv_AB((20, None)))