suivant: À propos de ce
Exercice 8.1 Arbres binaires de recherche.
- Ajouter successivement à l'arbre binaire dessiné ci-dessus les valeurs:
- Dessiner tous les arbres binaires de recherche valués sur
ayant 20 comme valeur à la racine.
- Donner le mot infixe obtenu en écrivant les
valeurs des sommets dans l'ordre de parcours infixe.
- Ecrire une fonction d'ajout d'une valeur
à un arbre binaire de recherche.
- Ecrire deux fonctions qui retournent respectivement la plus
petite et le plus grande valeur contenue dans un arbre binaire de
recherche. Ecrire les fonctions qui suppriment ces deux éléments
- Ecrire une fonction de recherche d'un élément donné dans un
arbre binaire de recherche.
- Ecrire une fonction qui vérifie si un arbre binaire est un arbre binaire de recherche.
Exercice 8.2 Bricolage
Dans une boite à outils, vous disposez de
écrous de diamètres tous différents et
des
boulons correspondants. Mais tout est mélangé et vous voulez apparier chaque
écrou avec le boulon qui lui correspond. Les différences de diamètre entre les écrous
sont tellement minimes qu'il n'est pas possible de d´eterminer à l'oeil nu si un écrou
est plus grand qu'un autre. Il en va de même avec les boulons. Par conséquent, le seul
type d'opération autorisée consiste à essayer un écrou avec un boulon, ce qui peut
amener
trois réponses possibles : soit l'écrou est strictement plus large que le boulon, soit
il est strictement moins large, soit ils ont exactement le même diamètre.
- Ecrire un algorithme simple en O(n2) essais qui appareille chaque écrou avec son
boulon.
- Supposons qu'au lieu de vouloir appareiller tous les boulons et écrous, vous voulez
juste trouver le plus petit écrou et le boulon correspondant. Montrer que vous pouvez résoudre
ce problème en moins de
essais.
suivant: À propos de ce
Maylis Delest
2007-11-12