Scribd
Importer
74 vues2 pages

Serie 10

Le document présente un TD sur les arbres binaires dans le cadre d'un module d'informatique. Il inclut des rappels sur les concepts de base des arbres, ainsi que des exercices pratiques sur l'insertion, les parcours et la manipulation d'un arbre binaire de recherche (ABR). Des fonctions spécifiques à écrire pour gérer les opérations sur un ABR sont également demandées.

Transféré par

Mohamed Trabelsi
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
74 vues2 pages

Serie 10

Le document présente un TD sur les arbres binaires dans le cadre d'un module d'informatique. Il inclut des rappels sur les concepts de base des arbres, ainsi que des exercices pratiques sur l'insertion, les parcours et la manipulation d'un arbre binaire de recherche (ABR). Des fonctions spécifiques à écrire pour gérer les opérations sur un ABR sont également demandées.

Transféré par

Mohamed Trabelsi
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

École préparatoire aux sciences et techniques, Annaba

Année universitaire 2013/2014


Module : Informatique 2

Série de TD no 10 : Arbres

Rappel sur les arbres


1. Donnez une structure de données qui permet de representer un arbre binaire (cette
structure sera utilisé dans les exercices qui suivent).
2. Dans un arbre, comment appelle-t-on le noeud qui n’a pas d’ascendant (parent) ?
3. Dans un arbre, comment appelle-t-on les noeuds qui n’ont pas de descendants
(fils) ?
4. Comment indiquer qu’un arbre est vide ?
5. Quels sont les trois types de parcours d’un arbre ?
6. Quel type de parcours fournit les valeurs d’un ABR en ordre croissant ?

Exercice 1
1. Donnez l’arbre binaire de recherche obtenu en inserant successivement les valeurs
suivantes : 7, 13, 3, 12, 5, 1, 24, 0, 2, 17, 30
2. Donnez le parcours infixe de cet arbre.
3. Donnez le parcours préfixe de cet arbre.
4. Donnez le parcours postfixe de cet arbre.
5. Supprimez le noeud 12 de cet arbre.
6. Supprimez le noeud 13 de cet arbre.
7. Supprimez le noeud 3 de cet arbre.

Exercice 2
1. Écrire une fonction inserer qui permet d’inserer une valeur dans un ABR.
2. Écrire une fonction infixe qui parcours et affiche les valeurs d’un ABR dans un
ordre infixe.
3. Écrire une fonction prefixe qui parcours et affiche les valeurs d’un ABR dans un
ordre préfixe.

1
4. Écrire une fonction postfixe qui parcours et affiche les valeurs d’un ABR dans
un ordre postfixe.
5. Écrire une fonction existe qui teste si une valeur donnée existe dans un ABR. La
fonction retourne true si la valeur existe et false sinon.
6. Écrire une fonction taille qui calcule le nombre de noeuds d’un ABR.
7. Écrire une fonction hauteur qui calcule la hauteur d’un ABR (la hauteur d’un
ABR est le nombre de noeuds entre la feuille la plus eloignée et la racine).
8. Écrire une fonction nombreFeuilles qui retourne le nombre de feuilles d’un ABR.
9. Écrire une fonction max qui retourne la plus grande valeur d’un ABR (supposez
que l’ABR n’est pas vide).
10. Écrire une fonction supprimer qui supprime une valeur d’un ABR.

Vous aimerez peut-être aussi