Créer arbre..

Signaler
Messages postés
63
Date d'inscription
dimanche 18 mars 2007
Statut
Membre
Dernière intervention
27 avril 2013
-
Messages postés
149
Date d'inscription
mercredi 28 mars 2007
Statut
Membre
Dernière intervention
17 mai 2007
-
Salut à tous , ben voilà j'été entrain de faire un petit programme en c++
Il s'agit de deffirentes fonctions pour manipuler un arbre binnair de recherche mais le problemme c'est que je ne sais pas comment crée un arbre en c++ pour tester ces derniers sachant que l'implumantation est chainée ..
Voilà la strructure que j'ai consu en c++

typedef struct noeud
{
char info;
int cle; // la clé ça consernne l'ordre dans l'arbre pour toute cle plus grande que la racine les noeuds viennent sur l'adroit et pour le vice-versa les noeuds seront sur l'agauch//
struct noeud *fg;
struct noeud *fd;
}NOEUD,Arber;
Et voilà les fonction que j'ai ecri jusqu'à present:

/****************************************************/
void Inisialisation(Arber *a)
{
a=NULL;
}
/************************************************************/
NOEUD* PreparerNoeud(int CLE, char element)
{
NOEUD *a;
a = (NOEUD*)malloc(sizeof(NOEUD));
if (a!= NULL)
{
a->cle=CLE;
a->info=element;
a->fd=NULL;
a->fg=NULL;
}
return a;
}
/*************************************************/
BOOLEEN AjouterNoeud(Arber *a,NOEUD *n)
{
if (a==NULL)
{
a=n;
return VRAI;
}
else
{
if(n->cle == a->cle)
return FAUX;
if (n->cle < a->cle )
return AjouterNoeud( a->fg,n);
else
return AjouterNoeud( a->fg,n);
}
}
/********************************************/
BOOLEEN AjouterElement(Arber *a,char element,int CLE)
{
NOEUD *n;
n=PreparerNoeud( CLE, element);
if (n ==NULL)
return FAUX;
else
{
if (AjouterNoeud(a,n)==VRAI)
return VRAI;
else
{
return FAUX;
free (n);
}
}


}
/***************************************/
BOOLEEN ExisteCle(Arber *a,int CLE)
{
if (a==NULL) return FAUX;
else
{
if (a->cle= CLE) return VRAI;
if (CLE< a->cle) return ExisteCle(a->fg, CLE);
if (CLE> a->cle) return ExisteCle(a->fd, CLE);
}

}/*************************************/
NOEUD* ExtraireMax(Arber *a)
{
NOEUD *n;
if (a==NULL) return NULL;
else
{
if (a->fd==NULL)
{
n=a;
a=a->fg;
return n;
free(n);
}

}
ExtraireMax( a->fd);
}
/*****************************************************/
Il m'etais dificile de ecrire un programme qui crée un arbre pour vue que l'implumantation est chainnée , quelqu'un a une idée ?
Et merci..
Allé salut

9 réponses

Messages postés
149
Date d'inscription
mercredi 28 mars 2007
Statut
Membre
Dernière intervention
17 mai 2007
1
Salut,
Ton code est pas indenté, déjà.
Ensuite:
-AjouterNoeud(Arber *a,NOEUD *n) <---- probleme ici
- Donc il faut Arbre ** a, et pas Arbre * a
- Changer tout le reste en fonction de ca forcement du coup ca va changer peut-etre AjouterNoeud aussi, qui prendrait deux etoiles.


@++


Ps: sinon Ton code est bien apparemment mais il faudra que tu l'indentes c'est plus facile a lire.
Corrige les fautes d'ortographe aussi, notamment Arbre au lieu de Arber
**  Mais l'erreur principale c'est ce AjouterNoeud(Arbre ** a, Noeud * n)
Car c'est ca qui fait que tu peux pas creer un arbre
Messages postés
63
Date d'inscription
dimanche 18 mars 2007
Statut
Membre
Dernière intervention
27 avril 2013

salut
Merci pour ta reponse mais c'est pas que je cherche exatement .
Car cette arbre que je veux créer est une arbre binnaire de recherche les element sont ordonnés selon un critère "les cle inferieur a celle de la racine viennent sur l'agauche par contre qui sont superieurs seront sur l'adroit ".
j'espére que tu as une sollution pour ça?
Salut
Messages postés
149
Date d'inscription
mercredi 28 mars 2007
Statut
Membre
Dernière intervention
17 mai 2007
1
Salut,

