Arbre dictionnaire
Toto_15l
Messages postés
5
Date d'inscription
mercredi 5 janvier 2005
Statut
Membre
Dernière intervention
30 mars 2009
-
6 avril 2005 à 12:38
julienbj Messages postés 452 Date d'inscription jeudi 4 décembre 2003 Statut Membre Dernière intervention 19 décembre 2008 - 17 avril 2005 à 15:42
julienbj Messages postés 452 Date d'inscription jeudi 4 décembre 2003 Statut Membre Dernière intervention 19 décembre 2008 - 17 avril 2005 à 15:42
1 réponse
julienbj
Messages postés
452
Date d'inscription
jeudi 4 décembre 2003
Statut
Membre
Dernière intervention
19 décembre 2008
15
17 avril 2005 à 15:42
17 avril 2005 à 15:42
Définition de la structure représentant l'arbre:
typedef struct s_arbre
{
struct s_arbre *droite, *gauche;
char *info;
} t_arbre;
On utilisera un pointeur sur l'arbre que l'on nommera arbre.
On considèrera que l'arbre est ordonné avec la relation suivante:
arbre->gauche->info < arbre->info<=arbre->droite->info
Fonction de recherche dans l'arbre:
int recherche(t_arbre *arbre, char *chaine)
{
if (arbre == NULL)
return NULL;
else if (stricmp(arbre->info, chaine) == 0)
return 1;
else if (stricmp(arbre->info, chaine) < 0)
return recherche(arbre->droite, chaine);
else
return recherche(arbre->gauche, chaine);
}
Insertion d'un élément de façon ordonné:
void CreerFeuille(char *chaine, t_arbre **arbre)
{
*arbre = (t_arbre*) malloc(1 * sizeof(t_arbre));
//Regarder si strlen + 1 ou seulement strlen, je m'en rappelle jamais
(*arbre)->info = (char*) malloc((strlen(chaine) + 1)*sizeof(char));
strcpy((*arbre)->info, chaine);
(*arbre)->gauche = NULL;
(*arbre)->droite = NULL;
}
void Insertion(t_arbre **arbre, char *chaine)
{
if (*arbre == NULL)
CreerFeuille(chaine, arbre);
else if (stricmp(chaine, (*arbre)->info) >= 0)
Insertion((*arbre)->droite, chaine);
else
Insertion((*arbre)->gauche, chaine);
}
Suppression d'un élément:
void SupprimerNoeud(t_arbre **arbre)
{
t_arbre *p, *q;
p = *arbre;
if ((*arbre)->droite)
{
q = (*arbre)->droite;
while (q->gauche)
q = q->gauche;
q->gauche = p->gauche;
(*arbre) = (*arbre)->gauche;
}
else
(*arbre) = (*arbre)->gauche;
free(p->info);
free(p);
}
void Supprimer(t_arbre **arbre, char *chaine)
{
if (*arbre)
{
if (stricmp((*arbre)->info, chaine) == 0)
SupprimerNoeud(arbre);
else if (stricmp((*arbre)->info, chaine) > 0)
Supprimer(&((*arbre)->gauche), chaine);
else
Supprimer(&((*arbre)->droite), chaine);
}
}
Voila, je pense que ça devrait marcher!
Le seul doute reste sur les tests de stricmp ou il faut tester pour
voir si ils sont dans le bon sens, mais j'y ai fait attention, et ça
devrait aller!
C'est de la traduction en C d'un prog pascal, alors si il y a problème de pointeur, tu essaies d'adapter, le principe est la!
Vive le C
Tchao
[mailto:julienbj@hotmail.com Savon]
typedef struct s_arbre
{
struct s_arbre *droite, *gauche;
char *info;
} t_arbre;
On utilisera un pointeur sur l'arbre que l'on nommera arbre.
On considèrera que l'arbre est ordonné avec la relation suivante:
arbre->gauche->info < arbre->info<=arbre->droite->info
Fonction de recherche dans l'arbre:
int recherche(t_arbre *arbre, char *chaine)
{
if (arbre == NULL)
return NULL;
else if (stricmp(arbre->info, chaine) == 0)
return 1;
else if (stricmp(arbre->info, chaine) < 0)
return recherche(arbre->droite, chaine);
else
return recherche(arbre->gauche, chaine);
}
Insertion d'un élément de façon ordonné:
void CreerFeuille(char *chaine, t_arbre **arbre)
{
*arbre = (t_arbre*) malloc(1 * sizeof(t_arbre));
//Regarder si strlen + 1 ou seulement strlen, je m'en rappelle jamais
(*arbre)->info = (char*) malloc((strlen(chaine) + 1)*sizeof(char));
strcpy((*arbre)->info, chaine);
(*arbre)->gauche = NULL;
(*arbre)->droite = NULL;
}
void Insertion(t_arbre **arbre, char *chaine)
{
if (*arbre == NULL)
CreerFeuille(chaine, arbre);
else if (stricmp(chaine, (*arbre)->info) >= 0)
Insertion((*arbre)->droite, chaine);
else
Insertion((*arbre)->gauche, chaine);
}
Suppression d'un élément:
void SupprimerNoeud(t_arbre **arbre)
{
t_arbre *p, *q;
p = *arbre;
if ((*arbre)->droite)
{
q = (*arbre)->droite;
while (q->gauche)
q = q->gauche;
q->gauche = p->gauche;
(*arbre) = (*arbre)->gauche;
}
else
(*arbre) = (*arbre)->gauche;
free(p->info);
free(p);
}
void Supprimer(t_arbre **arbre, char *chaine)
{
if (*arbre)
{
if (stricmp((*arbre)->info, chaine) == 0)
SupprimerNoeud(arbre);
else if (stricmp((*arbre)->info, chaine) > 0)
Supprimer(&((*arbre)->gauche), chaine);
else
Supprimer(&((*arbre)->droite), chaine);
}
}
Voila, je pense que ça devrait marcher!
Le seul doute reste sur les tests de stricmp ou il faut tester pour
voir si ils sont dans le bon sens, mais j'y ai fait attention, et ça
devrait aller!
C'est de la traduction en C d'un prog pascal, alors si il y a problème de pointeur, tu essaies d'adapter, le principe est la!
Vive le C
Tchao
[mailto:julienbj@hotmail.com Savon]