# ######################################################################## #
#  Implémentation d'un arbre binaire en Programmation Orientée Objet (POO) #
#  Date : 5 novembre 2024                                                  #
#                  Programme arbre_poo Version 5                           #
# ######################################################################## #

# #####################################################################
# Classe Arbre (qui crée 1 noeud)
# Cette classe possède 3 méthodes permettant d'afficher les 3 parcours en profondeur :
# parcours_prefixe(self)
# parcours_infixe(self)
# parcours_suffixe(self)
# #####################################################################

class Arbre:
    def __init__(self, val):
        self.valeur = val
        self.gauche = None
        self.droit = None

    def ajout_gauche(self, val):
        self.gauche = Arbre(val)

    def ajout_droit(self, val):
        self.droit = Arbre(val)

    def taille(self):
        if self.vide():
            return 0
        else:
            tg = self.gauche.taille() if self.gauche else 0
            td = self.droit.taille() if self.droit else 0
            return 1 + tg + td

    def hauteur(self):
        if self.vide():
            return 0
        else:
            hg = self.gauche.hauteur() if self.gauche else 0
            hd = self.droit.hauteur() if self.droit else 0
            return 1 + max(hg, hd)

    def vide(self):
        return self.valeur==None

    def parcours_prefixe(self):
        # parcours en profondeur dans l'ordre PREFIXE (RGD) :
        print(self.valeur,' ',end='') # affiche la racine
        if self.gauche:
            self.gauche.parcours_prefixe() # traite récurcivement le SAG
        if self.droit:
            self.droit.parcours_prefixe() # traite récurcivement le SAD

    def parcours_infixe(self):
        # parcours en profondeur dans l'ordre INFIXE (GRD) :
        if self.gauche:
            self.gauche.parcours_infixe() # traite récurcivement le SAG
        print(self.valeur,' ',end='') # affiche la racine
        if self.droit:
            self.droit.parcours_infixe() # traite récurcivement le SAD

    def parcours_suffixe(self):
        # parcours en profondeur dans l'ordre SUFFIXE (GDR) :
        if self.gauche:
            self.gauche.parcours_suffixe() # traite récurcivement le SAG
        if self.droit:
            self.droit.parcours_suffixe() # traite récurcivement le SAD
        print(self.valeur,' ',end='') # affiche la racine


# #####################################################################
# Fonctions externes à la classe Arbre :
# #####################################################################

def parcours_prefixe(arbre):
    # parcours en profondeur dans l'ordre PREFIXE :
    if arbre:
        print(arbre.valeur,' ',end='')
        parcours_prefixe(arbre.gauche)
        parcours_prefixe(arbre.droit)

def parcours_infixe(arbre):
    # parcours en profondeur dans l'ordre INFIXE :
    if arbre:
        parcours_infixe(arbre.gauche)
        print(arbre.valeur,' ',end='')
        parcours_infixe(arbre.droit)


def parcours_suffixe(arbre):
    # parcours en profondeur dans l'ordre SUFFIXE :
    if arbre:
        parcours_suffixe(arbre.gauche)
        parcours_suffixe(arbre.droit)
        print(arbre.valeur,' ',end='')

# #####################################################################
# Programme principal :
# #####################################################################

# ==> Décommentez un seul arbre b à la fois pour le tester

"""
# Arbre vide :
b=Arbre(None)

# Arbre unitaire :
b=Arbre('R')

# Arbre simple à 3 noeuds :
b=Arbre(1)
b.ajout_gauche(2)
b.ajout_droit(3)

"""
# Création en mémoire de l'arbre de la page 10 du TP 1 :
b = Arbre(1)
b.ajout_gauche(2)
b.ajout_droit(3)
b.gauche.ajout_gauche(4)
b.gauche.ajout_droit(5)
b.gauche.gauche.ajout_gauche(8)
b.gauche.gauche.ajout_droit(9)
b.gauche.droit.ajout_gauche(10)
b.droit.ajout_gauche(6)
b.droit.ajout_droit(7)

"""
# Création en mémoire de l'arbre de la page 1 du TP 2 :
b = Arbre('A')
b.ajout_gauche('B')
b.ajout_droit('C')
b.gauche.ajout_gauche('D')
b.gauche.ajout_droit('E')
b.gauche.gauche.ajout_droit('G')
b.droit.ajout_gauche('F')
"""

# Affichage des informations concernant l'arbre b :
print("Taille de l'arbre : %d" % b.taille())
print("Hauteur de l'arbre : %d" % b.hauteur())

print('\nParcours préfixe : ',end='')
parcours_prefixe(b)
print('\nParcours préfixe : ',end='')
b.parcours_prefixe()

print('\n\nParcours infixe : ',end='')
parcours_infixe(b)
print('\nParcours infixe : ',end='')
b.parcours_infixe()

print('\n\nParcours suffixe : ',end='')
parcours_suffixe(b)
print('\nParcours suffixe : ',end='')
b.parcours_suffixe()

# #####################################################################
#  Fin du programme principal
#        nsi.gecif.net
# #####################################################################