Ce que je te disais, c'est que ton programme ne marcherait certainement pas si tu le testais car tu as des bugs que je t'ai dit. Maintenant, le principe d'arbre de recherche, tu sembles l'avoir bien implemente, mais ca t'aiderait d'avoir un code qui marche pour le tester. Et puis ca aiderait d'avoir un code indenté  pour le lire aussi. En deux mots :
1) corrige les erreurs que je t'ai dit
 2) indente ton code, je regarderais, mais je pense que c'est pas mal ton arbre de recherche sinon
Messages postés
63
Date d'inscription
dimanche 18 mars 2007
Statut
Membre
Dernière intervention
27 avril 2013

Salut ...
Alors merci encore ..
ben là jé suis ...j'utulise la fonction Insérernoeud et çà marche mais il reste un problem avec le contraire "supprimmer la racine" j'ai cré une qui s'excute normalement ("pas de faute de syntaxe") ...
alors le problem etape par etape c'est que :
1/D'abord j'ai cre une arbre
2/j'ai appellé la fonction affiche(infixe postfixe ou prefixe)..oa fonctionne normalement , l'affichage est bon .
3/j'appell e la fonction supprimmer racine 'excutation normale '
4/là i l uara problem "j'appelle la fonction affiche a nouveau le compilateur m'envoi un message incomprehenssible pour moi" ...le message est le suivant:


********
Exception non gérée : System.AccessViolationException: Tentative de lecture ou d
'écriture de mémoire protégée. Cela indique souvent qu'une autre mémoire est end
ommagée.
à affich_infixe_croissant(noeud* a) dans c:\documents and settings\gued\mes d
ocuments\visual studio 2005\projects\essai\essai\essai.cpp:ligne 180
à affich_infixe_croissant(noeud* a) dans c:\documents and settings\gued\mes d
ocuments\visual studio 2005\projects\essai\essai\essai.cpp:ligne 180
à main() dans c:\documents and settings\gued\mes documents\visual studio 2005
\projects\essai\essai\essai.cpp:ligne 278
Appuyez sur une touche pour continuer...********



T'auras pas une idée sur ça!?
Messages postés
149
Date d'inscription
mercredi 28 mars 2007
Statut
Membre
Dernière intervention
17 mai 2007
1
Salut,

Oui, il y'a segfault.
Donc, le probleme que tu as est un probleme de memoire, tu dois mal gerer tes pointeurs a un moment ou à un autre. Pour le resoudre, il faudrait que:

1) tu colles tout ton code corrigé (il n'y a pas de fonction supprimerRacine dans le code que tu as indiqué)

2) tu mets pas tout le code comme un gros bloc mais une instruction par ligne, et des espaces entre les fonctions, sinon on ne s'y retrouve pas
Donc.
C'est normal que tu aies ce genre d'erreurs, on ne peut pas faire un programme parfait des le debut avec les pointeurs
 Bon courage
@++
Messages postés
63
Date d'inscription
dimanche 18 mars 2007
Statut
Membre
Dernière intervention
27 avril 2013

Salut.....
Alors merci infiniment pour ta reponse et pour le code de mon programme le voilà complet: 
 
// essai.cpp : fichier projet principal.

 

 

#include

<stdafx.h>#include

<stdio.h>#include

<malloc.h>/*DECLARATION DES TYPES*/

typedef

struct noeud{

int cle;

struct noeud *fg;

struct noeud *fd;}NOEUD,Arber;

/* Declaration de Type NOEUD et Arber*/typedef

enum BOOLEEN { FAUX=0, VRAI=1 };
/*Declaration du type BOOLEEN*//*****************************************************************************************/

/*Principe de la Fonction: initialisation d'une arbre */

/*les entrées: une arbre, */

/*la sortie: VOID */

/*****************************************************************************************/

void

Inisialisation(Arber *a){

a=NULL;

}

/*****************************************************************************************/

/*Principe de la Fonction: preparer un noeud et retourn l'adresse de ce noeud */

/*les entres: une cle */

/*la sortie: type NOEUD */

/*****************************************************************************************/

NOEUD* PreparerNoeud(

int CLE){

NOEUD *a;

a = (NOEUD*)malloc(

sizeof(NOEUD));

if (a!= NULL){

a->cle=CLE;

a->fd=NULL;

a->fg=NULL;

}

return a;}

/*****************************************************************************************/

/*Principe de la Fonction: Ajouter un noeud retourn booleen si la cle du noeud existe */

/*déjà il retourne FAUX sinon il retourn VRAI */

