from affiche_arbre import affiche_arbre, chaine_representation_arbre

class Noeud():
    def __init__(self, fils_gauche, valeur, fils_droit):
        self.fils_gauche = fils_gauche
        self.valeur = valeur
        self.fils_droit = fils_droit

    def est_vide(self):
        return self.fils_gauche is None and \
               self.valeur is None and \
               self.fils_droit is None

    def taille(n):
        """Renvoie la taille de l'arbre dont la racine est n"""
        if n is None:
            return 0
        else:
            return 1 + Noeud.taille(n.fils_gauche) + Noeud.taille(n.fils_droit)
     
    def hauteur(n) -> int:
        """Renvoie la hauteur de l'arbre dont la racine est n"""
        if n is None:
            return 0
        else:
            return 1 + max(Noeud.hauteur(n.fils_gauche), Noeud.hauteur(n.fils_droit))

    def __str__(self):
        return chaine_representation_arbre(self)

    def greffe_gauche(self, n):
        """Greffe le noeud n à gauche s'il n'y a pas de fils gauche"""
        if self.fils_gauche is None:
            self.fils_gauche = n

    def greffe_droit(self, n):
        """Greffe le noeud n à droite s'il n'y a pas de fils droit"""
        if self.fils_droit is None:
            self.fils_droit = n

    def __eq__(n1, n2):
        """Teste l'égalité de deux arbres binaires"""
        if n1 is None and n2 is None:  # Si les deux sont None, ils sont égaux
            return True
        elif n1 is None or n2 is None: # Si un seul des deux est None et
            return False               # pas l'autre, l'égalité est fausse
        else:
            return n1.valeur == n2.valeur and \
                   Noeud.__eq__(n1.fils_gauche, n2.fils_gauche) and \
                   Noeud.__eq__(n1.fils_droit, n2.fils_droit)