import matplotlib.pyplot as plt

class Arbre:
    def __init__(self,valeur,filsgauche=None,filsdroit=None):
        self.valeur=valeur
        self.filsgauche=filsgauche
        self.filsdroit=filsdroit

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

    def insertion_gauche(self, valeur):
        if self.filsgauche==None:
            self.filsgauche=Arbre(valeur)

    def insertion_droite(self, valeur):
        if self.filsdroit==None:
            self.filsdroit=Arbre(valeur)

    def zhauteur(self):
        listeh=[]
        if self.valeur==None:
            return 0
        if self.filsgauche==None and  self.filsdroit==None :
            return 0
        else:
            if self.filsgauche!=None:
                listeh.append(self.filsgauche.zhauteur())

            if self.filsdroit!=None:
                listeh.append(self.filsdroit.zhauteur())

            return max(listeh)+1

    def dessine_recurs(self,x1,x2,y1,y2,dy):

        if self.valeur==None:
            return

        xm=(x1+x2)//2

        if self.filsgauche!=None:
            self.filsgauche.dessine_recurs(x1,xm,y1,y2-dy,dy)
        if self.filsdroit!=None:
            self.filsdroit.dessine_recurs(xm,x2,y1,y2-dy,dy)

        plt.text(xm+6,y2,self.valeur, horizontalalignment='left', verticalalignment='center')

        if self.filsgauche!=None:
            plt.plot((xm, (x1 + xm) // 2), (y2, y2 - dy),'dodgerblue',marker='o', markersize=8)

        if self.filsdroit!=None:
            plt.plot((xm, (x2 + xm) // 2), (y2, y2 - dy),'dodgerblue',marker='o', markersize=8)


    def dessine(self):
        d=512
        pad=20
        dy=(d-2*pad)/(self.zhauteur()+1)
        self.dessine_recurs(pad,d-pad,pad,d-pad,dy)
        plt.axis([0, d, 0, d])
        plt.axis('off')
        plt.show()

    def dessinePays(self):
        d=512
        pad=20
        dy=(d-2*pad)/(self.zhauteur()+1)
        self.dessine_recursPays(pad,d-pad,pad,d-pad,dy)
        plt.axis([0, d, 0, d])
        plt.axis('off')
        plt.show()

    def dessine_recursPays(self,x1,x2,y1,y2,dy):

        if self.valeur==None:
            return
        xm=(x1+x2)//2
        if self.filsgauche!=None:
            self.filsgauche.dessine_recursPays(x1,xm,y1,y2-dy,dy)
        if self.filsdroit!=None:
            self.filsdroit.dessine_recursPays(xm,x2,y1,y2-dy,dy)
        plt.text(xm+10,y2,self.valeur[2])
        if self.filsgauche!=None:
            plt.plot((xm, (x1 + xm) // 2), (y2, y2 - dy),'dodgerblue',marker='o')
        if self.filsdroit!=None:
            plt.plot((xm, (x2 + xm) // 2), (y2, y2 - dy),'dodgerblue',marker='o')