Exercice 1
Arbre SommeEnfants
Écrivez une fonction qui retourne vrai si l'arbre binaire donné est SommeEnfants sinon faux. Un SommeEnfants est un arbre binaire où la valeur d'un nœud est égale à la somme des nœuds présents dans son sous-arbre gauche et son sous-arbre droit. Un arbre vide est SommeEnfants et la somme d'un arbre vide peut être considérée comme 0. Un nœud feuille est également considéré comme SommeEnfants.
Exemple(s)
Résultat
SommeEnfants(a) → True
Solution détaillée
- Principe : Pour vérifier la propriété SommeEnfants, il faut calculer récursivement la somme des sous-arbres et vérifier que la valeur du nœud est égale à la somme des valeurs de ses sous-arbres.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.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 utilitaire pour calculer la somme des valeurs d'un arbre
int somme(Noeud* racine) {
if (racine == NULL)
return 0;
return somme(racine->gauche) + racine->valeur + somme(racine->droit);
}
// Fonction qui vérifie si l'arbre est SommeEnfants
bool estSommeEnfants(Noeud* racine) {
// Si le nœud est vide, retourner true
if (racine == NULL)
return true;
// Si c'est une feuille, retourner true
if (racine->gauche == NULL && racine->droit == NULL)
return true;
// Calculer la somme des sous-arbres
int sommeGauche = somme(racine->gauche);
int sommeDroit = somme(racine->droit);
// Vérifier la propriété pour le nœud courant et récursivement pour les enfants
if (racine->valeur == sommeGauche + sommeDroit &&
estSommeEnfants(racine->gauche) &&
estSommeEnfants(racine->droit)) {
return true;
}
return false;
}
int main() {
// Construction de l'arbre exemple: [17, [6, [3, [3, [], []], []], []], [5, [], []]]
Noeud* racine = creerNoeud(17);
// Sous-arbre gauche
racine->gauche = creerNoeud(6);
racine->gauche->gauche = creerNoeud(3);
racine->gauche->gauche->gauche = creerNoeud(3);
// Sous-arbre droit
racine->droit = creerNoeud(5);
printf("Test SommeEnfants : %s\n", estSommeEnfants(racine) ? "True" : "False");
return 0;
}
Sortie
Test SommeEnfants : True
# Une fonction utilitaire pour obtenir la somme des valeurs
# dans un arbre avec la racine "a"
def somme(a):
# Enfant d'une feuille !
if a == []:
return 0
else:
# somme des valeurs à gauche+racine+valeurs à droite
return somme(a[1]) + a[0] + somme(a[2])
# renvoie True si la propriété SommeEnfant est
# vraie pour le nœud donné et ses deux enfants
def SommeEnfant(a):
# Si le nœud est vide [], retournez true
if a == []:
return True
# S'il s'agit d'un nœud feuille, retournez true
if a[1] == [] and a[2] == []:
return True
else:
# somme des éléments de sous arbre gauche
gauche = somme(a[1])
# somme des éléments de sous arbre droit
droit = somme(a[2])
# si le nœud et ses deux enfants satisfont la propriété,
# retourne True sinon False
if a[0] == (gauche + droit) and \
(SommeEnfant(a[1]) == True and SommeEnfant(a[2]) == True):
return True
return False
a0 = [17, [6, [3, [3, [], []], []], []], [5, [], []]]
print("SommeEnfants(a0) =", SommeEnfant(a0))
Sortie
SommeEnfants(a0) = True
Exercice 2
Arbre complet
Écrire une fonction créant un arbre complet (tous les niveaux sont remplis) d'une hauteur donnée. On s'efforcera de distribuer des étiquettes de façon injective.
Exemple(s)
Résultat
complet(2,1) → [1, [2, [4, [], []], [5, [], []]], [3, [6, [], []], [7, [], []]]]
Solution détaillée
- Principe : Un arbre complet de hauteur h a tous ses niveaux remplis. On peut le construire récursivement en attribuant des valeurs selon un parcours préfixe.
#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 créer un arbre complet de hauteur donnée
Noeud* complet(int hauteur, int racine) {
if (hauteur == 0) {
return creerNoeud(racine);
} else {
Noeud* noeud = creerNoeud(racine);
noeud->gauche = complet(hauteur - 1, 2 * racine);
noeud->droit = complet(hauteur - 1, 2 * racine + 1);
return noeud;
}
}
// Fonction pour afficher l'arbre (format Python)
void afficherArbre(Noeud* racine) {
if (racine == NULL) {
printf("[]");
return;
}
printf("[%d, ", racine->valeur);
afficherArbre(racine->gauche);
printf(", ");
afficherArbre(racine->droit);
printf("]");
}
int main() {
printf("complet(2, 1) →\n");
Noeud* arbre = complet(2, 1);
afficherArbre(arbre);
printf("\n");
return 0;
}
Sortie C
complet(2, 1) → [1, [2, [4, [], []], [5, [], []]], [3, [6, [], []], [7, [], []]]]
def complet(hauteur, racine):
if hauteur == 0:
return [racine, [], []]
else:
return [racine,
complet(hauteur-1, 2*racine),
complet(hauteur-1, 2*racine+1)]
print("complet(2,1) =", complet(2, 1))
Sortie
complet(2,1) = [1, [2, [4, [], []], [5, [], []]], [3, [6, [], []], [7, [], []]]]
Exercice 3
Miroir d'un arbre
Écrire une fonction calculant le miroir d'un arbre donné (au sens d'une symétrie par rapport à un axe vertical).
Exemple(s)
Résultat
a = [1, [2, [4, [], []], [5, [], []]], [3, [6, [], []], [7, [], []]]] miroir(a) → [1, [3, [7, [], []], [6, [], []]], [2, [5, [], []], [4, [], []]]]
Solution détaillée
- Principe : Le miroir d'un arbre s'obtient en échangeant récursivement les sous-arbres gauche et droit.
#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 créer le miroir d'un arbre
Noeud* miroir(Noeud* racine) {
if (racine == NULL)
return NULL;
Noeud* nouveau = creerNoeud(racine->valeur);
nouveau->gauche = miroir(racine->droit);
nouveau->droit = miroir(racine->gauche);
return nouveau;
}
// Fonction pour construire l'arbre exemple
Noeud* construireArbreExemple() {
Noeud* racine = creerNoeud(1);
racine->gauche = creerNoeud(2);
racine->gauche->gauche = creerNoeud(4);
racine->gauche->droit = creerNoeud(5);
racine->droit = creerNoeud(3);
racine->droit->gauche = creerNoeud(6);
racine->droit->droit = creerNoeud(7);
return racine;
}
// Fonction pour afficher l'arbre (format Python)
void afficherArbre(Noeud* racine) {
if (racine == NULL) {
printf("[]");
return;
}
printf("[%d, ", racine->valeur);
afficherArbre(racine->gauche);
printf(", ");
afficherArbre(racine->droit);
printf("]");
}
int main() {
Noeud* arbre = construireArbreExemple();
printf("Arbre original :\n");
afficherArbre(arbre);
printf("\n\n");
Noeud* arbreMiroir = miroir(arbre);
printf("Miroir de l'arbre :\n");
afficherArbre(arbreMiroir);
printf("\n");
return 0;
}
Sortie C
Arbre original : [1, [2, [4, [], []], [5, [], []]], [3, [6, [], []], [7, [], []]]] Miroir de l'arbre : [1, [3, [7, [], []], [6, [], []]], [2, [5, [], []], [4, [], []]]]
def miroir(a):
if len(a) == 0:
return []
else:
return [a[0], miroir(a[2]), miroir(a[1])]
# Arbre exemple
a = [1, [2, [4, [], []], [5, [], []]], [3, [6, [], []], [7, [], []]]]
print("Arbre original :", a)
print("Miroir :", miroir(a))
Sortie
Arbre original : [1, [2, [4, [], []], [5, [], []]], [3, [6, [], []], [7, [], []]]] Miroir : [1, [3, [7, [], []], [6, [], []]], [2, [5, [], []], [4, [], []]]]
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.