from File import File
from Pile import Pile
class Arbre :
def __init__(self, noeud, gauche=None, droit=None):
self.noeud= noeud
self.gauche= gauche
self.droit= droit
def __str__(self):
return "(" + str(self.noeud) +"," + str(self.gauche) +", "+ str(self.droit) +")"
def est_feuille(self):
return self.gauche==None and self.droit==None
def insert_gauche(self, valeur):
if self.gauche == None:
self.gauche = Arbre(valeur)
def insert_droit(self, valeur):
if self.droit == None:
self.droit = Arbre(valeur)
def taille(self):
if self.gauche is None and self.droit is None :
return 1
if self.gauche is None :
return self.droit.taille() + 1
if self.droit is None:
return self.gauche.taille() + 1
return 1 + self.gauche.taille() + self.droit.taille()
def hauteur(self):
if self.gauche is None and self.droit is None :
return 0
if self.gauche is None :
return 1 + self.droit.hauteur()
if self.droit is None :
return 1 + self.gauche.hauteur()
return 1+ max(self.gauche.hauteur(), self.droit.hauteur())
def parcours_largeur(self):
f = File()
f.enfiler(self)
while not f.est_vide():
n = f.defiler()
if n is not None:
print(n.noeud, end=" ")
f.enfiler(n.gauche)
f.enfiler(n.droit)
def parcours_profondeur(self):
p = Pile()
p.empiler(self)
while not p.est_vide():
n = p.depiler()
if n is not None:
print(n.noeud, end=" ")
p.empiler(n.droit)
p.empiler(n.gauche)
def parcours_profondeur_prefixe(self):
print(self.noeud, end=" ")
if self.gauche is not None:
self.gauche.parcours_profondeur_prefixe()
if self.droit is not None:
self.droit.parcours_profondeur_prefixe()
def parcours_profondeur_infixe(self):
if self.gauche is not None:
self.gauche.parcours_profondeur_infixe()
print(self.noeud, end=" ")
if self.droit is not None:
self.droit.parcours_profondeur_infixe()
def parcours_profondeur_postfixe(self):
if self.gauche is not None:
self.gauche.parcours_profondeur_postfixe()
if self.droit is not None:
self.droit.parcours_profondeur_postfixe()
print(self.noeud, end=" ")
def affiche(self, decalage=0):
if self.est_feuille():
print(decalage * " " + "|-->" + str(self.noeud))
else:
print(decalage * " " + "|-->" + str(self.noeud))
if self.gauche is not None:
self.gauche.affiche(decalage+1)
else:
print( (decalage+1) * " " + "|-->" + 'X')
if self.droit is not None:
self.droit.affiche(decalage+1)
else:
print( (decalage+1) * " " + "|-->" + 'X')
from Arbre import Arbre
def dico_occurence(texte):
dico = {}
for lettre in texte :
if lettre in dico.keys():
dico[lettre] = dico[lettre] + 1
else:
dico[lettre] = 1
return dico
def enlever_mini(liste_arbre):
mini = liste_arbre[0]
indice_mini = 0
for i in range(1, len(liste_arbre)):
if liste_arbre[i].noeud[1] < mini.noeud[1]:
mini = liste_arbre[i]
indice_mini = i
return liste_arbre.pop(indice_mini)
def generer_arbre_huffman(dico_occurence:dict) -> Arbre:
l = []
for lettre, occ in dico_occurence.items():
tpl = (lettre, occ)
a = Arbre(tpl)
l.append(a)
for _ in range(len(dico_occurence)-1):
mini1 = enlever_mini(l)
mini2 = enlever_mini(l)
noeud_tuple = ('', mini1.noeud[1] + mini2.noeud[1])
fusion = Arbre( noeud_tuple, mini2, mini1)
l.append(fusion)
return l[0]
def generer_dico_huffman(arbre:Arbre, dico:dict, chemin:str="") -> None:
if arbre.droit == None and arbre.gauche == None:
n = arbre.noeud
lettre = n[0]
dico[lettre] = chemin
if arbre.droit is not None:
generer_dico_huffman(arbre.droit, dico, chemin+"1")
if arbre.gauche is not None:
generer_dico_huffman(arbre.gauche, dico, chemin+"0")
def codage_huffman(texte, arbre_huffman):
dico_huffman = {}
generer_dico_huffman(arbre_huffman, dico_huffman)
resultat = ""
for lettre in texte :
rep = dico_huffman[lettre]
resultat = resultat + rep + " "
return resultat
def decodage_huffman(code, arbre):
decodage = ""
codes = code.split(' ')
arbre_courant = arbre
for code in codes:
for bit in code:
if bit == "0":
arbre_courant = arbre_courant.gauche
elif bit == "1":
arbre_courant = arbre_courant.droit
decodage = decodage + arbre_courant.noeud[0]
arbre_courant = arbre
return decodage
texte = 'BONJOUR'
dico_occurence = dico_occurence(texte)
arbre_huffman = generer_arbre_huffman(dico_occurence)
code = codage_huffman(texte, arbre_huffman)
print('Texte codé :', code)
decode = decodage_huffman(code, arbre_huffman)
print('Texte décodé :', decode)