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

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

# ===========================================================================
#  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 nombre_noeuds(t):
    if est_vide(t):
        return 0
    else:
        x,u,v=racine(t),fg(t),fd(t)
        return nombre_noeuds(u)+nombre_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):
    # recherche la valeur x dans l'ABR t et renvoie soir True soit False
    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):
    # Renvoie la valeur maximale d'un ABR : la feuille à droite toute !
    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):
    # Renvoie la valeur minimale d'un ABR : la feuille à gauche toute !
    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):
    # ajoute la feuille x dans l'ABR t (renvoie un nouvel ABR sans modifier 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):
    # renvoie une liste aléatoire contenant les entiers de 0 à n-1 (n valeurs distinctes)
    s=list(range(n))
    random.shuffle(s)
    return s

def abr_aleatoire(n):
    # renvoie un ABR contenant n noeuds ayant pour valeur de 0 à n-1
    s=liste_aleatoire(n)
    t=None
    for x in s:
        t=inserer(x,t)
    return t

def supprimer(x,t):
    # supprime le noeud x dans l'ABR t (renvoie un nouvel ABR sans modifier 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
    if est_vide(t):
        return []
    else:
        x,u,v=racine(t),fg(t),fd(t)
        return [x]+parcours_prefixe(u)+parcours_prefixe(v)

def parcours_infixe(t): # G, R, D
    if est_vide(t):
        return []
    else:
        x,u,v=racine(t),fg(t),fd(t)
        return parcours_infixe(u)+[x]+parcours_infixe(v)

def parcours_suffixe(t): # G, D, R
    if est_vide(t):
        return []
    else:
        x,u,v=racine(t),fg(t),fd(t)
        return parcours_suffixe(u)+parcours_suffixe(v)+[x]

def parcours_largeur(t): # niveau par niveau
    f=Queue(nombre_noeuds(t)) # crée une file f
    f.put(t) # enfiler

    while not f.empty():
        a=f.get() # défiler
        x=racine(a)
        u=fg(a)
        v=fd(a)
        print('x',x,'u',u,'v',v)
        if u is not None:
            f.put(u) # enfiler
        if v is not None:
            f.put(v) # enfiler
    return

#---------------------------------------------------------------------------
# Trie d'une liste :

def liste_vers_arbre(s):
    t=None # crée un arbre vide
    for x in s:
        t=inserer(x,t) # ajoute chaque élément de la liste s dans l'ABR t
    return t

def trier(s):
    return parcours_infixe(liste_vers_arbre(s)) # retourne le parcours infixe de l'ABR

# ===========================================================================
#  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(12)

# Arbre binaire quelconque de taille 6 :
#exemple=(7,(3,(1,None,None),(8,None,None)),(5,(4,None,None),None))

# ABR de taille 6 :
exemple=(7,(3,(1,None,None),(4,None,None)),(9,(8,None,None),None))

print('\n\nParcours prefixe (R G D) : ',parcours_prefixe(exemple))
print('Parcours infixe (G R D) : ',parcours_infixe(exemple))
print('Parcours suffixe (G D R): ',parcours_suffixe(exemple))

print('\n\nParcours en largeur :')
parcours_largeur(exemple)

# Affichage des information textuelles :
print('\n\n\nnombre de feuilles',nombre_feuilles(exemple))
print('liste des feuilles',liste_feuilles(exemple))
print('nombre de noeuds :',nombre_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)