Arbre binaire

Signaler
Messages postés
3
Date d'inscription
dimanche 13 mars 2011
Statut
Membre
Dernière intervention
7 février 2012
-
Messages postés
5
Date d'inscription
mardi 29 novembre 2011
Statut
Membre
Dernière intervention
9 mai 2012
-
Bonjour

je voudrais ecrire un programme en C++ permettant de modifier une valeur dans un arbre binaire de recherche.
je suis quasi nul alors si vous connaissez la solution, merci de me la décrire en entier

5 réponses

Messages postés
14884
Date d'inscription
lundi 11 juillet 2005
Statut
Modérateur
Dernière intervention
30 novembre 2020
93
Hello,
Dans quelle partie bloques-tu?
Sans code de ta part, nous ne pourrons que te rediriger vers Google...

@+
Buno, Admin CS
L'urgent est fait, l'impossible est en cours. Pour les miracles, prévoir un délai...
Messages postés
3
Date d'inscription
dimanche 13 mars 2011
Statut
Membre
Dernière intervention
7 février 2012

En fait, je l'ai presque terminé, vous trouverez le code ci dessous.
ce qui me bloque en ce moment c'est affichage, car quand j'utilise juste la methode pour le parcours préfixe, tout marche bien mais quand j'utilise ensuite les mothodes infixe et postfixe il ne se compile pas.
et comme je l'ai dit, je ne suis pas un expert alors pourriez vous me dire ou est ce que je me bloque !!
merci

#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
struct N
{
    int r ;
    struct N* g ;
    struct N* d ;
};

typedef struct N TN;
typedef struct N* NODE;


/****************************************Création d'un arbre vide***************************************/

NODE NewArbreVide( void )
{
    return NULL;
}



/************************************************Fin*****************************************************/

/****************************************Ajout des éléments**********************************************/

void Add( NODE* ARBRE , int VAL )
{
    if( *ARBRE == NULL )
    {
        *ARBRE = ( NODE)malloc( sizeof( TN ) );
        (*ARBRE)->r = VAL ;
        (*ARBRE)->g = NULL ;
        (*ARBRE)->d = NULL ;
    }
    else
    {
        if( VAL < (*ARBRE)->r)
        {
                Add( &(*ARBRE)->g , VAL ) ;
        }
        else
        {
                Add( &(*ARBRE)->d , VAL ) ;
        }
    }
}

/************************************************Fin*****************************************************/


/****************************************Recherche des éléments******************************************/

int search(NODE ARBRE,int va)
 {
int trouve=false;

while(ARBRE&&!trouve)
{
if(ARBRE->r==va)
trouve=true;
else
{

if(var)
ARBRE=ARBRE->g;
else
ARBRE=ARBRE->d;

}

}

return trouve;

}

/************************************************Fin*****************************************************/



/****************************************L'affichage de l'arbre******************************************/

void ShowPrefixe( NODE ARBRE)
{
    if( ARBRE != NULL )
    {
        printf( "%d " , ARBRE->r ) ;
        ShowPrefixe( ARBRE->g ) ;
        ShowPrefixe( ARBRE->d ) ;
    }

}

void ShowInfixe( NODE ARBRE)
{
    if( ARBRE != NULL )
    {
        printf( "%d " , ARBRE->g ) ;
        ShowPrefixe( ARBRE->r ) ;
        ShowPrefixe( ARBRE->d ) ;
    }

}

void ShowPostfixe( NODE ARBRE)
{
    if( ARBRE != NULL )
    {
        printf( "%d " , ARBRE->g ) ;
        ShowPrefixe( ARBRE->d ) ;
        ShowPrefixe( ARBRE->r ) ;
    }

}

/************************************************Fin*****************************************************/


/****************************************La suppression de l'arbre******************************************/


