Aller au contenu

Arbres binaires (interface)

Présentation

Définition

Les structures arborescentes permettent de représenter efficacement et synthétiquement des données issues de problèmes divers : probabilités, arbres de généalogie, organisation des répertoires sur un disque dur, liste des appels effectuées par une fonction récursive complexe, etc.

Les arbres sont une structure de données constituée d'éléments appelés nœud, auxquels on peut associer un certain nombre d'enfants. On s’intéresse dans ce TP aux arbres binaires, c’est à dire les arbres pour lesquels chaque nœud possède exactement deux enfants.

  • L’arbre vide: un arbre qui ne contient aucun nœud.
  • Les enfants: chaque arbre possède deux enfants, l’enfant gauche et l’enfant droit. Chaque enfant est lui même un arbre (il peut être vide).
  • La racine: le seul nœud de l'arbre qui ne possède pas de parents.
  • Les feuilles: il s’agit de nœuds dont les deux enfants sont des arbres vides.
  • Les étiquettes: chaque nœud peut être étiquetté par une valeur.

On prendra comme convention de représenter l'arbre vide par la valeur spéciale None. On assimilera également les arbres à leur nœud racine.

On donne ci-dessous l'interface du type Arbre.

Fonction Description
creer_vide() Renvoie un arbre vide
est_vide(a) Détermine si l'arbre a est vide
gauche(a) Renvoie l'enfant gauche de l'arbre a
droit(a) Renvoie l'enfant droit de l'arbre a
etiquette(a) Renvoie l'étiquette de la racine de l'arbre a
Arbre(e, ag, ad) Renvoie un arbre dont la racine a pour étiquette e,
  pour enfant gauche ag et pour enfant droit ad

interface

Exécuter le bloc ci-dessous pour charger l'interface du TP.

###

class Noeud:bksl-nl def py-undpy-undinitpy-undpy-und(self, etiquette, gauche, droit):bksl-nl self.etiquette = etiquettebksl-nl self.gauche = gauchebksl-nl self.droit = droitbksl-nlbksl-nldef creerpy-undvide(): return Nonebksl-nldef estpy-undvide(a): return a is Nonebksl-nldef etiquette(a): return a.etiquettebksl-nldef etiquettepy-undstr(a): return "•" if estpy-undvide(a) else str(etiquette(a))bksl-nldef gauche(a): return a.gauchebksl-nldef droit(a): return a.droitbksl-nldef Arbre(e, a1, a2): return Noeud(e, a1, a2)bksl-nlbksl-nl

Première utilisation

On peut représenter un arbre de la manière suivante :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
a0 = Arbre(5, None, None)
a1 = Arbre(-2, None, None)
a2 = Arbre(1, a0, a1)
a3 = Arbre(1,
           Arbre(4,
                 None,
                 Arbre(3, None, None)),
           Arbre(5,
                 Arbre(2,
                       Arbre(12, None, None),
                       Arbre(9, None, None)),
                 Arbre(1,
                       Arbre(7, None, None),
                       None)))
  1. Représenter graphiquement les arbres a0, a1, a2, a3.
  2. Quelle est l’étiquette de la racine de l'arbre \(\mathcal{A}_0\) ?
  3. Quel est le sous-arbre droit du nœud étiqueté 1 de l'arbre \(\mathcal{A}_3\) ?
  4. Quel est le sous-arbre gauche du nœud étiqueté 5 de l'arbre \(\mathcal{A}_3\) ?
  5. Quelles sont les étiquettes des feuilles de l’arbre de l'arbre \(\mathcal{A}_3\) ?

  6. Donner le code python correspondant aux arbres suivants :

    img

Exercices

Feuille d'un arbre

Écrire une fonction est_feuille qui étant donné un arbre a détermine si celui-ci est constitué d'un seul élément (sa racine est donc également une feuille).

