IT FORMATION
IT FORMATION
- Accueil
- Algorithmique
- Arbres et graphes
- Arbres binaires de recherche
Rubriques
Algorithmique
- Contributions
Recherche personnalisée
Actualité du Web
Arbres binaires de recherche
/*Structure de données: Arbre binaire de recherche*/
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
/* Définition de la structure Noeud d'un arbre*/
struct Noeud{
int d;
struct Noeud* succ_gauche;
struct Noeud* succ_droit;
};
/*Définition du type TArbre, une structure de type TArbre est définie
par un pointeur sur la racine de l'arbre*/
typedef struct Noeud* TArbre;
/* Fonction ajouterNoeud: crée un Noeud et l'ajoute dans
un arbre binaire de recherche.*/
void ajouterNoeud(TArbre* arbre, int val)
{ struct Noeud* nouveauNoeud;
TArbre pArbre; /* Variable utilisée pour parcourir l'arbre*/
/* Création du nouveau noeud dont la valeur de d est égale à val*/
nouveauNoeud=(struct Noeud*)malloc(sizeof(struct Noeud));
nouveauNoeud->d=val;
nouveauNoeud->succ_gauche=NULL;
nouveauNoeud->succ_droit=NULL;
/* Ajout du nouveau noeud dans l'arbre*/
pArbre=*arbre;
if (*arbre==NULL)
*arbre=nouveauNoeud; /* si c'est un nouvel arbre alors le nouveau noeud sera
la racine de cet arbre*/
else
while(TRUE)/* On crée une boucle infinie, la sortie de la sortie sera réalisée
par l'appel de l'instruction break; */
{ if (val< pArbre->d) /* Alors le nouveau doit être ajouté à gauche*/
{ if (pArbre->succ_gauche==NULL){
/* Donc le nouveau noeud doit être ajouté dans cet emplacement et on doit
quitter la boucle while*/
pArbre->succ_gauche=nouveauNoeud;
break;
}
else
pArbre=pArbre->succ_gauche;
}
else
{ /* donc val est supérieure à (*pArbre)->d, donc on ajoute le
nouveau noeud à droite */
if (pArbre->succ_droit==NULL){
/* Donc le nouveau noeud doit être ajouté dans cet emplacement et on doit
quitter la boucle while*/
pArbre->succ_droit=nouveauNoeud;
break;
}
else
pArbre=pArbre->succ_droit;
}
}
}
/*
*/
void afficherArbreRec(TArbre a )
{
if (a==NULL) return;
afficherArbreRec (a->succ_gauche );
printf ("%d", a->d);
afficherArbreRec (a->succ_droit);
}
void indenter (int i)
{
printf ("\n");
for ( ; i > 0; i--) printf ("-");
}
/* Affichage avec indentation*/
void afficher2ArbreRec(TArbre a, int indentation )
{
if (a==NULL) return;
afficher2ArbreRec (a->succ_gauche ,indentation + 1);
indenter (indentation );
printf ("%d", a->d );
afficher2ArbreRec (a->succ_droit,indentation + 1);
}
/**/
void afficher3ArbreRec(TArbre a )
{
if (a==NULL) return;
afficherArbreRec (a->succ_gauche );
afficherArbreRec (a->succ_droit);
printf ("%d", a->d);
}
void libererMemoire(TArbre a )
{
if (a==NULL) return;
libererMemoire (a->succ_gauche );
libererMemoire (a->succ_droit);
free(a);
}
int main(void){
TArbre arbre=NULL;
int i,d;
for(i=0; i<=6;i++){
scanf("%d",&d);
ajouterNoeud(&arbre,d);}
afficher3ArbreRec(arbre);
libererMemoire(arbre);
return 0;
}