int DeleteElement(NODE* ARBRE, int inf)
{


NODE temp=NULL;
NODE temp1=NULL;
int inftemp=0;
int elementSupprimer=false;

if(*ARBRE == NULL)
elementSupprimer=false;
else
{
if((*ARBRE)->rd,inf);

else if((*ARBRE)->r>inf)
elementSupprimer=DeleteElement(&(*ARBRE)->g,inf);

else
{
elementSupprimer=true;
if((*ARBRE)->g==NULL)
{
temp=*ARBRE;
(*ARBRE)=(*ARBRE)->d;
free(temp);
}
else
{
if((*ARBRE)->d==NULL)
{
temp=*ARBRE;
(*ARBRE)=(*ARBRE)->g;
free(temp);
}
else
{

//On remplace l'élément supprimer par le plus petit élément de son sous arbre droit

//Cherchons alors cet élément
temp=(*ARBRE);

temp=temp->d;
while(temp->g)
{
temp1=temp;
temp=temp->g;

}

//s'il n'y a plus de fils gauche, alors c'est lui le plus petit élément donc on le supprime

inftemp=temp->r;
if(temp->d)
{
temp1->g=temp->d;
free(temp);
}

(*ARBRE)->r=inftemp;
elementSupprimer=true;

}
}


}


}

return elementSupprimer;
}
/************************************************Fin*****************************************************/



/***************************************changement de la valeur******************************************/
void changerval(NODE* ARBRE, int inf)
{
  (*ARBRE)->r=inf;
}
/************************************************Fin*****************************************************/













/************************************************Main****************************************************/
int main()
{

    




    NODE ARBRE;
    int n,z;
    int test=0;
    int d=0;
    int l=0;
    char a;
    ARBRE=NewArbreVide();

Add( &ARBRE , 18);
Add( &ARBRE , 10);
Add( &ARBRE , 3);
Add( &ARBRE , 15);
Add( &ARBRE , 14);
Add( &ARBRE , 11);
Add( &ARBRE , 16);
Add( &ARBRE , 42);
Add( &ARBRE , 23);
Add( &ARBRE , 32);
Add( &ARBRE , 27);
Add( &ARBRE , 59);
Add( &ARBRE , 78);
Add( &ARBRE , 98);
Add( &ARBRE , 51);
Add( &ARBRE , 70);
Add( &ARBRE , 62);

int choix;

printf(" ==========Menu========== \n");
printf("1 . Parcours Prefixe\n");
printf("2 . Parcours Infixe\n");
printf("3 . Parcours Postfixe\n");
printf("Votre choix");scanf("%d", &choix);

switch (choix)
 {
case 1 :

printf("| Le parcours prefixe de l'arbre est:                                          |\n");
            printf("\t");ShowPrefixe(ARBRE);printf("\n");
            

            //changer la valeur de l'élément:

                 printf("|\t Donner la valeur a modifier:  ");
                 scanf("%d",&n);
                 printf("\n");
                  test=search(ARBRE,n);
                                                if(!test)
                                                printf("La valeur propose n'existe dans l'arbre. \n\n");

                                                else{

                 printf("\t Donner la nouvelle valeur :");
                 scanf("%d",&z);
                 l=search(ARBRE,z);
                 printf("\n");

                 while(l){
                           printf("\t Donner la nouvelle valeur :");
                 scanf("%d",&z);
                 printf("\n");
                 l=search(ARBRE,z);
                          }
                                    d=DeleteElement(&ARBRE,n);


                                                   Add( &ARBRE , z);


                printf("\n");
                                                    printf("Le nouveau parcours prefixe de l'arbre est :\n");
                                                   printf("\t");ShowPrefixe(ARBRE);
                                                    printf("\n\n");


                 a=getchar();}






break;

case 2 :

printf("| Le parcours Infixe de l'arbre est:                                          |\n");
            printf("\t");ShowInfixe(ARBRE);printf("\n");
            

            //changer la valeur de l'élément:

                 printf("|\t Donner la valeur a modifier:  ");
                 scanf("%d",&n);
                 printf("\n");
                  test=search(ARBRE,n);
                                                if(!test)
                                                printf("La valeur propose n'existe dans l'arbre. \n\n");

                                                else{

                 printf("\t Donner la nouvelle valeur :");
                 scanf("%d",&z);
                 l=search(ARBRE,z);
                 printf("\n");

                 while(l){
                           printf("\t Donner la nouvelle valeur :");
                 scanf("%d",&z);
                 printf("\n");
                 l=search(ARBRE,z);
                          }
                                    d=DeleteElement(&ARBRE,n);


                                                   Add( &ARBRE , z);


                printf("\n");
                                                    printf("Le nouveau parcours infixe de l'arbre est :\n");
                                                   printf("\t");ShowInfixe(ARBRE);
                                                    printf("\n\n");


                 a=getchar();}






break;

default :

printf("| Le parcours postfixe de l'arbre est:                                          |\n");
            printf("\t");ShowPostfixe(ARBRE);printf("\n");
            

            //changer la valeur de l'élément:

                 printf("|\t Donner la valeur a modifier:  ");
                 scanf("%d",&n);
                 printf("\n");
                  test=search(ARBRE,n);
                                                if(!test)
                                                printf("La valeur propose n'existe dans l'arbre. \n\n");

                                                else{

                 printf("\t Donner la nouvelle valeur :");
                 scanf("%d",&z);
                 l=search(ARBRE,z);
                 printf("\n");

                 while(l){
                           printf("\t Donner la nouvelle valeur :");
                 scanf("%d",&z);
                 printf("\n");
                 l=search(ARBRE,z);
                          }
                                    d=DeleteElement(&ARBRE,n);


                                                   Add( &ARBRE , z);


                printf("\n");
                                                    printf("Le nouveau parcours postfixe de l'arbre est :\n");
                                                   printf("\t");ShowPostfixe(ARBRE);
                                                    printf("\n\n");


                 a=getchar();}






break;
 }
 
 return 0;



}
/************************************************Fin*****************************************************/

