# ===========================================================================
#  Tracé d'un arbre graphiquement
#  Version 2
# ===========================================================================

# importation des modules :
import matplotlib.pyplot as plt
import random

# ===========================================================================
#  Définition des fonctions :
# ===========================================================================

def vide():
    return None

def racine(t):
    return t[0]

def fg(t):
    return t[1]

def fd(t):
    return t[2]

def fils(t):
    return(fg(t),fd(t))

def est_vide(t):
    return t==None

def arbre(x,u,v):
    return (x,u,v)

# ---------------------------------------------------------------------------

def nbr_noeuds(t):
    if est_vide(t):
        return 0
    else:
        x,u,v=racine(t),fg(t),fd(t)
        return nbr_noeuds(u)+nbr_noeuds(v)+1

# ---------------------------------------------------------------------------

def liste_feuilles(t):
    if est_vide(t):
        return []
    else:
        x,u,v=racine(t),fg(t),fd(t)
        if est_vide(u) and est_vide(v): return [x]
        else: return liste_feuilles(u)+liste_feuilles(v)

# ---------------------------------------------------------------------------

def nombre_feuilles(t):
    if est_vide(t):
        return 0
    else:
        x,u,v=racine(t),fg(t),fd(t)
        if est_vide(u) and est_vide(v): return 1
        else: return nombre_feuilles(u)+nombre_feuilles(v)

# ---------------------------------------------------------------------------

def hauteur(t):
    if est_vide(t):
        return 0
    else:
        u,v=fg(t),fd(t)
        return 1 + max(hauteur(u),hauteur(v))


# ---------------------------------------------------------------------------

def dessiner_aux(t,rect,dy,labels):
    if est_vide(t):
        return

    x1,x2,y1,y2=rect
    xm=(x1+x2)//2
    x,t1,t2=t

    """ x,t1,t2=t est équuivalent à :

        x=t[0]
        t1=t[1]
        t2=t[2]
    """

    dessiner_aux(t1,(x1,xm,y1,y2-dy),dy,labels)
    dessiner_aux(t2,(xm,x2,y1,y2-dy),dy,labels)
    if labels:
        plt.text(xm-5,y2+5,str(x),fontsize=10,horizontalalignment='center',va='bottom')

    if not est_vide(t1):
        a,b=((xm,(x1+xm)//2),(y2,y2-dy))
        plt.plot(a,b,'k',marker='o',markerfacecolor='r')

    if not est_vide(t2):
        c,d=((xm,(x2+xm)//2),(y2,y2-dy))
        plt.plot(c,d,'k',marker='o',markerfacecolor='r')


# ---------------------------------------------------------------------------

def dessiner(t, labels=True):
    d=512
    pad=20
    dy=(d-2*pad)/(hauteur(t))
    dessiner_aux(t,(pad,d-pad,pad,d-pad),dy,labels)
    plt.axis([0,d,0,d])
    plt.show()

# ---------------------------------------------------------------------------
# Les arbres binaires de recherche (ABR) :

def rechercher(x,t):
    if est_vide(t):
        return False
    else:
        y,u,v=racine(t),fg(t),fd(t)
        if x<y:
            return rechercher(x,u)
        elif x>y:
            return rechercher(x,v)
        else:
            return True

def maximum(t):
    if est_vide(t):
        raise Exception('Arbre vide')
    else:
        x,u,v=racine(t),fg(t),fd(t)
        if est_vide(v):
            return x
        else:
            return maximum(v)

def minimum(t):
    if est_vide(t):
        raise Exception('Arbre vide')
    else:
        x,u,v=racine(t),fg(t),fd(t)
        if est_vide(u):
            return x
        else:
            return minimum(u)

def inserer(x,t):
    if est_vide(t):
        return (x,vide(),vide())
    else:
        y,u,v=racine(t),fg(t),fd(t)
        if x<=y:
            return (y,inserer(x,u),v)
        else:
            return (y,u,inserer(x,v))

def liste_aleatoire(n):
    s=list(range(n))
    random.shuffle(s)
    return s

def abr_aleatoire(n):
    s=liste_aleatoire(n)
    t=None
    for x in s:
        t=inserer(x,t)
    return t

def supprimer(x,t):
    if est_vide(t):
        return None
    else:
        y,u,v=racine(t),fg(t),fd(t)
        if x<y:
            return (y,supprimer(x,u),v)
        elif x>y:
            return (y,u,supprimer(x,v))
        elif est_vide(v):
            return u
        else:
            m=minimum(v)
            return (m,u,supprimer(m,v))

# ---------------------------------------------------------------------------
# Les différents parcours d'un arbre :

def parcours_prefixe(t): # R, G, D
    pass

def parcours_infixe(t): # G, R, D
    pass

def parcours_suffixe(t): # G, D, R
    pass

def parcours_largeur(t): # niveau par niveau
    pass

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

# Codage de l'arbre par un tuple de tuples :

#exemple=(2,(1,(0,None,None),None),(5,(4,(3,None,None),None),(12,(9,(8,(6,None,(7,None,None)),None),(10,None,(11,None,None))),(13,None,(14,None,(18,(17,(15,None,(16,None,None)),None),(19,None,None)))))))
#exemple=('A',('B',('C',None,('E',None,None)),('D',None,None)),('F',('G',('I',None,None),None),('H',None,('J',None,None))))

"""
# Racine de l'arbre (NIVEAU 1) :
exemple=(2,
# Sous-Arbre Gauche :
(1,(0,None,None),None),

# Sous-Arbre Droit :

# Racine NIVEAU 2 :
(5,
# SAG Niveau 3 :
(4,(3,None,None),None),
# SAD Niveau 3 :
(12,

# SAG Niveau 4 :
(9,
# SAG dégénéré :
(8,(6,None,(7,None,None)),None),
# SAD dégénéré :
(10,None,(11,None,None))),

# SAD Niveau 4 :
(13,None,(14,None,(18,(17,(15,None,(16,None,None)),None),(19,None,None)))))))


# arbre simple à 3 noeuds :
exemple=(5,
# SAG : 1 noeud :
(3, None, None),
# SAD : 1 noeud :
(8, None, None),
)
"""
# exemple3 page 7 :
# exemple=(8,(3,(1,None,None),(6,(4,None,None),(7,None,None))),(10,None,(14,(13,None,None),None)))

# création d'un ABR aléatoire :
exemple=abr_aleatoire(100)

# Affichage des information textuelles :
print('nombre de feuilles',nombre_feuilles(exemple))
print('liste des feuilles',liste_feuilles(exemple))
print('nombre de noeuds :',nbr_noeuds(exemple))
print('hauteur :',hauteur(exemple))

# Affichage graphique de l'arbre grâce à MatPlotLib :
plt.rcParams['figure.figsize'] = (20,6)

# Arbre avec le nom des noeuds :
dessiner(exemple)

# Arbre sans le nom des noeuds :
#dessiner(exemple,False)