Scribd
Importer
10 vues1 page

Manipulation et Parcours des Arbres Binaires

Le document présente une série d'exercices sur la manipulation des arbres binaires, incluant la création d'une classe pour les arbres et l'implémentation de divers parcours. Il aborde également des concepts tels que les arbres binaires de recherche (ABR) et les méthodes d'ajout d'éléments. Enfin, il propose des défis supplémentaires comme l'affichage textuel des arbres et l'application de fonctions aux nœuds.

Transféré par

Frédéric Gava
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
10 vues1 page

Manipulation et Parcours des Arbres Binaires

Le document présente une série d'exercices sur la manipulation des arbres binaires, incluant la création d'une classe pour les arbres et l'implémentation de divers parcours. Il aborde également des concepts tels que les arbres binaires de recherche (ABR) et les méthodes d'ajout d'éléments. Enfin, il propose des défis supplémentaires comme l'affichage textuel des arbres et l'application de fonctions aux nœuds.

Transféré par

Frédéric Gava
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Manipulation des arbres binaires

Exercice 0 : Dessinez un arbre qui contiendrez des informations de votre choix et qui vous
semblerez pertinent (pas de limite de domaine, Bio, Physique, Droit, Lettres, Médecine, etc.)

Exercice 1 : Reprendre les méthodes statiques du cours et en faite des méthodes de l’objet arbre lui-
même. Écrire donc une classe complète pour les arbres.

Exercice 2 : Rajouter les autres parcours en profondeur (infixe, suffixe) en récursif ; Écrire un main
avec quelques arbres pour comparer. Essayer un parcours en profondeur infixe mais en itératif (avec
une boucle while).

Exercice 3 : Quel arbres sont ABR ? Justifiez !

Exercice 4 : Est-ce que tout arbre peut être mis sous la forme d’un arbre binaire ?

Exercice 5 : Est-ce que votre arbre de l’exercice 0 pourrait être mis sous la forme d’un ABR ?
Justifiez.

Exercice 6 : Construire dans un main, un arbre binaire de recherche ; puis affichez ces valeurs avec
différents parcours. L’un des parcours a une propriété remarquable pour les ABR. Laquelle ? Quelle
pourrait être l’utilité ?

Exercice 7 : Ecrire une méthode « map » qui applique un calcul/fonction (donné en paramètre) à
tout les nœuds et feuilles de l’arbre. Regardez le cours sur les streams du premier semestre pour
vous rappeler comment on passe une fonction en paramètre.

Exercice 8 : Écrire une méthode qui permet d’ajouter un élément « x » à un arbre binaire de
recherche (en tant que nouvelle feuille) ; Voici ce qu’il faut faire :
Si la valeur « x » est plus grande que la valeur de nœud, alors il faut continuer à insérer dans
l’arbre droit ;
Dans le cas contraire ; allez dans l’arbre gauche
Si il n’y a pas de nœud (arbre vide), alors rajouter une nouvelle feuille à l’arbre
Essayez une (a) une méthode récursif ; (b) une méthode impérative (itérative)

Exercice 9 : (Difficile) Écrivez une méthode (static ou non) permettant d’afficher les arbres binaire
(en mode texte) comme ci-dessous. Exemple pour l’arbre (a)
___10
_6___15
2_3_12_18
On décale donc les nœuds avec des « _ » pour qu’ils soient mieux centrés. Pour ce faire, on suppose
un « _ » d’espace entre 2 feuilles ; Un nœud, fils ajoute aussi un « _ ». On décale le nœuds d’un fils
droit (p. ex. Le nœud 15) avec des « _ » et on en ajoute autant qu’il y a de noeuds/feuilles(+1) pour
le frère (nœud 6) et qu’il y a de petits fils à gauche (ici, il n’y a que la feuille 12). Essayez d’abord à
la main; Pensez aussi à un parcours en largeur...

Vous aimerez peut-être aussi