/*les entres: un arbre, */

/*la sortie: VOID */

/*****************************************************************************************/

BOOLEEN AjouterNoeud(Arber *a,NOEUD *n)

{

if (a==NULL){

a=n;

return VRAI;}

else{

if(n->cle == a->cle)

return FAUX;

if (n->cle < a->cle )

return AjouterNoeud( a->fg,n);

else

return AjouterNoeud( a->fg,n);}

}

/*****************************************************************************************/

/*Principe de la Fonction: initialisation d'un element (une clé) retourn FAUX */

/*si la clé existe déjà ou ya pas d'espace memoire */

/*les entres: un arbre, */

/*la sortie: VOID */

/*****************************************************************************************/

BOOLEEN AjouterElement(Arber *a,

int CLE){

NOEUD *n;

n=PreparerNoeud( CLE);

if

(n ==NULL)

return FAUX;
else

{

if (AjouterNoeud(a,n)==VRAI)

return VRAI;

else{

return FAUX;

delete n;}

}

 

}

/*****************************************************************************************/

/*Principe de la Fonction: initialisation d'une arbre */

/*les entres: un arbre, */

/*la sortie: VOID */

/*****************************************************************************************/

BOOLEEN ExisteCle(Arber *a,

int CLE){

if (a==NULL)
return FAUX;

else{

if (a->cle== CLE)
return VRAI;

if (CLE< a->cle)
return ExisteCle(a->fg, CLE);

if (CLE> a->cle)
return ExisteCle(a->fd, CLE);}

}

/*****************************************************************************************/

/*Principe de la Fonction: initialisation d'une arbre */

/*les entres: un arbre, */

/*la sortie: VOID */

/*****************************************************************************************/

NOEUD* ExtraireMax(Arber *a)

{

NOEUD *n;

if (a==NULL)
return NULL;

else{

if (a->fd==NULL){

n=a;

a=a->fg;

return n;

delete n;

}

}

ExtraireMax( a->fd);

}

/*****************************************************************************************/

/*Principe de la Fonction: initialisation d'une arbre */

/*les entres: un arbre, */

/*la sortie: VOID */

/*****************************************************************************************/

BOOLEEN SupprimmerRacine(Arber *a)

{

NOEUD *n;

if (a==NULL){

return FAUX;}

n=a;

if (n->fg==NULL) {

a=n->fd;

}

else{

if (n->fd==NULL) {

a=n->fg;

}

else{

a=ExtraireMax(n->fg);

a->fd=n->fd;

a->fg=n->fg;

}

}

delete n;

return VRAI;

}

/*****************************************************************************************/

/*Principe de la Fonction: initialisation d'une arbre */

/*les entres: un arbre, */

/*la sortie: VOID */

/*****************************************************************************************/

BOOLEEN ExtraireElement(Arber *a,

int CLE){

char e;

if (a==NULL)
return FAUX;

if (CLE< a->cle)
return ExtraireElement(a->fg, CLE);

if (CLE> a->cle)
return ExtraireElement(a->fd, CLE);e=a->cle;

return SupprimmerRacine(a);

}

/*****************************************************************************************/

/*Principe de la Fonction: initialisation d'une arbre */

/*les entres: un arbre, */

/*la sortie: VOID */

/*****************************************************************************************/

void

InsererNoeud(Arber *a,NOEUD *n){

if

(n->clecle){

if (a->fg!=NULL)
return InsererNoeud( a->fg,n);

elsea->fg=n;

}

else

{

if (n->cle>a->cle){

if (a->fd!=NULL)
return InsererNoeud( a->fd,n);

else a->fd=n;

}

else printf (
"\ncette cle existe déjà");}

}

/*****************************************************************************************/

/*Principe de la Fonction: initialisation d'une arbre */

/*les entres: un arbre, */

/*la sortie: VOID */

/*****************************************************************************************/

void

affich_infixe_croissant(Arber *a){

if(a!=NULL){

affich_infixe_croissant(a->fg);

printf(

"%d\n",a->cle);affich_infixe_croissant(a->fd);

}

}

/*****************************************************************************************/

/*Principe de la Fonction: initialisation d'une arbre */

/*les entres: un arbre, */

/*la sortie: VOID */

/*****************************************************************************************/

void

affich_pre(Arber *racine){

if (racine==NULL)

return;printf(

"\n%d ",racine->cle);affich_pre(racine->fg);

affich_pre(racine->fd);

}

/*****************************************************************************************/

