Scribd
Importer
14 vues1 page

Arbres arithmétiques et algorithmes avancés

Le document présente un exercice sur les arbres arithmétiques et binaires dans le cadre d'un cours d'algorithmique avancée. Il demande de déterminer la valeur d'une expression, d'implémenter un arbre sous forme chainée, de proposer une stratégie de parcours, et d'analyser la complexité de l'algorithme. Un second exercice concerne la modélisation d'un arbre binaire dans un tableau, avec des questions sur sa structure, ses feuilles, et la racine.

Transféré par

Chaima Mestiri
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
14 vues1 page

Arbres arithmétiques et algorithmes avancés

Le document présente un exercice sur les arbres arithmétiques et binaires dans le cadre d'un cours d'algorithmique avancée. Il demande de déterminer la valeur d'une expression, d'implémenter un arbre sous forme chainée, de proposer une stratégie de parcours, et d'analyser la complexité de l'algorithme. Un second exercice concerne la modélisation d'un arbre binaire dans un tableau, avec des questions sur sa structure, ses feuilles, et la racine.

Transféré par

Chaima Mestiri
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

Université de Sousse

Institut Supérieur d’Informatique et des Technologies de Communication de Hammam Sousse – 2ème année
Cycle Ingénieur en Téléinformatique

TD - Algorithmique avancee
Theme : Les Arbres

EXERCICE N°1.

On considère l'arbre arithmétique suivant :


Déterminer la valeur de cette expression. *
1. Donner une implémentation sous forme chainée de
cet arbre. + 3
2. Quelle est la stratégie de parcours à adopter pour
évaluer cet arbre ? Justifier votre réponse.
5
3. Ecrire un algorithme qui permet de déterminer la 1
valeur d’une expression représentée sous forme
d'un arbre arithmétique.
4. Appliquer votre algorithme sur l'arbre précédent.
5. Déterminer la complexité de votre algorithme en fonction de h, la hauteur de l'arbre. En déduire une
borne inférieure et une borne supérieure pour cette complexité en fonction de n, le nombre de nœuds
dans l'arbre.

EXERCICE N°2.

Soit un arbre binaire implémenté dans un tableau de trois lignes dans lequel pour chaque indice i les trois
lignes contiennent dans l’ordre :
 L’élément associé au nœud i
 L’indice dans le tableau où se trouve le fils gauche du nœud i
 L’indice dans le tableau où se trouve le fils droit du nœud i.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a + b + c * d * e - f + g / h
0 12 0 10 0 5 0 2 0 9 0 1 0 13 0
0 6 0 14 0 7 0 4 0 11 0 3 0 15 0

Dans ce tableau, la valeur 0 modélise la valeur NIL.


1. Ecrire la structure de données modélisant cet arbre binaire.
2. Quelles sont les feuilles de l’arbre ?
3. Ecrire un algorithme qui permet de retrouver la racine de l’arbre.
4. Dessiner l’arbre correspondant et calculer sa hauteur
ISITCom / US © L. B. Romdhane page 1 sur 1

Vous aimerez peut-être aussi