Messages postés
14884
Date d'inscription
lundi 11 juillet 2005
Statut
Modérateur
Dernière intervention
30 novembre 2020
93
Bon, j'ai pas tout regardé, mais y'a ça:
void ShowInfixe( NODE ARBRE)
{
    if( ARBRE != NULL )
    {
        printf( "%d " , ARBRE->g ) ;
        ShowPrefixe( ARBRE->r ) ;
        ShowPrefixe( ARBRE->d ) ;
    }
}

void ShowPostfixe( NODE ARBRE)
{
    if( ARBRE != NULL )
    {
        printf( "%d " , ARBRE->g ) ;
        ShowPrefixe( ARBRE->d ) ;
        ShowPrefixe( ARBRE->r ) ;
    }
}

Pourquoi ces 2 fonctions appellent-elles la fonction ShowPrefixe()?

Tu dis que ça ne compile pas? Quel est le message d'erreur?

@+
Buno, Admin CS
L'urgent est fait, l'impossible est en cours. Pour les miracles, prévoir un délai...
Messages postés
3
Date d'inscription
dimanche 13 mars 2011
Statut
Membre
Dernière intervention
7 février 2012

en fait c'est faut ce que j'ai ecrit, j'ai oublie de corriger ça

en realiter se sont des fonctions récursives et elles retournent elles meme

voici ce que j'aurais du mettre

void ShowInfixe( NODE ARBRE)
{
    if( ARBRE != NULL )
    {
        printf( "%d " , ARBRE->g ) ;
        ShowInfixe( ARBRE->r ) ;
        ShowInfixe( ARBRE->d ) ;
    }
}

void ShowPostfixe( NODE ARBRE)
{
    if( ARBRE != NULL )
    {
        printf( "%d " , ARBRE->g ) ;
        ShowPostfixe( ARBRE->d ) ;
        ShowPostfixe( ARBRE->r ) ;
    }
}


pour ce qui concerne le message d'erreur je ne sais rien, j'utilise codeblock et quand je clique sur build and run il ne se passe rien du tout, par contre si j'enleve ces deux methodes alors il s'exécute

ça pourrait aussi venir de mon ordinateur donc si quelqu'un pourrait l'essayer ça serait pas de refut
Messages postés
5
Date d'inscription
mardi 29 novembre 2011
Statut
Membre
Dernière intervention
9 mai 2012

Essaye avec ça:

void ShowInfixe( NODE ARBRE)
{
    if( ARBRE != NULL )
    {
        ShowInfixe( ARBRE->r ) ;
        printf( "%d " , ARBRE->g ) ;
        ShowInfixe( ARBRE->d ) ;
    }
}

void ShowPostfixe( NODE ARBRE)
{
    if( ARBRE != NULL )
    {
        ShowPostfixe( ARBRE->d ) ;
        ShowPostfixe( ARBRE->r ) ;
        printf( "%d " , ARBRE->g ) ;
    }
}