Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 Corrigé E.D. Algorithmes et Structures de Données n° 8 Thème : Arbres Binaire

1 Corrigé E.D. Algorithmes et Structures de Données n° 8 Thème : Arbres Binaires de Recherche Exercice VII.1 Arbre Binaire de Recherche Question 1 On utilise un tableau T_ARB pour représenter cet arbre. Donner ce tableau. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 100 70 130 50 90 110 200 20 60 80 - - - 150 250 - 30 Question 2 Ajouter la valeur 115 à cet arbre. Quel est alors l’indice J du tableau tel que T_ARB[J]=115 ? 100 70 130 50 90 110 200 20 60 80 150 250 30 2 115 devient le fils droit de 110. 110 est à la position 6 de T_ARB donc 115 sera à la position (2*6)+1 =13. On mettra donc T_ARB[13] :=115. Question 3 La hauteur est le plus long chemin entre la racine et une feuille. Ici, 4. Question 4 Selon le cours, on remplace 70 par le plus petit élément de son sous-arbre droit : On pourrait aussi supprimer 70 et le remplacer par le plus grand élément de son sous- arbre gauche 100 70 130 50 90 110 200 20 60 80 150 250 30 115 100 70 130 50 90 110 200 20 60 80 150 250 30 3 Question 5 La procédure récursive suivante : procedure lecture (arbre) debut si arbre non vide alors ecrire(valeur_de_la_racine); lecture(sous-arbre droit); lecture(sous-arbre gauche); finsi; fin lecture; exécutée sur l’arbre initial, donne l’affichage : 100-130-200-250-150-110-70-90-80-50-60-20-30 Question 6 Pour obtenir la liste triée par ordre croissant, il suffit de modifier la procédure lecture : procedure lecture (arbre) debut si arbre non vide alors lecture(sous-arbre gauche); ecrire(valeur_de_la_racine); lecture(sous-arbre droit); finsi; fin lecture; Exercice VII.2 Tri fusion 4 6 3 8 5 2 100 70 130 50 90 110 200 20 60 80 150 250 30 4 Question 1 Dessiner l’arborescence associée à la première phase du tri fusion (Division). Question 2 En supposant que le tri se fait « sur place », donner la suite des listes obtenues après chaque modification du tableau lors de la deuxième phase (Fusion). Indiquer pour chaque liste à quel sommet (numéro) de l’arborescence elle correspond. 4 – 6 – 3 – 8 – 5 – 2 4 – 6 – 3 8 – 5 – 2 a g b 4 – 6 3 f c 8 – 5 2 k h 4 6 e d 8 5 j i 2 – 3 – 4 – 5 – 6 – 8 3 – 4 – 6 2 – 5 – 8 a g b 4 – 6 3 f c 5 – 8 2 k h 4 6 e d 8 5 j i uploads/Litterature/ ed-8-corrige 1 .pdf