TD 5 : Introduction aux arbres

Les méthodes de tous les exercices doivent être écrites dans les classes fournies en annexe (télécharger ces classes) .

EXERCICE 1

On désire implémenter les mesures qui s'appliquent aux arbres binaires étudiés en cours.

Ecrivez les méthodes taille, hauteur, bassesse et feuilles de la classe ArbreBinaire telles que A.taille(), A.hauteur(), A.bassesse() et A.feuilles() retournent respectivement la taille, la hauteur, la bassesse et le nombre de feuilles de l'arbre A. Identifiez le type de parcours utilisé par chacune de ces méthodes.

Aucune difficulté.

EXERCICE 2

On appelle base d'un arbre binaire non vide le nombre de noeuds de profondeur h où h est la hauteur de l'arbre. La largeur de l'arbre vide est 0.

Après avoir écrit la méthode auxiliaire appropriée et en utilisant la méthode hauteur définie précédemment, écrivez la méthode base de la classe ArbreBinaire telles que A.base() retourne la base de l'arbre A.

Plus généralement, on peut chercher le nombre de noeuds de profondeur p.

EXERCICE 3

On représente la généalogie d'un individu par un ArbreBinaire dont la racine est l'individu (par exemple, son nom), le sous-arbre gauche étant la généalogie de son père (vide si père inconnu), et le sous-arbre droit étant la généalogie de sa mère (vide si mère inconnue).

Ecrivez la procédure ascendants(int k) de la classe ArbreBinaire qui, étant donnée la généalogie d'un individu, affiche sur le flux de sortie tous les ascendants masculins connus de l'individu à la k-ième génération.

Pour ne pas afficher la (les) (grand)-mère(s), il faut s'arrêter sur le (la) (k-1)-ième ascendant(e).

Ecrivez la méthode tousLesAscendants(int k) de la classe ArbreBinaire qui, étant donnée la généalogie d'un individu, affiche sur le flux de sortie tous les ascendants masculins connus de l'individu jusqu'a la k-ième génération.

Quand on est sur le (la) i-ième ascendant(e) (i < k), il est facile d'afficher son père (s'il existe).

EXERCICE 4

On définit les deux relations binaires suivantes sur les arbres binaires (A et B sont des arbres binaire) :

A est équivalent à B si et seulement si A et B ont exactement la même structure
A est isomorphe à B si et seulement si on peut passer de A à B en effectuant zéro, une ou plusieurs permutations de certains des sous-arbres de A. Deux arbres équivalents sont isomorphes.

Montrez que ces deux relations binaires sont des relations d'équivalence.

On rappelle qu'une relation d'équivalence est une relation réflexive, symétrique et transitive.

Ecrivez les méthodes equivalent et isomorphe de la classe Isomorphisme qui, respectivement, teste si deux arbres sont équivalents ou isomorphes.

Utilisez le fait que ces relations sont des relations d'équivalence et n'effectuez pas des tests inutiles.

EXERCICE 5

On considère les deux propriétés suivantes définies sur un arbre binaire :

un arbre penche-à-gauche si, soit l'arbre est vide, soit ses sous-arbres penchent-à-gauche et celui de gauche a au moins autant d'éléments que celui de droite.
un arbre est équilibré si, soit l'arbre est vide, soit ses sous-arbres sont équilibrés et leur hauteur diffère au plus de un.

Expliquez en quoi les propriétés penche-à-gauche et équilibré sont semblables et donner la structure commune des méthodes qui testent ces deux propriétés,

Identifiez le type de parcours qu'on doit utiliser pour tester ces propriétés.

En définissant au besoin d'autres méthodes, écrivez les méthodes pencheAGauche() et equilibre() de la classe ArbreBinaire correspondants aux propriétés énoncées précédemment, de façon que ces méthodes aient une complexité linéaire.

Remarquez que les méthodes pencheAGauche(), taille(), equilibre() et hauteur() ont toutes la même structure.

EXERCICE 6

On définit le poids d'un arbre binaire de la manière suivante :

le poids de l'arbre vide est nul,
si un arbre est non vide, son poids est égal au maximum entre le poids de son sous-arbre gauche et la valeur obtenue en ajoutant 1 au poids de son sous-arbre droit.

Ecrivez la méthode poids() de la classe ArbreBinaire qui, étant donné A un arbre binaire, calcule son poids.

Aucune difficulté.

Deux arbres binaires sont dits isomorphes s'ils sont tous les deux vides ou si l'on peut obtenir l'un en transformation l'autre à l'aide d'une ou plusieurs permutations des deux sous-arbres issus d'un même noeud.

Expliquez dans quel cas la permutation de deux sous-arbres entraîne une diminution de poids. Ecrivez la méthode minimiser() de la classe Poids qui transforme un arbre binaire donné en un arbre binaire isomorphe de poids minimal en utilisant la méthode poids de la question précédente.

Pour permuter deux sous-arbres on utilise les méthodes gauche et droite en écriture.

Ecrivez une nouvelle version de la méthode minimiser() sans utiliser la méthode poids. Quelle est la différence fondamentale entre ces deux versions de la méthode minimiser ?

Inspirez-vous largement de l'exercice précédent.

EXERCICE 7

Un arbre binaire est harmonieux, si, soit l'arbre est vide, soit ses sous-arbres sont harmonieux et la hauteur de l'arbre n'excède pas le double de sa bassesse.

En définissant au besoin une classe interne et une méthode privée, écrivez la méthode estHarmonieux de la classe ArbreBinaire qui teste si un arbre binaire est harmonieux.

Même chose que les deux exercices précédents, mais cette fois on a besoin de deux informations pour décider éventuellement si un arbre est harmonieux.

EXERCICE 8

On désire affiner le parcours en largeur d'un arbre binaire et effectuer un parcours par niveaux. Le parcours par niveau imprime tous les noeuds de l'arbre de même profondeur sur la même ligne, à raison d'une ligne par profondeur.

Ecrivez la méthode parcoursNiveau de la classe ArbreBinaire qui affiche surle flux de sortie tous les éléments de l'arbre suivant l'ordre par niveau.

Modifiez la méthode parcoursLargeur étudiée en cours.

EXERCICE 9

On définit la largeur d'un arbre binaire comme le nombre maximum d'éléments que l'on peut trouver dans l'arbre à la même profondeur. Plus précisément, la largeur L(A) de l'arbre A est définie par :

L(A) = max{ Card(A_p) | 0 £ p £ h(A) }

où A_p est l'ensemble des éléments de A à la profondeur p, Card(E) est le cardinal de E et h(A) la hauteur de A.

Expliquez pourquoi le parcours en profondeur n'est pas adapté à cet algorithme.

Essayez de définir la largeur inductivement sur les sous-arbres d'une arbre.

Ecrivez la méthode largeur de la classe ArbreBinaire qui calcule la largeur de l'arbre.

Inspirez-vous de l'exercice précédent.

EXERCICE 10

Le parcours en largeur peut-il remplacer parfois le parcours en profondeur ?

Reprenez l'exercice 3 en utilisant cette fois le parcours en largeur pour implémenter les méthodes ascendants et tousLesAscendants.

Pour identifier facilement les ascendants masculins à la k-ième génération, il faut connaître les ascendants à la (k-1)-ième génération.

This document was translated from L^AT_EX by H^EV^EA.