###
def testpy-undestpy-undfeuille():bksl-nl """ Tests pour la fonction estpy-undfeuille """bksl-nl print("Tests de estpy-undfeuille passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import estpy-undfeuillebksl-nl# testpy-undestpy-undfeuille()bksl-nlbksl-nl 5/5

def estpy-undfeuille(a):bksl-nl """ Arbre -> boolbksl-nl Détermine si a est constitué d'un seul élément """bksl-nl passbksl-nlbksl-nl

Taille d'un arbre

Écrire une fonction récursive taille qui étant donné un arbre a détermine le nombre de nœuds que contient l'arbre a.

###
def testpy-undtaille():bksl-nl """ Tests pour la fonction taille """bksl-nl print("Tests de taille passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import taillebksl-nl# testpy-undtaille()bksl-nlbksl-nl 5/5

def taille(a):bksl-nl """ Arbre -> intbksl-nl Renvoie le nombre de nœuds de a """bksl-nl passbksl-nlbksl-nl

Somme des éléments d'un arbre

Écrire une fonction récursive somme qui étant donné un arbre a non vide dont les étiquettes de tous les nœuds sont des entiers, détermine la somme des étiquettes de l'arbre a.

###
def testpy-undsomme():bksl-nl """ Tests pour la fonction somme """bksl-nl print("Tests de somme passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import sommebksl-nl# testpy-undsomme()bksl-nlbksl-nl 5/5

def somme(a):bksl-nl """ Arbre -> intbksl-nl Renvoie la somme des éléments de l'arbre a """bksl-nl passbksl-nlbksl-nl

Hauteur d'un arbre

Écrire une fonction récursive hauteur qui étant donné un arbre a non vide détermine le nombre de "niveaux" dont est constitué l'arbre.

###
def testpy-undhauteur():bksl-nl """ Tests pour la fonction hauteur """bksl-nl print("Tests de hauteur passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import hauteurbksl-nl# testpy-undhauteur()bksl-nlbksl-nl 5/5

def hauteur(a):bksl-nl """ Arbre -> intbksl-nl Renvoie la hauteur de l'arbre """bksl-nl passbksl-nlbksl-nl

Affichage d'un arbre en mode texte

Écrire une fonction affiche_infixe qui étant donné un arbre a en réalise l'affichage à l'aide de l'algorithme récursif suivant :

  1. Si l'arbre est vide on n'affiche rien.
  2. Sinon :
    1. on affiche une parenthèse ouvrante ;
    2. on affiche récursivement le sous-arbre gauche ;
    3. on affiche l'étiquette du nœud racine de l'arbre ;
    4. on affiche récursivement le sous-arbre droit ;
    5. on affiche une parenthèse fermante.

On utilisera l'argument optionnel end de la fonction print afin que tous les affichages soient réalisés sur la même ligne.

###
def testpy-undaffichepy-undinfixe():bksl-nl """ Tests pour la fonction affichepy-undinfixe """bksl-nl print("Tests de affichepy-undinfixe passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import affichepy-undinfixebksl-nl# testpy-undaffichepy-undinfixe()bksl-nlbksl-nl 5/5

def affichepy-undinfixe(a):bksl-nl """ Arbre -> Nonetypebksl-nl Affiche l'arbre a de manière infixe """bksl-nl passbksl-nlbksl-nl

Recherche d'un élément dans un arbre

Écrire une fonction récursive recherche qui étant donné un arbre a dont les étiquettes de tous les nœuds sont des entiers, et un entier e détermine si l'entier e correspond à étiquette d'un des nœuds de l'arbre.

###
def testpy-undrechercher():bksl-nl """ Tests pour la fonction rechercher """bksl-nl print("Tests de rechercher passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import rechercherbksl-nl# testpy-undrechercher()bksl-nlbksl-nl 5/5

def rechercher(a, e):bksl-nl """ Arbre, int -> boolbksl-nl Renvoie True ssi e est une des étiquettes de a """bksl-nl passbksl-nlbksl-nl

Maximum des éléments d'un arbre

Écrire une fonction récursive maximum qui étant donné un arbre a (supposé non vide) dont les étiquettes de tous les nœuds sont des entiers, détermine la plus grande valeur d'une étiquette de l'arbre a.

###
def testpy-undmaximum():bksl-nl """ Tests pour la fonction maximum """bksl-nl print("Tests de maximum passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import maximumbksl-nl# testpy-undmaximum()bksl-nlbksl-nl 5/5

def maximum(a):bksl-nl """ Arbre -> intbksl-nl Renvoie la plus grande étiquette de a """bksl-nl passbksl-nlbksl-nl

Égalité d'arbres

Égalité d'arbres

On dit que deux arbres sont égaux lorsqu'ils ont la même structure et que leurs étiquettes sont les mêmes (aux mêmes endroits). Deux arbres égaux ont la même représentation graphique.

Écrire une fonction est_egal qui étant donné deux arbres a1 et a2 détermine si les deux arbres sont égaux.

###
def testpy-undestpy-undegal():bksl-nl """ Tests pour la fonction estpy-undegal """bksl-nl print("Tests de estpy-undegal passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import estpy-undegalbksl-nl# testpy-undestpy-undegal()bksl-nlbksl-nl 5/5

def estpy-undegal(a1, a2):bksl-nl """ Arbre, Arbre -> boolbksl-nl Détermine si les arbres a1 et a2 sont identiques """bksl-nl passbksl-nlbksl-nl

Égalité faible d'arbres

On dit que deux arbres sont faiblement égaux si l'on peut obtenir l'un en échangeant un nombre arbitaire d'enfants gauches et droits. Les étiquettes doivent cependant se trouver au même endroit après transformation.

Par exemple, les deux arbres ci-dessous ne sont pas égaux mais sont faiblement égaux.

img

Écrire une fonction est_egalf qui étant donné deux arbres a1 et a2 détermine si les deux arbres sont faiblement égaux.

###
def testpy-undestpy-undegalf():bksl-nl """ Tests pour la fonction estpy-undegalf """bksl-nl print("Tests de estpy-undegalf passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import estpy-undegalfbksl-nl# testpy-undestpy-undegalf()bksl-nlbksl-nl 5/5

def estpy-undegalf(a1, a2):bksl-nl """ Arbre, Arbre -> boolbksl-nl Renvoie True si et seulement si les arbres a1 et a2 sont faiblement égaux """bksl-nl passbksl-nlbksl-nl

Égalité de contenu d'arbres

On dit que deux arbres ont le même contenu si ils possèdent les mêmes étiquettes (qui possèdent le même nombre d'occurrence), sans se soucier de la structure de l'arbre.

Par exemple, les arbres ci-dessous ont le même contenu, mais ne sont pas égaux ni faiblement égaux :

img

Contenu d'un arbre

Écrire une fonction contenu qui étant donné un arbre a et un dictionnaire d ajoute au dictionnaire le contenu de a de la manière suivante :

  • les clés du dictionnaire correspondront aux étiquettes de l'arbre ;
  • les valeurs du dictionnaires correspondront aux occurrences de la clé correspondante.

On rappelle que si d est un dictionnaire k in d vaut True si et seulement si k est une des clés du dictionnaire d. On rappelle également que l'on peut accéder à la valeur associée à la clé k du dictionnaire d à l'aide de l'instruction d[k].

1
2
3
4
5
6
d = {3:6, 1:2, 2:4}    
print(3 in d)
print(6 in d)
print(d[3])
d[3] += 1
print(d[3])

True
False
6
7
###
def testpy-undcontenu():bksl-nl """ Tests pour la fonction contenu """bksl-nl print("Tests de contenu passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import contenubksl-nl# testpy-undcontenu()bksl-nlbksl-nl 5/5

def contenu(a, d):bksl-nl """ Arbre, dict -> Nonetypebksl-nl Ajoute à d le contenu de a """bksl-nl passbksl-nlbksl-nl

Égalité de dictionnaires

Écrire une fonction est_dico_egal qui étant donné deux dictionnaires détermine si ceux-ci sont égaux, c'est à dire :

  • d1 et d2 possèdent le même ensemble de clés ;
  • pour chaque clé k de leur ensemble de clé commun, les valeurs associées sont identiques : d1[k] est égal à d2[k].
###
def testpy-undestpy-unddicopy-undegal():bksl-nl """ Tests pour la fonction estpy-unddicopy-undegal """bksl-nl print("Tests de estpy-unddicopy-undegal passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import estpy-unddicopy-undegalbksl-nl# testpy-undestpy-unddicopy-undegal()bksl-nlbksl-nl 5/5

def estpy-unddicopy-undegal(d1, d2):bksl-nl """ dict, dict -> boolbksl-nl Détermine si les dictionnaires d1 et d2 sont égaux """bksl-nl passbksl-nlbksl-nl

Égalité de contenu d'arbres

Déduire des questions précédentes une fonction est_egalc qui étant donné deux arbres a1 et a2 détermine si les arbres a1 et a2 possèdent le même contenu.

###
def testpy-undestpy-undegalc():bksl-nl """ Tests pour la fonction estpy-undegalc """bksl-nl print("Tests de estpy-undegalc passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import estpy-undegalcbksl-nl# testpy-undestpy-undegalc()bksl-nlbksl-nl 5/5

def estpy-undegalc(a1, a2):bksl-nl """ Arbre, Arbre -> boolbksl-nl Renvoie True ssi les arbres a1 et a2 ont le même contenu """bksl-nl passbksl-nlbksl-nl

Documents