Scribd
Importer
23 vues2 pages

Exercices sur les arbres en C

Le document présente trois exercices portant sur les arbres binaires et les structures de données arborescentes. Le premier exercice décrit un arbre binaire représenté sous forme de tableau et demande de le dessiner, définir sa structure et implémenter des fonctions de parcours. Le deuxième exercice porte sur la représentation d'un arbre n-aire sous forme d'arbre binaire et demande d'implémenter des fonctions de parcours. Le troisième exercice demande de construire différents types d'arbres (recherche, tas, AVL) à partir d'une liste de nombres.

Transféré par

mohamedsenani5
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
23 vues2 pages

Exercices sur les arbres en C

Le document présente trois exercices portant sur les arbres binaires et les structures de données arborescentes. Le premier exercice décrit un arbre binaire représenté sous forme de tableau et demande de le dessiner, définir sa structure et implémenter des fonctions de parcours. Le deuxième exercice porte sur la représentation d'un arbre n-aire sous forme d'arbre binaire et demande d'implémenter des fonctions de parcours. Le troisième exercice demande de construire différents types d'arbres (recherche, tas, AVL) à partir d'une liste de nombres.

Transféré par

mohamedsenani5
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é M’hamed Bougara Boumerdes - Faculté des Sciences

Département Informatique
Ingenieur informatique, 2ème année
Algorithmique et Complexité
———————————————————————
Série TD No 2 : Les arbres
———————————————————————

Exercice 1:
Soit le tableau suivant qui représente en langage C un arbre binaire T . Chaque élément de ce tableau T contient
les champs : inf o, gauche et droit qui représentent la valeur du nœud, l’indice du fils gauche et l’indice du fils
droit, respectivement.

23 2 3 5 7 11 13 37 41 19
-1 4 3 -1 -1 9 -1 8 6 -1
-1 5 0 -1 -1 -1 2 1 -1 -1

La première colonne représente le nœud dont le champ info est 23 , le champ gauche est -1 et le champ droit
est -1. La valeur -1 pour l’indice du fils gauche ou fils droit indique son absence.

1. Dessiner l’arbre binaire T et donner sa taille.

2. Donner la partie définition et déclaration de la structure T en langage C.

3. Determiner la recine de l’arbre T , puis ecrire une fonction qui détermine la racine de l’arbre T .

4. Donner en langage C la définition et la déclaration d’une nouvelle structure qui contient l’indice de la racine.

5. Ecrire une procédure qui liste toutes les feuilles de l’arbre T .

6. Donner le résultat du parcours de l’arbre T : (a) en ordre infixe, (b) en ordre préfixe, et (c) en ordre postfixe.

Exercice 2 :
Soit l’arbre n-aire appellé A et représenté comme suit :

Page 1/2
Cet arbre est représentée par un arbre Binaire B ou chaque noeud prossède un pointeur vers le fils gauche
et un autre vers le prochain frère.

1. Donner la définition et la déclaration de la structure B.

2. Donner l’arbre B.

3. Donner la fonction qui permet d’afficher les feuilles de l’arbre A en parcourant l’arbre binaire B.

4. Donner la fonction qui permet d’afficher tous les fils d’un noued donné à partir de l’arbre binaire B.

5. Donner la fonction qui permet d’afficher les élements de A selon un parcours postfixe en parcourant l’arbre
binaire B.

Exercice 3 :
Soit la liste L des éléments suivante : 7, 6, 8, 2, 4, 3, 10.

1. Construire à partir de la liste L un arbre binaire de recherche B.

2. Construire à partir de la liste L un arbre Tas min B-Tas-min.

3. Construire à partir de la liste L un arbre Tas max B-Tas-max.

4. Construire à partir de la liste L un arbre AVL B-AVL.

5. Donner la définition de la structure AVL.

6. Donner la fonction qui permet de faire une rotation droite sur un noeud donné.

7. Donner la fonction qui permet de faire une rotation gauche sur un noeud donné.

Page 2/2

Vous aimerez peut-être aussi