TD05 ABR
Télécharger le TD05 ABR en pdf
Pages : 1
Page 1 : Pré-ING2Informatique 3Semestre 1 - 2023/2024TD 05 : Arbres Binaires de RechercheOn rappelle que les commandes à taper dans le terminal pour compiler puis éxécuter votre programme C :— Pour compiler : gcc -o nomexecutable nomprogramme.c— Pour exécuter : ./nomexecutableExercice 1 Question de cours 1. Construire un arbre binaire en insérant les éléments dans cet ordre ; 10, 3, 5, 15, 20, 12, 7, 45, 9.2. Construire un second arbre binaire en insérant les éléments dans l’ordre inverse que précédement. Obtient-on le mêmearbre ?3. Effectuer un parcours infixe sur ces deux arbres. Que remarque-t-on ?4. Supprimer l’élément 5 puis 12 du premier arbre.Exercice 2 Construction d’un ABRLes versions pseudo-code des fonctions demandées aux question 2,3 et 5 sont dans le cours.1. Définir la structure permettant de construire un arbre binaire contenant des entiers.2. Écrire la fonction recherchepArbre a, int e indiquant si l’élément e appartient à l’ABR pointé par a.3. Écrire la fonction recursive insertABRparbre a, int e permettant d’inserer l’élément e dans l’ABR. Attention,l’insertion doit respecter les règles des ABR !4. Écrire une version itérative de la fonction d’insertion écrite précédement.5. Écrire les fonctions nécessaires à la suppression d’un élément dans un ABR.6. Creer un ABR et insérer les éléments suivants dans cet ordre : 10, 3, 5, 15, 20, 12, 7, 45, 9. Afficher l’arbre et vérifierqu’il s’agit bien d’un ABR.7. Vérifier si les élément 13 et 12 appartiennent à l’arbre.8. Supprimer l’élement 15 et vérifier que l’arbre et toujours un ABR.Exercice 3 Test des fonctions de recherche Pour cet exercice, on travaille sur l’arbre construit dans l’exercice précédent.1. Modifier la fonction de recherche recherchepArbre a, int e pour qu’elle retourne le nombre de nœuds qui aurontété parcourus lors de cette recherche. Si un élément n’appartient pas à l’arbre, on affichera que l’élément recherchén’existe pas mais on retournera tout de même le nombre de nœuds visités.2. Proposer une modification de la fonction permettant le parcours Préfixe de l’arbre pour que cette dernière serve àrechercher si un élément existe dans l’arbre en parcourant l’arbre et en s’arrêtant lorsque l’élément est trouvé. Commepour la question précédente, la fonction doit afficher le nombre de nœuds parcourus.3. Aficher le nombre de nœuds parcourus pour les deux fonctions lors de la recherche des éléments suivants : 10, 20, 22.Exercice 4 ABR ?Exercice 5 D’arbre binaire à ABR Proposer une ou plusieurs fonctions qui permettent de construire un ABR à partirExercice 6 Tri de tableau1. Déclarer un tableau de taille 15 et le remplir avec des valeurs saisies différentes.2. Construire un ABR à partir de ce tableau3. Trier ce tableau en vous basant sur un parcours de l’ABR.4. bonus : reprendre la question 1 mais les valeurs du tableau sont aléatoires entre 0 et 100 et ne doivent pas avoir dedoublons !1 Consignes générales : N’oubliez pas pour ce TD comme pour les suivants de vous créer un répertoire consacré au TD et d’enregistrer vos codes dedans. Proposer une fonction permettant de vérifier si un arbre binaire est un ABR ou non. d’un arbre binaire simple.
Pages : 1