Dans ce TD, nous allons implémenter des arbres binaires en Python. On choisit de représenter l'arbre vide par la liste vide, et un arbre de racine étiquetée par e et fils fg et fd par la liste [e, fg, fd]
Dans ces exercices, nous allons travailler sur cet arbre
La représentation de l'arbre ci-dessus est :
a = [40, [14, [5, [], []], [4, [], [8, [], []]]], [6, [], []]]
Exercice 1
Hauteur d'un arbre binaire
Écrire une fonction hauteur(a) calculant la hauteur d'un arbre.
Exemple(s)
Résultat
hauteur(a) → la hauteur de a = 3
Solution détaillée
- Principe : La hauteur d'un arbre est la longueur du plus long chemin de la racine à une feuille. On calcule récursivement la hauteur des sous-arbres et on prend le maximum.
#include <stdio.h>
#include <stdlib.h>
// Définition de la structure d'un nœud d'arbre binaire
typedef struct Noeud {
int valeur;
struct Noeud* gauche;
struct Noeud* droit;
} Noeud;
// Fonction pour créer un nouveau nœud
Noeud* creerNoeud(int val) {
Noeud* nouveau = (Noeud*)malloc(sizeof(Noeud));
nouveau->valeur = val;
nouveau->gauche = NULL;
nouveau->droit = NULL;
return nouveau;
}
// Fonction pour calculer la hauteur d'un arbre
int hauteur(Noeud* racine) {
// Cas de base : arbre vide
if (racine == NULL)
return -1; // -1 car la hauteur d'une feuille est 0
// Calcul récursif de la hauteur des sous-arbres
int hauteurGauche = hauteur(racine->gauche);
int hauteurDroit = hauteur(racine->droit);
// La hauteur est 1 + le maximum des hauteurs des sous-arbres
return 1 + (hauteurGauche > hauteurDroit ? hauteurGauche : hauteurDroit);
}
// Construction de l'arbre exemple
Noeud* construireArbre() {
Noeud* racine = creerNoeud(40);
// Sous-arbre gauche
racine->gauche = creerNoeud(14);
racine->gauche->gauche = creerNoeud(5);
racine->gauche->droit = creerNoeud(4);
racine->gauche->droit->droit = creerNoeud(8);
// Sous-arbre droit
racine->droit = creerNoeud(6);
return racine;
}
int main() {
Noeud* arbre = construireArbre();
printf("Hauteur de l'arbre = %d\n", hauteur(arbre));
return 0;
}
Sortie
Hauteur de l'arbre = 3
def hauteur(a):
# Ici le cas de base, ça veut dire l'enfant d'une feuille,
# puisque une feuille n'a pas d'enfant retourner -1
# (1+max(-1,-1)=1+(-1)=0) donc 0 est la hauteur d'une feuille
if len(a) == 0:
return -1
else:
# 1 + le maximum entre l'enfant gauche a[1] et l'enfant droit a[2]
return 1 + max(hauteur(a[1]), hauteur(a[2]))
# Arbre exemple
a = [40, [14, [5, [], []], [4, [], [8, [], []]]], [6, [], []]]
print("Hauteur de a =", hauteur(a))
Sortie
Hauteur de a = 3
Exercice 2
Nombre de nœuds
Écrire une fonction calculant le nombre de nœuds d'un arbre binaire.
Exemple(s)
Résultat
nb_noeuds(a) → Nombre de nœuds de a = 6
Les nœuds sont : 40, 14, 5, 4, 8, 6 → total = 6
Solution détaillée
- Principe : Le nombre de nœuds est la somme des nœuds des sous-arbres plus le nœud courant.
#include <stdio.h>
#include <stdlib.h>
typedef struct Noeud {
int valeur;
struct Noeud* gauche;
struct Noeud* droit;
} Noeud;
Noeud* creerNoeud(int val) {
Noeud* nouveau = (Noeud*)malloc(sizeof(Noeud));
nouveau->valeur = val;
nouveau->gauche = NULL;
nouveau->droit = NULL;
return nouveau;
}
// Fonction pour compter le nombre de nœuds
int nbNoeuds(Noeud* racine) {
// Cas de base : arbre vide
if (racine == NULL)
return 0;
// Compter récursivement : 1 (nœud courant) + nœuds gauche + nœuds droit
return 1 + nbNoeuds(racine->gauche) + nbNoeuds(racine->droit);
}
Noeud* construireArbre() {
Noeud* racine = creerNoeud(40);
// Sous-arbre gauche
racine->gauche = creerNoeud(14);
racine->gauche->gauche = creerNoeud(5);
racine->gauche->droit = creerNoeud(4);
racine->gauche->droit->droit = creerNoeud(8);
// Sous-arbre droit
racine->droit = creerNoeud(6);
return racine;
}
int main() {
Noeud* arbre = construireArbre();
printf("Nombre de nœuds de a = %d\n", nbNoeuds(arbre));
return 0;
}
Sortie C
Nombre de nœuds de a = 6
def nb_noeuds(a):
# Ici le cas de base, ça veut dire l'enfant d'une feuille,
# puisque une feuille n'a pas d'enfant retourner 0
if len(a) == 0:
return 0
else:
# 1 (nœud lui même) + nombre de nœuds de sous arbre gauche a[1]
# + nombre de nœuds de sous arbre droit a[2]
return 1 + nb_noeuds(a[1]) + nb_noeuds(a[2])
# Arbre exemple
a = [40, [14, [5, [], []], [4, [], [8, [], []]]], [6, [], []]]
print("Nombre de nœuds de a =", nb_noeuds(a))
Sortie Python
Nombre de nœuds de a = 6
Exercice 3
Nombre de feuilles
Écrire une fonction calculant le nombre de feuilles d'un arbre binaire.
Exemple(s)
Résultat
nb_feuilles(a) → Nombre de feuilles de a = 3
Les feuilles sont : 5, 8, 6 → total = 3
Solution détaillée
- Principe : Une feuille est un nœud sans enfant. On compte récursivement les feuilles dans les sous-arbres.
#include <stdio.h>
#include <stdlib.h>
typedef struct Noeud {
int valeur;
struct Noeud* gauche;
struct Noeud* droit;
} Noeud;
Noeud* creerNoeud(int val) {
Noeud* nouveau = (Noeud*)malloc(sizeof(Noeud));
nouveau->valeur = val;
nouveau->gauche = NULL;
nouveau->droit = NULL;
return nouveau;
}
// Fonction pour compter le nombre de feuilles
int nbFeuilles(Noeud* racine) {
// Cas de base : arbre vide
if (racine == NULL)
return 0;
// Si c'est une feuille (pas d'enfants)
if (racine->gauche == NULL && racine->droit == NULL)
return 1;
// Sinon, compter les feuilles dans les sous-arbres
return nbFeuilles(racine->gauche) + nbFeuilles(racine->droit);
}
Noeud* construireArbre() {
Noeud* racine = creerNoeud(40);
// Sous-arbre gauche
racine->gauche = creerNoeud(14);
racine->gauche->gauche = creerNoeud(5);
racine->gauche->droit = creerNoeud(4);
racine->gauche->droit->droit = creerNoeud(8);
// Sous-arbre droit
racine->droit = creerNoeud(6);
return racine;
}
int main() {
Noeud* arbre = construireArbre();
printf("Nombre de feuilles de a = %d\n", nbFeuilles(arbre));
return 0;
}
Sortie
Nombre de feuilles de a = 3
def nb_feuilles(a):
# Ici le cas de base, ça veut dire l'enfant d'une feuille,
# puisque une feuille n'a pas d'enfant retourner 0
if len(a) == 0:
return 0
# si il s'agit d'une feuille [val,[],[]]
# le nœud n'a pas d'enfant gauche [] et d'enfant droit []
elif len(a[1]) + len(a[2]) == 0:
return 1
else:
# Sinon retourner le nombre d'enfants de sous arbre gauche a[1]
# et sous arbre droit a[2]
return nb_feuilles(a[1]) + nb_feuilles(a[2])
# Arbre exemple
a = [40, [14, [5, [], []], [4, [], [8, [], []]]], [6, [], []]]
print("Nombre de feuilles de a =", nb_feuilles(a))
Sortie
Nombre de feuilles de a = 3
Vérification
Les feuilles de l'arbre sont : 5, 8, 6 → total = 3 ✓
Sortie
// La sortie apparaîtra ici…
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.