def noeud(nom, fg = None, fd = None) :

    return {'racine': nom, 'fg' : fg, 'fd': fd}

# création des noeuds (chaque noeud est un dictionnaire)

k = noeud('k')

f = noeud('f')

e = noeud('e', k, None)

b = noeud('b', e, f)

m = noeud('m')

j = noeud('j', m, None)

i = noeud('i')

d = noeud('d', i, j)

h = noeud('h')

c = noeud('c', None, h)

a = noeud('a', c, d)

racine = noeud('r', a, b)

​

# création de l'arbre (construction récursive)

def construit(arbre) :

    if arbre == None :

        return []

    else:

        return [arbre['racine'],construit(arbre['fg']),construit(arbre['fd'])]

​

arbre1=construit(racine)

print(arbre1)

​

def hauteur(arbre):

    pass

def hauteur(arbre):

    if arbre==[]:

        return -1

    else:

        h1=1+hauteur(arbre[1])

        h2=1+hauteur(arbre[2])

        return max(h1,h2)

print(hauteur(arbre1))

# la classe File

class File:

    ''' classe File

    création d'une instance File avec une liste

    '''

    def __init__(self):

        "Initialisation d'une file vide"

        self.L=[]

​

    def vide(self):

        "teste si la file est vide"

        return self.L==[]

​

    def defiler(self):

        "défile"

        assert not self.vide(), "file vide"

        return self.L.pop(0)

​

    def enfiler(self,x):

        self.L.append(x)

def parcours_largeur(arbre):

    pass

def parcours_largeur(arbre):

    f=File()

    liste=[]

    f.enfiler(arbre)

    while not f.vide():

        tmp=f.defiler()

        liste.append(tmp[0])

        #print(liste)

        if tmp[1]!=[]:

            f.enfiler(tmp[1])

        if tmp[2]!=[]:

            f.enfiler(tmp[2])

    return liste

​

print(parcours_largeur(arbre1))

def parcours_prefixe(arbre):

    pass

​

def parcours_infixe(arbre):

    pass

​

def parcours_postfixe(arbre):

    pass

# parcours prefixe

​

def parcours_prefixe(arbre):

    if arbre!=[]:

        print(arbre[0],end=" , " )

        parcours_prefixe(arbre[1])

        parcours_prefixe(arbre[2])

parcours_prefixe(arbre1)

​

# parcours infixe

​

def parcoursInfixe(arbre) :

    if(arbre != []) :

        parcoursInfixe(arbre[1])

        print(arbre[0], end = ', ')

        parcoursInfixe(arbre[2])

parcoursInfixe(arbre1)

# parcours suffixe ou Postfixe

​

def parcoursPostfixe(arbre) :

    if(arbre != []) :

        parcoursPostfixe(arbre[1])

        parcoursPostfixe(arbre[2])

        print(arbre[0], end = ', ')

parcoursPostfixe(arbre1)

####################################################################

#                       Création de l'arbre                        #

####################################################################

sept=noeud(7,None,None)

quatre=noeud(4,None,None)

m = noeud('-',quatre,sept)

trois = noeud(3,None,None)

deux = noeud(2,None,None)

d = noeud('/',trois,m)

racine = noeud('+', deux, d)

​

arbreexp=construit(racine)

print(arbreexp)

def evalue(arbre):

    pass

def evalue(arbre):

    if arbre[1]==[] and arbre[2]==[]:

        res=arbre[0]

    elif arbre[0]=='+':

        res= evalue(arbre[1])+evalue(arbre[2])

    elif arbre[0]=='-':

        res= evalue(arbre[1])-evalue(arbre[2])

    elif arbre[0]=='*':

        res= evalue(arbre[1])*evalue(arbre[2])

    elif arbre[0]=='/':

        res= evalue(arbre[1])/evalue(arbre[2])

    else:

        res=None

    return res

​

print(evalue(arbreexp))

​

​

​