# solutions exercices arbres binaires et arbres binaires de recherche
# (mercredi 8 juillet, matin)

# à toutes fins utiles, on redonne la classe Noeud

class Noeud:
    def __init__(self, g, v, d):
        self.gauche = g
        self.valeur = v
        self.droit  = d


### exercice 1 ############################################################

# Il y a 5 arbres binaires possédant 3 noeuds
#    et 14 arbres binaires possédant 4 noeuds

### exercice 2 ############################################################

# Pour les dénombrer, on considère le noeud à la racine puis on
# répartit les quatre noeuds restants entre le sous-arbre gauche et
# le sous-arbre droit. Par exemple, on peut mettre un noeud dans
# le sous-arbre gauche et trois dans le sous-arbre droit. Au total, il
# y a cinq façons différentes de répartir les noeuds (0+4, 1+3,
# 2+2, 3+1, 4+0). Pour chacune, on connaît le
# nombre de sous-arbres possibles, ce qui donne la somme
#
#   1*14 + 1*5 + 2*2 + 5*1 + 14*1
#
# soit un total de 42 arbres binaires possédant 5 noeuds.

### exercice 3 ############################################################

def affiche(a):
    if a is None:
        return
    print("(", end="")
    affiche(a.gauche)
    print(a.valeur, end="")
    affiche(a.droit)
    print(")", end="")

### exercice 4 ############################################################

# On peut le faire au choix avec une fonction récursive ou avec une
# boucle. On choisit ici la seconde solution :

def peigne_gauche(h):
    """construit un peigne gauche de hauteur h"""
    a = None
    while h > 0:
        a = Noeud(a, h, None)
        h -= 1
    return a

# Il est intéressant de noter que les noeuds de l'arbre sont ici
# construits de bas en haut. C'est ce qui nous permet notamment de
# l'écrire facilement avec une boucle.

### exercice 5 ############################################################

# On reprend les cinq arbres de l'exercice 1 et on les
# étiquette correctement à chaque fois (il n'y a qu'une seule façon de le
# faire à chaque fois.

### exercice 6 ############################################################

# C'est exactement la même réponse que celle de l'exercice précédent !

### exercice 7 ############################################################

# par définition d'un ARB, le plus petit élément se trouve en bas à
# gauche de l'arbre.

def minimum(a):
    if a is None:
        return None
    if a.gauche is None:
        return a.valeur
    else:
        return minimum(a.gauche)

### exercice 8 ############################################################

def ajoute(x, a):
    if a is None:
        return Noeud(None, x, None)
    if x < a.valeur:
        return Noeud(ajoute(x, a.gauche), a.valeur, a.droit)
    elif x > a.valeur:
        return Noeud(a.gauche, a.valeur, ajoute(x, a.droit))
    else:
        return a # x est dans a

### exercice 9 ############################################################

def compte(x, a):
    if a is None:
        return 0
    if x < a.valeur:
        return compte(x, a.gauche)
    elif x > a.valeur:
        return compte(x, a.droit)
    else:
        return 1 + compte(x, a.gauche) + compte(x, a.droit)

### exercice 10 ############################################################

# C'est un cas particulier de parcours infixe

def remplir(a, t):
    if a is None:
        return
    remplir(a.gauche, t)
    t.append(a.valeur)
    remplir(a.droit, t)

# Pour la méthode lister, on crée un nouveau tableau, que l'on
# remplit avec la fonction remplir
# (à faire dans la classe ABR, bien entendu)

def lister(self):
    t = []
    remplir(self.racine, t)
    return t

### exercice 11 ############################################################

# L'idée est d'ajouter tous les éléments du tableau t dans un
# ABR, puis d'utiliser la méthode lister de l'exercice précédent.

def trier(t):
    a = ABR()
    for x in t:
        a.ajouter(x)
    return a.lister()

# L'efficacité de ce tri dépend fortement de la répartition des
# éléments dans le tableau initial. Si par exemple les éléments sont
# déjà triés dans le tableau initial, alors l'arbre sera un peigne et
# le coût de la construction de l'ABR sera donc quadratique.