#include <stdio.
h>
#include <stdlib.h>
#include <limits.h>
typedef struct Noeud {
int valeur;
struct Noeud* gauche;
struct Noeud* droite;
} Noeud;
Noeud* cree_arbre(int valeur, Noeud* gauche, Noeud* droite) {
Noeud* nouveau = (Noeud*)malloc(sizeof(Noeud));
nouveau->valeur = valeur;
nouveau->gauche = gauche;
nouveau->droite = droite;
return nouveau;
}
int nombre_de_noeuds(Noeud* arbre) {
if (arbre == NULL) return 0;
return 1 + nombre_de_noeuds(arbre->gauche) + nombre_de_noeuds(arbre->droite);
}
Noeud* insere(Noeud* arbre, int valeur) {
if (arbre == NULL) return cree_arbre(valeur, NULL, NULL);
if (valeur < arbre->valeur) {
arbre->gauche = insere(arbre->gauche, valeur);
} else {
arbre->droite = insere(arbre->droite, valeur);
}
return arbre;
}
void affiche_arbre_profondeur_GND(Noeud* arbre) {
if (arbre != NULL) {
affiche_arbre_profondeur_GND(arbre->gauche);
printf("%d ", arbre->valeur);
affiche_arbre_profondeur_GND(arbre->droite);
}
}
void affiche_arbre_profondeur_NGD(Noeud* arbre) {
if (arbre != NULL) {
printf("%d ", arbre->valeur);
affiche_arbre_profondeur_NGD(arbre->gauche);
affiche_arbre_profondeur_NGD(arbre->droite);
}
}
void affiche_arbre_largeur(Noeud* arbre) {
if (arbre == NULL) return;
Noeud** queue = (Noeud**)malloc(100 * sizeof(Noeud*)); // Assurez-vous
d'allouer correctement la mémoire
int debut = 0, fin = 0;
queue[fin++] = arbre;
while (debut < fin) {
Noeud* noeud = queue[debut++];
printf("%d ", noeud->valeur);
if (noeud->gauche != NULL) queue[fin++] = noeud->gauche;
if (noeud->droite != NULL) queue[fin++] = noeud->droite;
}
free(queue);
}
void detruit_arbre(Noeud* arbre) {
if (arbre != NULL) {
detruit_arbre(arbre->gauche);
detruit_arbre(arbre->droite);
free(arbre);
}
}
Noeud* trouve_noeud(Noeud* arbre, int valeur) {
if (arbre == NULL || arbre->valeur == valeur) return arbre;
if (valeur < arbre->valeur) return trouve_noeud(arbre->gauche, valeur);
return trouve_noeud(arbre->droite, valeur);
}
void affiche_arbre2(Noeud* arbre) {
if (arbre == NULL) {
printf("_");
return;
}
printf("{");
affiche_arbre2(arbre->gauche);
printf(",%d,", arbre->valeur);
affiche_arbre2(arbre->droite);
printf("}");
}
int est_abr(Noeud* arbre, int min_val, int max_val) {
if (arbre == NULL) return 1;
if (arbre->valeur <= min_val || arbre->valeur >= max_val) return 0;
return est_abr(arbre->gauche, min_val, arbre->valeur) && est_abr(arbre->droite,
arbre->valeur, max_val);
}
int main() {
Noeud* arbre = cree_arbre(4,
cree_arbre(3,
cree_arbre(1, NULL, NULL),
NULL
),
cree_arbre(6,
cree_arbre(6, NULL, NULL),
cree_arbre(9,
cree_arbre(7, NULL, NULL),
NULL
)
)
);
printf("Affichage en profondeur (GND) :\n");
affiche_arbre_profondeur_GND(arbre);
printf("\n");
printf("Affichage en profondeur (NGD) :\n");
affiche_arbre_profondeur_NGD(arbre);
printf("\n");
printf("Affichage en largeur :\n");
affiche_arbre_largeur(arbre);
printf("\n");
printf("Nombre de nœuds : %d\n", nombre_de_noeuds(arbre));
int valeur_recherchee = 0;
Noeud* noeud_trouve = trouve_noeud(arbre, valeur_recherchee);
if (noeud_trouve) {
printf("\nNoeud avec la valeur %d trouvé.\n", valeur_recherchee);
} else {
printf("\nLe noeud avec la valeur %d est non trouve.\n",
valeur_recherchee);
}
printf("\nAffichage de la structure de l'arbre :\n");
affiche_arbre2(arbre);
printf("\n");
if (est_abr(arbre, INT_MIN, INT_MAX)) {
printf("\nL'arbre est un ABR.\n");
} else {
printf("\nL'arbre n'est pas un ABR.\n");
}
detruit_arbre(arbre);
return 0;
}
