Arbres-binaires

Arbres binaires

Partie 1: description et parcours d'un arbre

On vous donne l'arbre suivant:

figure1

Question 1.1 

Quelle est la taille de cet arbre? Quel est sa hauteur h si la racine est de profondeur 1?

Citer le nombre de feuilles de cet arbre.

Cet arbre est-il équilibré?

Quelle est la profondeur du noeud 5?

Compte tenu de la hauteur h de l'arbre, quel est le nombre maximal N de noeuds qu'aurait pu avoir cette arbre? Exprimer la relation entre h et N

Question 1.2

On décide de coder cet arbre à partir d'objets nœuds décrits dans la classe suivante:

class Nœud:

    def __init__(self, g,v,d):

        self.gauche = g

        self.valeur = v

        self.droite = d

Coder l'arbre de la figure 1 à partir d'objets nœuds.

Question 1.3

Ecrire les fonctions python  calcule_taille(arbre)  et  mesure_hauteur(arbre) qui permettent de déterminer  la taille et la hauteur d'un arbre binaire. Vérifier que vous obtenez bien les mêmes valeurs qu'à la question 1.1

A)  Parcours en profondeur infixe:  Dans un parcours en profondeur infixe, on liste chaque nœud ayant un fils à gauche la seconde fois qu’on le voit et chaque nœud sans fils à gauche la première fois qu’on le voit, on commence par parcourir le sous-arbre de gauche. Les numéros sur les segments de l'arbre ci-dessous vous montre le sens parcours:  la valeur 4 (sans fils à gauche) est affichée la première fois qu'elle est rencontrée soit à l'étape 2 du parcours, la valeur 2 qui a un fils à gauche sera affichée,  la seconde fois qu'on le parcourt, au retour de l'étape 2 soit à l'étape 3. Pour l'arbre ci-dessous, on obtiendra l'ordre d'affichage: 427581396

figure 2

On vous donne le programme python qui réalise ce parcours:

def parcours_infixe(arbre):

    if arbre is None:

        return

    parcours_infixe(arbre.gauche)

    print(arbre.valeur, end =";")

    parcours_infixe(arbre.droite)

Question 1.4 

Tester le code du parcours infixe sur l'arbre de la figure 1 et comparer avec les valeurs sous la figure 2.

Que se passe-t-il après un return suite à un test évalué True de  if arbre is None ?  

B)  Parcours en profondeur préfixe:  dans ce cas de parcours en profondeur, on liste chaque sommet la première fois qu’on le rencontre dans le parcours. Cela donne l'affichage: 124578369 pour l'arbre étudié.

pseudo code:

ParcoursPréfixe(arbre_binaire):

    si arbre_binaire est vide:

        retourner

Afficher valeur

ParcoursPréfixe( sous arbre_binaire gauche)

ParcoursPréfixe( sous arbre_binaire droit)

Question 1.5

Coder en python le pseudo code du parcours préfixe et tester le code.

C)  Parcours en profondeur postfixe:  dans ce cas de parcours en profondeur, on liste chaque sommet la dernière fois qu’on le rencontre. Cela donne l'affichage: 478529631 pour l'arbre étudié.

ParcoursPostfixe(arbre_binaire):

    si arbre_binaire est vide:

        retourner

     ParcoursPostfixe( sous arbre_binaire gauche)

     ParcoursPostfixe( sous arbre_binaire droit)

     Afficher valeur

Question 1.6

Coder en python le pseudo code du parcours postfixe et tester le code.

C)  Parcours en largeur:  Le parcours d’un arbre en largeur consiste à partir de la racine puis visiter le fils gauche puis le fils droit, puis le fils gauche du fils gauche, puis le fils droit du fils droit, puis leurs enfants, etc.. Cela donne l'affichage: 123456789 pour l'arbre étudié.

On utilise une File f passée en paramètre de la fonction de parcours.

On passe également en paramètre de la fonction  l’arbre à parcourir.

On met l’arbre à parcourir dans la file f.

Tant que la file n’est pas vide:

On enlève un element de la file

Si l'élément enlevé ne vaut pas None

    On affiche la valeur du nœud de l'élément

    On met dans la file son fils gauche

    On met dans la file son fils droit

Algorithme python:

# classe cellule permet de construire un élément de la File

