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)