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

# #####################################################################
# Classe Arbre (qui crée 1 noeud) :

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 :
        # ==> méthode à compléter après avoir supprimer l'instruction pass
        pass

    def parcours_infixe(self):
        # parcours en profondeur dans l'ordre INFIXE :
        # ==> méthode à compléter après avoir supprimer l'instruction pass
        pass

    def parcours_suffixe(self):
        # parcours en profondeur dans l'ordre SUFFIXE :
        # ==> méthode à compléter après avoir supprimer l'instruction pass
        pass

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

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

def parcours_infixe(arbre):
    # parcours en profondeur dans l'ordre INFIXE :
    # ==> fonction à compléter après avoir supprimer l'instruction pass
    pass

def parcours_suffixe(arbre):
    # parcours en profondeur dans l'ordre SUFFIXE :
    # ==> fonction à compléter après avoir supprimer l'instruction pass
    pass

# #####################################################################
# 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('Parcours préfixe : ',end='')
parcours_prefixe(b)