class Cellule :

    """ construit une cellule de liste chaînée """  

    def  __init__( self, valeur, cellule_suivante) :

        self.valeur=valeur

        self.suite_liste = cellule_suivante

# classe File permet de construire une file pour accueillir les nœuds de l'arbre

class File:

    def __init__(self):

         self.tete = None

         self.queue = None

    def est_vide(self):

        return self.tete is None

    def ajouter(self, valeur):

        # on crée un objet cellule qui contient la valeur à ajouter

        cell = Cellule( valeur, None)

        # on teste si c’est le premier élément ajouté

        if self.tete is None:

            self.tete = cell

        # s’il y a déjà une cellule, on rajoute en queue

        else:

            self.queue.suite_liste = cell

        self.queue = cell

    def retirer(self):

        if self.est_vide():

            raise IndexError (" la file est vide")

        # on enlève le premier élement de la file

        la_valeur_a_retirer =  self.tete.valeur

        # on fixe l’élément suivant en tête

        self.tete = self.tete.suite_liste

        # s’il n’y a plus d’élément en tête, la file est vide

        if self.tete is None:

            self.queue = None

        # on renvoie la valeur retirée.

        return la_valeur_a_retirer

# la fonction de parcours en largeur

def parcours_en_largeur(un_arbre, f):

     f.ajouter(un_arbre)

     while not f.est_vide():

         arbre=f.retirer()

         if arbre is not None:

             print(arbre.valeur, end= ";")

             f.ajouter(arbre.gauche)

             f.ajouter(arbre.droite)

# le programme principal

mon_arbre = Noeud( Noeud( Noeud( None,4, None) ,2, Noeud( Noeud( None,7, None) ,5, Noeud( None,8, None))), 1 , Noeud( None,3, Noeud( Noeud( None,9, None),6, None)) )

une_file = File()

parcours_en_largeur(mon_arbre, une_file)

     

Question 1.7

Tester le code. Détailler les étapes d'exécution de la fonction parcours_en_largeur(..) ce qui vous permettra de comprendre le code de la fonction.

Partie 2:  implémentation d'un arbre sous forme d'un dictionnaire

Il est également possible de coder un arbre avec la structure dictionnaire étudiée en première. Voici une fonction qui renvoie un dictionnaire qui représente le noeud d'un arbre:

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

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

# création d'un noeud qui contient la valeur 2

k = noeud(2)   # k = { 'racine':2, 'fg' : None, 'fd': None }

# visite du noeud:

print( k['racine'])   # affichera 2

# Ajout d'un nœud parent m au nœud k

m = noeud(3, k, None)   # m = { 'racine':3, 'fg' : { 'racine':2, 'fg' : None, 'fd': None }, 'fd': None }

Question 2.1

Compléter l'exemple ci-dessus pour obtenir l'arbre ci-dessous:

Question 2.2

Tester votre code en mesurant la taille de votre arbre avec le code ci-dessous:

def taille(arbre):

        """ nombre de noeuds de l'arbre"""

        if arbre is None:

            return 0

        else:

            return 1 + taille(arbre['fg']) + taille(arbre['fd'])

Question 2.3

En vous inspirant de la mesure de la taille ci-dessus et de l'implémentation objet de la mesure de la hauteur vu en cours: écrire le code qui permet de mesurer la hauteur d'un arbre conçu avec un dictionnaire.

Partie 3:  arbre de recherche ( ABR)

Question 3.1

Quelle propriété possède un ABR que l'on ne retrouve pas sur l'arbre binaire étudié en partie 1?

Question 3.2 

Quelle est la taille de cet arbre? Quel est sa hauteur?

Citer le nombre de feuilles de cet arbre.

Question 3.3

Coder cet arbre en utilisant un dictionnaire  pour chaque noeud de l'arbre.

Question 3.4:  appartenance à un arbre

Écrire une fonction qui permette de déterminer si un nombre appartient ou pas à l'arbre.

Question 3.5:  ajout d'une valeur dans un ABR

Ecrire une fonction qui permette d'ajouter un nombre à l'arbre en respectant la propriété d'un ABR. Tester ce code en ajoutant la valeur 5, redessiner l'arbre avec le nœud qui porte la valeur 5.

Projet

Voir la partie projet des activités ( encadré ci-dessous) :

Créé avec HelpNDoc Personal Edition: Produire des livres Kindle gratuitement