#!/usr/bin/env python
# encoding: utf-8

class Noeud:
    pass
def noeud(x):
    n = Noeud()
    n.valeur = x
    n.gauche = None
    n.droit = None
    return n
class Arbre:
    pass
def arbre(n = None):
    a = Arbre()
    a.racine = n
    return a

# Exercice 1.
# Question 1.2

def vide(a):
    return a.racine == None

def gauche(a):
    return a.gauche

def droit(a):
    return a.droit

def racine(a):
    return a.racine.valeur

def cons(x, a1, a2):
    n = noeud(x)
    a = arbre(n)
    a.gauche = a1
    a.droit = a2
    return a

# Question 1.4

def profondeur(a):
    if vide(a):
        return 0
    else:
        return max(profondeur(gauche(a)), profondeur(droit(a)))

def nb_noeuds(a):
    if vide(a):
        return 0
    else:
        return 1 + nb_noeuds(gauche(a)) + nb_noeuds(droit(a))

def somme(a):
    if vide(a):
        return 0
    else:
        return racine(a) + somme(gauche(a)) + somme(droit(a))

def incremente(a):
    if vide(a):
        return a
    else:
        return cons(racine(a)+1, incremente(gauche(a)), incremente(droit(a)))

def hierarchie(a):
    if vide(a):
        return True
    else:
        if not vide(gauche(a)) and racine(a) < racine(gauche(a)):
            return False # le fils gauche de la racine est trop grand
        elif not vide(droit(a)) and racine(a) < racine(droit(a)):
            return False # le fils droit de la racine est trop grand
        else:
            return hierarchie(gauche(a)) and hierarchie(droit(a))

# Exercice 2.
# Question 2.2

def parcours1(a):
    if not vide(a):
        print racine(a)
        parcours1(gauche(a))
        parcours1(droit(a))

# Question 2.3

def parcours2(a):
    if not vide(a):
        parcours2(gauche(a))
        parcours2(droit(a))
        print racine(a)

# Exercice 3.

def applique(f, a):
    if vide(a):
        return a
    else:
        return cons(f(racine(a)), applique(f, gauche(a)), applique(f, droit(a)))

# 1ere solution pour applique_prof
def applique_prof(f, a):
    if vide(a):
        return a
    else:
    # on applique f à tout l'arbre, puis on redescend sur chaque fils
        return cons(a, applique(f, gauche(a)), applique(f, droit(a)))

# 2eme solution pour applique_prof
def applique_prof(f, a):
    # on définit une fonctions annexe qui prend un argument de plus (le nombre de fois qu'il faut appliquer la fonction f au noeud courant)
    def app_prof(f, a, n):
        if vide(a):
            return a
        elif n == 0:
            return cons(racine(a), app_prof(f, gauche(a), n+1), app_prof(f, droit(a), n+1))
        else:
            return app_prof(f, cons(f(racine(a)), gauche(a), droit(a)), n-1)
    # on appelle la fonction annexe avec le paramètre n = 1
    app_prof(f, a, 1)

def grand_chemin(a):
    if vide(a):
        return 0
    else:
        return racine(a) + max(grand_chemin(gauche(a)), grand_chemin(droit(a)))