/*Principe de la Fonction: initialisation d'une arbre */

/*les entres: un arbre, */

/*la sortie: VOID */

/*****************************************************************************************/

void

affich_pos(Arber *racine){

if (racine==NULL)

return;

affich_pos(racine->fg);

affich_pos(racine->fd);

printf(

"\n%d ",racine->cle);}

Arber* ExtraireSousAD(Arber *a)

{

if

(a==NULL)
return NULL;
else

{

return

a->fd;a->fd=NULL;

}

}

//****************************************/

Arber* ExtraireSousAG(Arber *a)

{

if

(a==NULL)
return NULL;
else

{

return

a->fg;a->fg=NULL;

}

}

/*****************************************************************************************/

/*Principe de la Fonction: initialisation d'une arbre */

/*les entres: un arbre, */

/*la sortie: VOID */

/*****************************************************************************************/

void

affich_menu(){

printf(

"\t\tManipulation d'arbre binaire:\n\n");printf(

"\t1-> Creation d'un arbre ordonne(OBLIGATOIR).\n");printf(

"\t2-> affichage infixe.\n");printf(

"\t3-> affichage prefixe.\n");printf(

"\t4-> affichage postfixe.\n");printf(

"\t5->Inistialisation.\n");printf(

"\t6-> preparation d un noeud.\n");printf(

"\t7-> Ajout d un noeud.\n");printf(

"\t8-> Ajout d'un element.\n");printf(

"\t9-> existance d une cle.\n");printf(

"\t10-> Extraire un element.\n");printf(

"\t11-> Etraire l adresse du noeud contenant la cle maximal.\n");printf(

"\t12-> Iserstion d un noeud .\n");printf(

"\t13-> supprission de la racine.\n");printf(

"\t0-> Quitter\n\n");}

int

main (){

/* Declaration des variables et initialisation */

Arber *A,*Fg,*Fd;

char reponse;NOEUD *racine ,*Nracine;

NOEUD *n ;

/* initialisation a -1 permet de rentrer dans le switch au debut */

int choix = -1;

int nb_noeud = 0;

char information ,R_info;

int R_cle,i;

int cle;BOOLEEN Bool;

printf(

"vouler vous tester les manipulations sur les arbres? o/n? ");scanf (

"\n%s",& reponse);

if (reponse==
'o') {

while

(choix != 0){

/* affichage du menu */affich_menu();

/* saisie du choix */printf(

"\tVotre choix:\n");scanf(

"\n%d",&choix);

/* acces au choix demandé */

switch(choix){

case 1: {printf(

"donner le nmbr des noeuds\n");scanf(

"\n%d",&nb_noeud);printf(

"donner la cle de la racine\n");scanf(

"\n%d",&R_cle);racine=PreparerNoeud(R_cle);

printf(

"donner les cles des noeuds\n");i=2;

while (i<=nb_noeud){

scanf(

"\n%d",&cle);n=PreparerNoeud(cle);

InsererNoeud(racine,n);

i=i+1;

}

break;}

case 2: {printf(

"********************************************\n");printf(

"L affichage est comme suite....\n");affich_infixe_croissant(racine);

printf(

"********************************************\n"); 

break;}

case 3: {printf(

"********************************************\n");printf(

"L affichage est comme suite....\n");affich_pre(racine);

printf(

"\n********************************************\n");

break;}

case 4:{ printf(

"\n********************************************\n");printf(

"L affichage est comme suite....\n");affich_pos(racine);

printf(

"\n********************************************\n");

break;}

case 5:printf(

"\n********************************************\n");{

Inisialisation(racine);

printf(

"l arbre est intialiser\n");printf(

"\n********************************************\n"); 

break;}

case 6:printf(

"\n********************************************\n");{

printf(

"donner la cle a inserer\n");scanf(

"\n%d",&cle);A=PreparerNoeud(cle);

printf(

"L adress du noeud preparer est =%d",&A);printf(

"\n********************************************\n");

break;}

case 7:printf(

"\n********************************************\n");{

printf(

"Preparation d un noeud..\n");printf(

"donner la cle a inserer\n");scanf(

"\n%d",&cle);n=PreparerNoeud(cle);

Bool=AjouterNoeud( racine,n);

if (Bool==VRAI){

printf (

"Vous pouvez l'inserer\n");}

if (Bool==FAUX) printf(
"Desole, impossible de l'inserer car sa cle existe deja\n");

break;printf(

"\n********************************************\n");}

case 8:{

printf(

"\n********************************************\n");printf(

"Donner l element a ajouter.\n");scanf(

"\n%d",&cle);Bool=AjouterElement(racine, cle);

if (Bool==VRAI) printf (
"Vous pouvez inserer cette element.\ ");

if (Bool==FAUX) printf(
"Desole, impossible de l'inserer peu etre que elle existe deja! ou bien ya pas d'espace memoire!\n");

break;printf(

"\n********************************************\n");}

case 9:printf(

"\n********************************************\n");{

printf(

"Donner la cle.\n");scanf(

"\n%d",&cle);Bool=ExisteCle(racine,cle);

if (Bool==VRAI){

printf (

" la cle existe ");}

if (Bool==FAUX){

printf(

"la cle n'existe pas");}

break;printf(

"\n********************************************\n"); }

case 10:{

printf(

"\n********************************************\n");printf(

"Donner la cle.\n");scanf(

"\n%d",&cle);Bool=ExtraireElement(racine,cle);

if (Bool==VRAI) printf (
"la cle exsite et le noeud corespondant est supprimme");

if (Bool==FAUX)(
"Desole, la cle n'existe pas!");

break; printf(

"\n********************************************\n");}

case 11:{

printf(

"\n********************************************\n");A=ExtraireMax(racine);

printf (

"la'dresse du maximum =%d",&A);

break;printf(

"\n********************************************\n");}

case 12:{

printf(

"\n********************************************\n");printf(

"Dabord la preparation du noeud\n"); printf(

"Donner la cle.\n");scanf(

"\n%d",&cle);n=PreparerNoeud(cle);

InsererNoeud(racine,n);

printf(

"le noeud est insere"); 

 

break;printf(

"\n********************************************\n");}

case 13:{

printf(

"\n********************************************\n");

SupprimmerRacine(racine);

printf(

"la racine est supprimme.");printf(

"\n********************************************\n");

break;}

 

 

case 0:
break;

default :{printf(

"Choix impossible.\n");

break;}

}

printf(

"\n\n");}

 

 

 

 

 

}

else{

if (reponse==
'n')printf(
"Merci pour votre de votre attantion tout de meme");

else printf(
"Entrer la bonne reponse SVP...");}

return (0);}
Messages postés
149
Date d'inscription
mercredi 28 mars 2007
Statut
Membre
Dernière intervention
17 mai 2007
1
Salut,

