Exercices corrigés sur les arbres - TD 1 | Développement Informatique

Dans ce TD, nous allons implémenter des arbres binaires en Python. On choisit de représenter l’arbre vide par la liste vide, et un arbre de racine étiquetée par e et fils fg et fd par la liste [e, fg, fd]

Dans ces exercices, nous allons travailler sur cet arbre

La représentation de l'arbre ci-dessus est :

                                            a=[40,[14,[5,[],[]],[4,[],[8,[],[]]]],[6,[],[]]]

Exercice 1

Ecrire une fonction hauteur(a) calculant la hauteur d’un arbre.

Exemple(s)

Hauteur(a)
la hauteur de a = 3

Solution

Python

def hauteur(a):
    # Ici le cas de base, ca veut dire l'enfant d'une feuille, 
    # puisque une feuille
    # n'a pas d'enfant retourner -1 (1+max(-1,-1)=1+(-1)=0 ) donc 0 
    # est la hauteur d'une feuille
    if len(a) == 0:
        return -1
    else:
        # 1 + le maximum entre l'enfant gauche a[1] et l'enfant droit a[2]
        return 1 + max(hauteur(a[1]), hauteur(a[2]))

Exercice 2

Ecrire une fonction calculant le nombre de nœuds d’un arbre binaire.

Exemple(s)

nb_noeuds(a)
Nombre de noeuds de a = 3

Solution

Python

def nb_noeuds(a):
    # Ici le cas de base, ca veut dire l'enfant d'une feuille, 
    # puisque une feuille
    # n'a pas d'enfant retourner 0
    if len(a) == 0:
        return 0
    else:
        # 1 (noeud lui même) + nombre de noeuds de sous arbre gauche 
        # a[1] + nombre de noeuds de sous arbre droit a[2]
        return 1 + nb_noeuds(a[1]) + nb_noeuds(a[2])

Exercice 3

Ecrire une fonction calculant le nombre de feuilles d’un arbre binaire.

Exemple(s)

nb_feuilles(a)
Nombre de feuille de a = 3

Solution

Python

def nb_feuilles(a):
    # Ici le cas de base, ca veut dire l'enfant d'une feuille, 
    # puisque une feuille n'a pas d'enfant retourner 0
    if len(a) == 0:
        return 0
    # si il s'agit d'une feuille [val,[],[]]
    # le noeud n'a pas d'enfant gauche [] et d'enfant droit []
    elif len(a[1]) + len(a[2]) == 0:
        return 1
    else:
        # Sinon retourner le nombre d'enfants de sous arbre gauche a[1]
        # et sous arbre droit a[2]
        return nb_feuilles(a[1]) + nb_feuilles(a[2])

Exercices corrigés sur les arbres - TD 1