Exercice 1
Somme des feuilles d'un arbre binaire
Étant donné un arbre binaire, trouvez la somme de toutes les feuilles.
Exemple(s)
Résultat
somme_feuilles(abr) La somme des nœuds feuilles est : 15
Les feuilles sont : 3, 2, 4, 1, 5 → somme = 3+2+4+1+5 = 15
Solution détaillée
- Principe : Parcourir l'arbre récursivement et additionner les valeurs des nœuds qui n'ont pas d'enfants (feuilles).
#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 somme des feuilles
int sommeFeuilles(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 racine->valeur;
// Sinon, retourner la somme des feuilles des sous-arbres
return sommeFeuilles(racine->gauche) + sommeFeuilles(racine->droit);
}
int main() {
// Construction de l'arbre exemple
Noeud* racine = creerNoeud(40);
racine->gauche = creerNoeud(14);
racine->droit = creerNoeud(6);
racine->gauche->gauche = creerNoeud(5);
racine->gauche->droit = creerNoeud(4);
racine->droit->gauche = creerNoeud(1);
racine->droit->droit = creerNoeud(5);
racine->gauche->gauche->gauche = creerNoeud(3);
racine->gauche->gauche->droit = creerNoeud(2);
int somme = sommeFeuilles(racine);
printf("La somme des nœuds feuilles est : %d\n", somme);
return 0;
}
def somme_feuilles(a):
# Cas de base : arbre vide
if len(a) == 0:
return 0
# Si c'est une feuille [val, [], []]
if len(a[1]) + len(a[2]) == 0:
return a[0]
# Sinon, somme des feuilles des sous-arbres
return somme_feuilles(a[1]) + somme_feuilles(a[2])
# Représentation de l'arbre : [valeur, sous-arbre gauche, sous-arbre droit]
a2 = [40,
[14,
[5, [3, [], []], [2, [], []]],
[4, [], []]],
[6,
[1, [], []],
[5, [], []]]]
print("La somme des nœuds feuilles est :", somme_feuilles(a2))
Sortie
La somme des nœuds feuilles est : 15
Exercice 2
Feuilles au même niveau
Étant donné un arbre binaire, vérifiez si toutes les feuilles sont au même niveau ou non.
Exemple(s)
T1 :
40
/ \
14 6
/ \ / \
5 4 1 5
/
3
Les feuilles sont aux niveaux : 3 (niveau 3), 4 (niveau 2), 1 (niveau 2), 5 (niveau 2) → pas tous au même niveau
T2 :
40
/ \
14 6
/ \ / \
5 4 1 5
Les feuilles sont toutes au niveau 2 → toutes au même niveau
Résultat
memeniveau(T1) → False memeniveau(T2) → True
Solution détaillée
- Principe : Parcourir l'arbre en gardant trace du niveau. À la première feuille rencontrée, enregistrer son niveau. Vérifier que toutes les autres feuilles sont au même niveau.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.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;
}
// Variable globale pour stocker le niveau de référence
int niveauReference = -1;
bool memeniveau(Noeud* racine, int niveau) {
// Arbre vide
if (racine == NULL)
return true;
// Si c'est une feuille
if (racine->gauche == NULL && racine->droit == NULL) {
// Première feuille rencontrée
if (niveauReference == -1) {
niveauReference = niveau;
return true;
}
// Vérifier que le niveau correspond
return niveau == niveauReference;
}
// Vérifier récursivement les sous-arbres
return memeniveau(racine->gauche, niveau + 1) &&
memeniveau(racine->droit, niveau + 1);
}
void resetNiveauReference() {
niveauReference = -1;
}
int main() {
// Construction de T1 (feuilles à différents niveaux)
Noeud* t1 = creerNoeud(40);
t1->gauche = creerNoeud(14);
t1->droit = creerNoeud(6);
t1->gauche->gauche = creerNoeud(5);
t1->gauche->droit = creerNoeud(4);
t1->droit->gauche = creerNoeud(1);
t1->droit->droit = creerNoeud(5);
t1->gauche->gauche->gauche = creerNoeud(3);
// Construction de T2 (toutes les feuilles au même niveau)
Noeud* t2 = creerNoeud(40);
t2->gauche = creerNoeud(14);
t2->droit = creerNoeud(6);
t2->gauche->gauche = creerNoeud(5);
t2->gauche->droit = creerNoeud(4);
t2->droit->gauche = creerNoeud(1);
t2->droit->droit = creerNoeud(5);
printf("Test T1 : ");
printf(memeniveau(t1, 0) ? "True\n" : "False\n");
resetNiveauReference();
printf("Test T2 : ");
printf(memeniveau(t2, 0) ? "True\n" : "False\n");
return 0;
}
Sortie C
Test T1 : False Test T2 : True
niveau = -1
def memeniveau(a, l):
global niveau
# Arbre vide
if len(a) == 0:
return True
# Si c'est une feuille [val, [], []]
if len(a[1]) + len(a[2]) == 0:
if niveau < 0:
niveau = l
return True
return l == niveau
# Vérifier récursivement les sous-arbres
return memeniveau(a[1], l+1) and memeniveau(a[2], l+1)
# T1 : feuilles à différents niveaux
t1 = [40,
[14,
[5, [3, [], []], []],
[4, [], []]],
[6,
[1, [], []],
[5, [], []]]]
# T2 : toutes les feuilles au même niveau
t2 = [40,
[14,
[5, [], []],
[4, [], []]],
[6,
[1, [], []],
[5, [], []]]]
print("Test T1 :", memeniveau(t1, 0))
niveau = -1 # Réinitialiser
print("Test T2 :", memeniveau(t2, 0))
Sortie
Test T1 : False Test T2 : True
Exercice 3
Vérification de cousins
Étant donné un arbre binaire et deux nœuds "a" et "b", déterminez si les deux nœuds sont cousins l'un de l'autre ou non.
Définition : Deux nœuds sont cousins l'un de l'autre s'ils sont au même niveau et ont des parents différents.
Exemple(s)
40
/ \
14 6
/ \ / \
5 4 1 5
/ \
3 2
Résultat
cousins(4, 1) → True (même niveau 2, parents différents : 14 et 6) cousins(3, 5) → False (même niveau ? 3 est niveau 3, 5 est niveau 2 → niveaux différents)
Solution détaillée
- Principe : Trouver le chemin de la racine à chaque nœud. Comparer la longueur des chemins (niveau) et l'avant-dernier élément (parent).
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.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;
}
// Structure pour stocker un chemin
typedef struct {
int valeurs[100];
int taille;
} Chemin;
// Fonction pour trouver le chemin vers un nœud
bool trouverChemin(Noeud* racine, int val, Chemin* chemin) {
if (racine == NULL)
return false;
// Ajouter le nœud courant au chemin
chemin->valeurs[chemin->taille] = racine->valeur;
chemin->taille++;
// Si c'est le nœud recherché
if (racine->valeur == val)
return true;
// Chercher dans les sous-arbres
if (trouverChemin(racine->gauche, val, chemin) ||
trouverChemin(racine->droit, val, chemin))
return true;
// Pas trouvé, retirer le nœud courant
chemin->taille--;
return false;
}
bool cousins(Noeud* racine, int val1, int val2) {
if (racine == NULL)
return false;
Chemin chemin1 = { .taille = 0 };
Chemin chemin2 = { .taille = 0 };
// Trouver les chemins
trouverChemin(racine, val1, &chemin1);
trouverChemin(racine, val2, &chemin2);
// Vérifier les conditions
// 1. Même niveau (même longueur de chemin)
// 2. Parents différents (avant-dernier élément différent)
// 3. Les nœuds ne sont pas le même nœud
if (chemin1.taille == chemin2.taille && chemin1.taille >= 2) {
return chemin1.valeurs[chemin1.taille - 2] != chemin2.valeurs[chemin2.taille - 2] &&
chemin1.valeurs[chemin1.taille - 1] != chemin2.valeurs[chemin2.taille - 1];
}
return false;
}
int main() {
// Construction de l'arbre
Noeud* racine = creerNoeud(40);
racine->gauche = creerNoeud(14);
racine->droit = creerNoeud(6);
racine->gauche->gauche = creerNoeud(5);
racine->gauche->droit = creerNoeud(4);
racine->droit->gauche = creerNoeud(1);
racine->droit->droit = creerNoeud(5);
racine->gauche->gauche->gauche = creerNoeud(3);
racine->gauche->gauche->droit = creerNoeud(2);
printf("cousins(4, 1) → %s\n", cousins(racine, 4, 1) ? "True" : "False");
printf("cousins(3, 5) → %s\n", cousins(racine, 3, 5) ? "True" : "False");
printf("cousins(2, 3) → %s (mêmes parents)\n", cousins(racine, 2, 3) ? "True" : "False");
return 0;
}
Sortie C
cousins(4, 1) → True cousins(3, 5) → False cousins(2, 3) → False (mêmes parents)
def chemin_vers_noeud(a, chemin, val):
"""Trouve le chemin de la racine vers le nœud val"""
# Si l'arbre est vide
if a == []:
return False
# Ajouter le nœud dans le chemin
chemin.append(a[0])
# Si la racine a la même valeur que val
if a[0] == val:
return True
# Vérifier si val se trouve dans le sous-arbre gauche ou droit
if chemin_vers_noeud(a[1], chemin, val) or chemin_vers_noeud(a[2], chemin, val):
return True
# S'il n'est pas présent, supprimer la racine du chemin
chemin.pop()
return False
def cousins(a, val1, val2):
"""Vérifie si deux nœuds sont cousins"""
if a == []:
return False
chemin1 = [] # Chemin vers val1
chemin2 = [] # Chemin vers val2
# Calculer les chemins
chemin_vers_noeud(a, chemin1, val1)
chemin_vers_noeud(a, chemin2, val2)
# Vérifier les conditions :
# 1. Même niveau (même longueur de chemin)
# 2. Parents différents (avant-dernier élément différent)
# 3. Les nœuds ne sont pas le même nœud
if len(chemin1) == len(chemin2) and len(chemin1) >= 2:
return chemin1[-2] != chemin2[-2] and chemin1[-1] != chemin2[-1]
return False
# Arbre exemple
a2 = [40,
[14,
[5, [3, [], []], [2, [], []]],
[4, [], []]],
[6,
[1, [], []],
[5, [], []]]]
print("cousins(4, 1) →", cousins(a2, 4, 1))
print("cousins(3, 5) →", cousins(a2, 3, 5))
print("cousins(2, 3) →", cousins(a2, 2, 3), "(mêmes parents)")
Sortie Python
cousins(4, 1) → True cousins(3, 5) → False cousins(2, 3) → False (mêmes parents)
Explication
- 4 et 1 : Tous deux au niveau 2, parents différents (14 et 6) → cousins ✅
- 3 et 5 : 3 est au niveau 3, 5 est au niveau 2 → niveaux différents ❌
- 2 et 3 : Même niveau 3, mais mêmes parents (5) → frères, pas cousins ❌
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.