Université Moulay Ismaïl
2ème Année 2021-2022
ENSAM – Meknès
Programmation avancée en C++
TD4 - Arbres
A- Arbres binaires
Exercice 1
Un arbre binaire peut être construit si l’on connait les résultats, au moins, de 2 parcours, à condition qu'un parcours
soit toujours un parcours Infixe et que le second soit un parcours Préfixe ou un parcours Postfixe.
Un parcours Infixe détermine les nœuds enfants gauche et droit de l'arbre binaire. Un parcours Préfixe ou Postfixe
détermine le nœud racine de l'arbre binaire. Par conséquent, il existe deux manières de créer un arbre binaire, qui sont :
- Parcours infixe et parcours préfixe.
- Parcours infixe et parcours postfixe.
1- Construire manuellement l’arbre binaire correspondant aux 2 parcours suivants :
• Parcours Infixé : 5 , 15 , 18 , 20 , 25 , 30 , 35 , 40 , 45 , 50 , 60.
• Parcours Préfixé : 30 , 20 , 15 , 5 , 18 , 25 , 40 , 35 , 50 , 45 , 60.
2- Ecrire une fonction qui construit un arbre binaire à partir de 2 tableaux contenant respectivement le parcours infixe
et le parcours préfixe.
Exercice 2
1- Ecrire une fonction estFeuille qui reçoit un nœud N et teste si ce dernier est feuille ou non.
2- Ecrire une fonction listerFeuilles qui reçoit le nœud racine racine d’un arbre binaire et affiche les
valeurs de ses feuilles en utilisant le parcours préfixé.
3- Ecrire une fonction nbFeuilles qui reçoit le nœud racine racine d’un arbre binaire et retourne le nombre
de ses feuilles.
4- Ecrire un programme de test.
Exercice 3
1- Écrire une fonction noeudExiste qui reçoit la racine d’un arbre binaire racine et un entier x0 et teste si
ce dernier existe dans l’arbre ou non.
2- Ecrire un programme de test.
Exercice 4
3- Écrire une fonction maxArbre qui reçoit la racine d’un arbre binaire racine et retourne la plus grande
valeur de ses éléments.
4- Ecrire un programme de test.
Exercice 5
1- Écrire une fonction hauteurArbre qui reçoit la racine d’un arbre binaire racine et retourne sa hauteur.
2- Ecrire un programme de test.
__________________________________________________________________________________________
A. Ahmadi 1/3 ENSAM-Meknès
Exercice 6
Étant donné deux arbres binaires S et T, On voudrait vérifier si le premier arbre est un sous-arbre du second. Un sous-
arbre d'un arbre T est un arbre S composé d'un nœud dans T et de tous ses descendants dans T. Le sous-arbre
correspondant au nœud racine est l'arbre entier ; le sous-arbre correspondant à tout autre nœud est appelé un sous-arbre
propre.
1- Ecrire une fonction arbBinIdentiques qui permet de vérifier si 2 arbres, ayant respectivement les racines
racine1 et racine2, sont identiques ou non.
2- Ecrire une fonction estSousArbre qui reçoit deux racines de 2 arbres binaires T et S et vérifie si S est un
sous-arbre de T ou non.
3- Ecrire un programme de test.
B- Arbres binaires de recherche (BST)
Exercice 7
1- Construire manuellement un arbre binaire de recherche correspondant à la séquence ABFCDGK. Trouver
ses deux parcours préfixés et postfixé.
2- Ecrire un programme qui réalise les opérations de la première question. Comparer les résultats.
Exercice 8
1- Créer manuellement un arbre de recherche binaire en insérant les éléments : 50, 34, 23, 87, 100, 67, 43, 51, 18
et 95.
2- Donner manuellement le nouvel arbre de recherche binaire après chaque suppression des éléments : 100, 34 et
95, 50.
3- Ecrire un programme qui réalise les deux tâches précédentes et comparer les résultats.
Exercice 9
4- Écrire une fonction rechElemBST qui reçoit la racine d’un arbre binaire de recherche racine et un entier
x0 et retourne l’adresse du nœud contenant la valeur x0. Si x0 ne se trouve pas dans l’arbre, la fonction
retournera NULL.
5- Ecrire un programme de test.
Exercice 10
Étant donné deux arbres binaires, On voudrait vérifier si le premier arbre est un sous-arbre du second. Un sous-arbre
d'un arbre T est un arbre S composé d'un nœud dans T et de tous ses descendants dans T. Le sous-arbre correspondant
au nœud racine est l'arbre entier ; le sous-arbre correspondant à tout autre nœud est appelé un sous-arbre propre.
1- Ecrire une fonction arbBinIdentiques qui reçoit 2 racines racine1 et racine2 de deux arbres binaires
et vérifie si ces derniers sont identiques ou non.
2- Ecrire une fonction estSousArbre qui reçoit 2 racines T et S de deux arbres binaires et vérifie si S est sous-
arbre de T ou non.
3- Ecrire un programme de test.
Exercice 11
Ecrire une fonction arbBinVersBST qui reçoit la racine d’un arbre binaire racine et convertit ce dernier en un arbre
binaire de recherche (BST). La conversion doit être effectuée de manière à conserver la structure originale de l’arbre
binaire initial.
Indication :
__________________________________________________________________________________________
A. Ahmadi 2/3 ENSAM-Meknès
1. Créer un tableau temporaire tab et y stocker le parcours Infixe de l'arbre binaire.
2. Trier par ordre croissant le tableau temporaire tab.
3. Refaire un parcours Infixe de l’arbre binaire et y copier les éléments du tableau tab un par un.
C- Arbres équilibrés
Exercice 12
Créer un arbre AVL en insérant les éléments suivants : 60, 10, 21, 30, 19, 120, 100, 80, 20. Indiquer après chaque
étape, les nouveaux facteurs d’équilibre des nœuds concernés.
Exercice 13
On voudrait calculer le nombre minimum de nœuds dans un arbre AVL de hauteur h, noté par nbMinNoeudsAVL(h).
1- Montrer que nbMinNoeudsAVL(1)=1 et nbMinNoeudsAVL(2)=2.
2- Trouver une relation de récurrence entre nbMinNoeudsAVL(h), nbMinNoeudsAVL(h-1) et
nbMinNoeudsAVL(h-2).
3- Ecrire une fonction récursive nbMinNoeudsAVL qui reçoit la hauteur h d’un arbre AVL et retourne le nombre
minimum de ses nœuds.
4- Ecrire un programme de test.
__________________________________________________________________________________________
A. Ahmadi 3/3 ENSAM-Meknès