Rapide survol et déjà:

 Initialisation : marche pas, il faut un arbre ** a; et faire *a = NULL en parametres
-ou retourner un arbre *
Puis ajouterNoeud : marche pas pour les memes raisons..
Puis extraireMax : marche pas pour les memes raisons..
Puis supprimerRacine.
Puis insererNoeud marchera pas, etc

En fait toutes les fonctions ne marcheront pas.
@++
Messages postés
63
Date d'inscription
dimanche 18 mars 2007
Statut
Membre
Dernière intervention
27 avril 2013

Salut ...


J'ai compilé le code et j'i pas trouver d'erreur par contre quand j'ai mi qu'est ce que tu m'as di , tats d'erreur me sont affichées ...


mais pour le fait qu'il ya as d'erreur et la fonction ne fait pas ce que je demande ,je crois le problem  est dans les instructions eux memes  .....(l'algorithme de la fonction est faux)..


 
Messages postés
149
Date d'inscription
mercredi 28 mars 2007
Statut
Membre
Dernière intervention
17 mai 2007
1
Salut,

Tu décris un exemple typique. Ton code compile mais ne marche pas. Moi je te propose d'y faire des changements pour que ça marche, mais tu me dis que ça ne compile pas. C'est parce qu'il faut changer plusieurs trucs, il suffit pas de rajouter une étoile. Enfin à toi de voir, de toutes façons ton code n'est toujours pas indenté c'est une horreur à lire, mais je t'ai dit comment résoudre ton problème. Je le redis une dernière fois.
Quand tu passes un "int i" en paramètres, changer "i" dans la fonction n'aura aucun effet à l'extérieur
 Quand tu passes un "arbre * a" en paramètres, changer "a" dans la fonction n'aura aucun effet à l'extérieur
Si tu veux que ça ait un effet, il faut passer "arbre ** a" et modifier "*a"
Car là tu ajoutes un noeud dans la fonction et dès que tu en sors le noeud a disparu, ou bien pire

Bon courage pour ton programme, mais si tu l'indentes pas (avec des espaces) et si tu fais pas ces modifications, oui, ca marchera pas même si ton algo est bon..
@++