#include <stdio.
h>
#include <stdlib.h>
#include <limits.h>
//Q1
typedef struct Noeud {
int valeur;
struct Noeud* gauche;
struct Noeud* droite;
} Noeud;
//Q2
Noeud* cree_arbre(int valeur, Noeud* gauche, Noeud* droite) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
nouveauNoeud->valeur = valeur;
nouveauNoeud->gauche = gauche;
nouveauNoeud->droite = droite;
return nouveauNoeud;
//Q3
int nombre_de_noeuds(Noeud* racine) {
if (racine == NULL) {
return 0;
return 1 + nombre_de_noeuds(racine->gauche) + nombre_de_noeuds(racine->droite);
//Q4
Noeud* insere(Noeud* racine, int valeur) {
if (racine == NULL) {
return cree_arbre(valeur, NULL, NULL);
if (valeur <= racine->valeur) {
racine->gauche = insere(racine->gauche, valeur);
} else {
racine->droite = insere(racine->droite, valeur);
return racine;
//Q5
void affiche_arbre(Noeud* racine) {
if (racine != NULL) {
affiche_arbre(racine->gauche);
printf("%d ", racine->valeur);
affiche_arbre(racine->droite);
void affiche_arbre_ngd(Noeud* racine) {
if (racine != NULL) {
printf("%d ", racine->valeur);
affiche_arbre_ngd(racine->gauche);
affiche_arbre_ngd(racine->droite);
//Q6
void affiche_arbre_largeur(Noeud* racine) {
if (racine == NULL) {
return;
}
Noeud* file[100];
int debut = 0, fin = 0;
file[fin++] = racine;
while (debut < fin) {
Noeud* noeud = file[debut++];
printf("%d ", noeud->valeur);
if (noeud->gauche != NULL) {
file[fin++] = noeud->gauche;
if (noeud->droite != NULL) {
file[fin++] = noeud->droite;
//Q7
void detruit_arbre(Noeud* racine) {
if (racine != NULL) {
detruit_arbre(racine->gauche);
detruit_arbre(racine->droite);
free(racine);
}
Noeud* trouve_noeud(Noeud* racine, int valeur) {
if (racine == NULL || racine->valeur == valeur) {
return racine;
if (valeur < racine->valeur) {
return trouve_noeud(racine->gauche, valeur);
return trouve_noeud(racine->droite, valeur);
//Q8
void affiche_arbre2(Noeud* racine) {
if (racine == NULL) {
printf("_");
} else {
printf("{");
affiche_arbre2(racine->gauche);
printf(",%d,", racine->valeur);
affiche_arbre2(racine->droite);
printf("}");
//Q9
int est_ABR(Noeud* racine, int min, int max) {
if (racine == NULL) {
return 1;
}
if (racine->valeur < min || racine->valeur > max) {
return 0;
return est_ABR(racine->gauche, min, racine->valeur - 1) &&
est_ABR(racine->droite, racine->valeur + 1, max);
int verifier_ABR(Noeud* racine) {
return est_ABR(racine, INT_MIN, INT_MAX);
//Q10
int main() {
Noeud* racine = NULL;
racine = insere(racine, 4);
racine = insere(racine, 3);
racine = insere(racine, 1);
racine = insere(racine, 6);
racine = insere(racine, 6);
racine = insere(racine, 9);
racine = insere(racine, 7);
printf("Affichage en profondeur GND: ");
affiche_arbre(racine);
printf("\n");
printf("Affichage en profondeur NGD: ");
affiche_arbre_ngd(racine);
printf("\n");
printf("Affichage en largeur : ");
affiche_arbre_largeur(racine);
printf("\n");
printf("Nombre de noeuds est : %d\n", nombre_de_noeuds(racine));
if (verifier_ABR(racine)) {
printf("L'arbre est un arbre de recherche binaire\n");
} else {
printf("L'arbre n'est pas un arbre de recherche binaire\n");
int valeur_recherchee ;
printf("entrer la valeur a rechercher:\n");
scanf("%d",&valeur_recherchee);
Noeud* noeud;
noeud =trouve_noeud(racine, valeur_recherchee);
if (noeud != NULL) {
printf("Noeud avec valeur %d existe\n", valeur_recherchee);
} else {
printf("Noeud avec valeur %d n'est existe pas\n", valeur_recherchee);
}
printf("Structure de l'arbre : ");
affiche_arbre2(racine);
printf("\n");
detruit_arbre(racine);
return 0;
