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 nœuds: éléments constituant l'arbre.

Il y a 7 nœuds dans l'arbre \(\mathcal{A}\). - Les étiquettes: chaque nœud peut être étiqueté par une valeur.

Les étiquettes des nœuds de l'arbre \(\mathcal{A}\) sont les nombres \(1\), \(2\), …, \(7\). - La racine: le seul nœud de l'arbre qui ne possède pas de parents.

Le nœud d'étiquette \(1\) est la racine de l'arbre \(\mathcal{A}\). - 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).

Le nœud d'étiquette \(1\) possède deux enfants : le sous-arbre gauche dont la racine est le nœud d'étiquette \(2\), et le sous-arbre droit dont la racine est le nœud d'étiquette \(5\).
Les feuilles: il s’agit de nœuds dont les deux enfants sont des arbres vides.

Les nœuds d'étiquettes \(3\), \(4\), \(6\) et \(7\) sont les feuilles de l'arbre \(\mathcal{A}\).

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`.

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¶

À l'aide de l'interface de l'énoncé, on peut représenter un arbre de la manière suivante :

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(8,
                       Arbre(7, None, None),
                       None)))

Représenter graphiquement les arbres a0, a1, a2, a3.
Quelle est l’étiquette de la racine de l'arbre \(\mathcal{A}_0\) ?
Quel est le sous-arbre droit du nœud étiqueté 1 de l'arbre \(\mathcal{A}_3\) ?
Quel est le sous-arbre gauche du nœud étiqueté 5 de l'arbre \(\mathcal{A}_3\) ?
Quelles sont les étiquettes des feuilles de l'arbre \(\mathcal{A}_3\) ?
Donner le code python correspondant aux arbres suivants :

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

Nombre de niveaux d'un arbre¶

Écrire une fonction récursive nb_niveaux 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 nbpy-undniveaux(a):bksl-nl """ Arbre -> intbksl-nl Renvoie le nombre de niveaux 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 :

Si l'arbre est vide on n'affiche rien.
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¶

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.

É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 :

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].

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