from Noeud import *
from Files import File


class ABR():
    """Classe permettant de manipuler un arbre binaire de recherche. Cette
    classe s'appuie sur la classe Noeud qui représente un noeud de l'arbre."""
    def __init__(self, remplissage=None):
        """Création d'un arbre binaire de recherche vide, sauf si l'argument
           optionnel remplissage est fourni. Dans le cas où remplissage est un
           noeud (qui peut éventuellement avoir des fils), il devient la racine
           de l'arbre. Si remplissage est un tableau, ses valeurs sont
           automatiquement insérée dans l'arbre dans l'ordre du tableau."""
        self.racine = None
        if type(remplissage) == Noeud:  # Si on a fourni un noeud
            self.racine = remplissage   # il devient la racine de l'arbre
        elif type(remplissage) == list: # Si on a fourni une liste de valeurs
            for valeur in remplissage:  # On les insère dans l'arbre
                self.insertion(valeur)
    
    def __str__(self):
        """La chaîne représentant l'arbre est celle représent&ant son noeud
           racine (ou chaine vide si l'arbre est vide)."""
        if self.racine is None:
            return ""
        else:
            return str(self.racine)

    def parcours_prefixe(n):
        if type(n) == ABR: n = n.racine
        if n is not None:
            print(n.valeur, end=", ")
            ABR.parcours_prefixe(n.fils_gauche)
            ABR.parcours_prefixe(n.fils_droit)

    def parcours_infixe(n):
        if type(n) == ABR: n = n.racine
        if n is not None:
            ABR.parcours_infixe(n.fils_gauche)
            print(n.valeur, end=", ")
            ABR.parcours_infixe(n.fils_droit)

    def parcours_postfixe(n):
        if type(n) == ABR: n = n.racine
        if n is not None:
            ABR.parcours_postfixe(n.fils_gauche)
            ABR.parcours_postfixe(n.fils_droit)
            print(n.valeur, end=", ")

    def parcours_en_largeur(n):
        if type(n) == ABR: n = n.racine
        if n is not None:
            f = File()
            f.enfiler(n)
            while not(f.est_vide()):
                n = f.defiler()
                print(n.valeur, end=", ")
                if n.fils_gauche is not None:
                    f.enfiler(n.fils_gauche)
                if n.fils_droit is not None:
                    f.enfiler(n.fils_droit)
    
    def recherche(self, val):
        """Recherche la valeur val dans l'arbre. Renvoie None si elle n'est pas
           présente ou le noeud où elle se trouve si elle est dans l'arbre"""
        n = self.racine
        while n is not None:
            if n.valeur == val:
                return n
            elif n.valeur > val:
                n = n.fils_gauche
            else:
                n = n.fils_droit
        return None


    def insertion(self, val):
        """Insertion de la valeur val dans l'arbre"""
        if self.racine is None:   # Si l'arbre est vide
            self.racine = Noeud(None, val, None)  # On crée sa racine
        else:
            n = self.racine
            while n is not None:
                #print(n.valeur)
                precedent = n    # On note le noeud père où accrocher la valeur
                if n.valeur == val:
                    n = n.fils_gauche
                elif n.valeur > val:
                    n = n.fils_gauche
                else:
                    n = n.fils_droit
            # on accroche cette valeur au noeud précédent
            if precedent.valeur < val:  # Si c'est plus grand, accroche à droite
                precedent.fils_droit = Noeud(None, val, None)
            else:  # Si c'est plus petit ou égal, on accroche à gauche
                precedent.fils_gauche = Noeud(None, val, None)