Discussion :

[Gio35]

Bonjour à tous, je sollicite l'aide de quelqu'un pour m'aider à résoudre cette exercice s'il vous plait. Il s'agit d'un arbre binaires de recherche :

En informatique, un arbre binaire de recherche (ABR) est un arbre binaire dans lequel chaque noeud
possède une clé telle que chaque noeud du sous-arbre gauche ait une clé inférieure ou égale à celle du
noeud considéré, et que chaque noeud du sous-arbre droit possède une clé supérieure ou égale à celleci.
Selon la mise en oeuvre de l’ABR, on pourra interdire ou non des clés de valeur égale. Les noeuds que
l’on ajoute deviennent des feuilles de l'arbre.

Implémentez les fonctions suivantes qui agissent sur des ABR.
Les déclarations se trouveront dans le fichier abr.h et les implémentations dans le fichier abr.c.

Exercice 1
Créez un type arbre_recherche qui permet de simuler les arbres binaires de recherche d’entiers.

Exercice 2
Écrivez une fonction int insertion(arbre_recherche * ar, int x) qui permet d’insérer un
entier dans un arbre binaire de recherche. Cette fonction devra renvoyer la valeur 1 si l’insertion a été
réussie, -1 sinon. Votre arbre ne supportera pas les clés de valeur égale.

Exercice 3
Écrivez la fonction void affichage(arbre_recherche * ar) qui fait un affichage de l’arbre en
effectuant un parcours infixe de celui-ci.
La méthode infixe parcourt l’arbre en visitant d’abord le sous-arbre gauche, ensuite la racine et enfin le
sous-arbre droit. Ainsi, le parcours de l’arbre donnée en exemple serait : 1, 3, 4, 6, 7, 8, 19, 13, 14.

Si quelqu'un si connait un peu! Merci

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
#include "abr.h"
 
int main()
{
    arbre_recherche x;
 
    printf("Quel nombre cherchez-vous dans l'ABR ?\n")
    scanf("%d", &x);
 
    insertion(&x);
 
    affichage(&x);
 
    return 0;
}
 
 
int insertion(arbre_recherche* ar, int x)
{
    ar->nombre1 = *x;
 
    int i = -1;
 
    while (i = 1)
    {
        printf("L'insertion a ete faite avec succes !\n");
    }
}
 
 
 
void affichage(arbre_recherche* ar)
{
    int i = 0;
    int x = 0;
 
    for(i = 0, i < *x, i++)
        printf("%d", i);
}

[SofEvans]

En informatique, un arbre binaire de recherche (ABR) est un arbre binaire dans lequel chaque noeud
possède une clé telle que chaque noeud du sous-arbre gauche ait une clé inférieure ou égale à celle du
noeud considéré, et que chaque noeud du sous-arbre droit possède une clé supérieure ou égale à celleci.
Selon la mise en oeuvre de l’ABR, on pourra interdire ou non des clés de valeur égale. Les noeuds que
l’on ajoute deviennent des feuilles de l'arbre.

Implémentez les fonctions suivantes qui agissent sur des ABR.
Les déclarations se trouveront dans le fichier abr.h et les implémentations dans le fichier abr.c.

Exercice 1
Créez un type arbre_recherche qui permet de simuler les arbres binaires de recherche d’entiers.

Exercice 2
Écrivez une fonction int insertion(arbre_recherche * ar, int x) qui permet d’insérer un
entier dans un arbre binaire de recherche. Cette fonction devra renvoyer la valeur 1 si l’insertion a été
réussie, -1 sinon. Votre arbre ne supportera pas les clés de valeur égale.

Exercice 3
Écrivez la fonction void affichage(arbre_recherche * ar) qui fait un affichage de l’arbre en
effectuant un parcours infixe de celui-ci.
La méthode infixe parcourt l’arbre en visitant d’abord le sous-arbre gauche, ensuite la racine et enfin le
sous-arbre droit. Ainsi, le parcours de l’arbre donnée en exemple serait : 1, 3, 4, 6, 7, 8, 19, 13, 14.

Bonjour,

en premier lieu, je tiens a te signaler que tu as poster sur un forum d'entraide.
On est pas ici pour faire tes devoir.

Si tes profs t'ont donné cet énoncé, c'est que tu as eu les cours ou les connaissance nécessaire pour le faire seul.

Je tiens aussi a te rappeler que les commentaire existe ! J'ai pas envie de décrypter un code (surtout s'il il est long et complexe).


Pour ton cas :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
int insertion(arbre_recherche* ar, int x)
{
    ar->nombre1 = *x;
 
    int i = -1;
 
    // ABSOLUMNT INCOHERENT
    while (i = 1)
    {
        // LA VALEUR i N'EST JAMAIS CHANGER !!!!
        // RISQUE DE BOUCLE INFINIE !
        printf("L'insertion a ete faite avec succes !\n");
    }
}

Va falloir m'expliquer ce que tu as essayer de faire la ...
Tu as un ennoncé, donc un cahier des charge a respecter !!!

En informatique, un arbre binaire de recherche (ABR) est un arbre binaire dans lequel chaque noeud
possède une clé telle que chaque noeud du sous-arbre gauche ait une clé inférieure ou égale à celle du
noeud considéré, et que chaque noeud du sous-arbre droit possède une clé supérieure ou égale à celleci.

En clair, tu as un nombre. Si le nombre est inferieur a la racine (premiere valeur), il est stocker a gauche (si c'est possible). S'il est superieur, il est stocker a droite. S'il est egale, a toi de voir.

De plus, tu nous dis utiliser une structure. On a pas la declaration de la structure et je suis pas devin.

Bref, revise tes cours et dis nous comment tu compte gerer ton ABR. Quelle va etre ta demarche.
Commence a coder, et si tu as des probleme, post.

Si tu as des probleme de compilation, post nous tes erreur que te sort ton compilo.

[diogene]

Bonjour et bienvenue sur nos forums.

Exercice 1
Créez un type arbre_recherche qui permet de simuler les arbres binaires de recherche d’entiers.

Autrement dit, présentement, il nous faut le contenu de abr.h qui est ta réponse à cette question.

Exercice 2
Écrivez une fonction int insertion(arbre_recherche * ar, int x) qui permet d’insérer un
entier dans un arbre binaire de recherche. Cette fonction devra renvoyer la valeur 1 si l’insertion a été réussie, -1 sinon. Votre arbre ne supportera pas les clés de valeur égale.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
int insertion(arbre_recherche* ar, int x)
{
    ar->nombre1 = *x;
 
    int i = -1;
 
    while (i = 1)
    {
        printf("L'insertion a ete faite avec succes !\n");
    }
}

Il est évident que ce code ne peut en aucune manière insérer quoi que ce soit dans un arbre.
Remarques complémentaires :
la comparaison se fait avec == pas avec =
La boucle while ne s'exécute jamais ou on n'en sort jamais puisque la condition est toujours ou vrai ou fausse (i n'est pas modifié par la boucle). En l'occurence, tel que c'est écrit elle est toujours vrai et la boucle est sans fin)

Exercice 3
Écrivez la fonction void affichage(arbre_recherche * ar) qui fait un affichage de l’arbre en
effectuant un parcours infixe de celui-ci.
La méthode infixe parcourt l’arbre en visitant d’abord le sous-arbre gauche, ensuite la racine et enfin le sous-arbre droit. Ainsi, le parcours de l’arbre donnée en exemple serait : 1, 3, 4, 6, 7, 8, 19, 13, 14.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
void affichage(arbre_recherche* ar)
{
    int i = 0;
    int x = 0;
 
    for(i = 0, i < *x, i++)
        printf("%d", i);
}

Ce code est à l'évidence n'importe quoi puisqu'il ne dépend même pas de l'arbre (ar) censé être affiché.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
int main()
{
    arbre_recherche x;
 
    printf("Quel nombre cherchez-vous dans l'ABR ?\n")
    scanf("%d", &x);...

Ah! x du type arbre_recherche est aussi un type entier ?

Il va falloir faire un petit effort et proposer un code un minimum cohérent qui puisse être discuté.
Sur cette base, on peut considérer que tu nous demandes de faire tes exercices sans faire l'effort de les résoudre toi-même. Ce n'est pas notre rôle.

Travaille le sujet et si tu trouves des difficultés, poste ton code en expliquant ce qui pose problème.

[Gio35]

Je suis de nouveau et j'avoue ne pas avoir beaucoup de base mais voudrait comprendre étape par étape!

http://img44.imageshack.us/img44/9265/capturer1b.jpg voici la structure

[SofEvans]

Je voudrais m'excuser pour ma reponse precedente.

La premiere etape consiste a savoir comment tu vas modeliser ton ABR.

Il y a plusieurs facon de le modeliser.
J'en vois deux :
*modelisation de type liste chainée ( une structure possedant des pointeur sur la meme structure)
ou
*modelisation grace a un tableau

Il serait beaucoup mieux de le modeliser grace a la premiere solution.

Dis moi ce que tu connais, on pourra poursuivre le developpement.

[Gio35]

Disons que les pointeurs c'est pas trop mon fort! Je ne sais pas pas ou vraiment commencer? Mais c'est vrai que c'est la meilleure méthode! J'aimerais à l'aide de cet exercice un petit récap pour comprendre grâce à des explications.

[SofEvans]

Je ne suis pas assez expérimenter pour t'expliquer de par moi-même ce qu'est un pointeur. Je te conseille de lire ceci pour comprendre.

Pointeurs, tableaux et chaînes de caractères

Je part du principe que tu connais au minimum les notions des tuto precedent.
Si tu as du mal avec ces tutos, essais ceux de developpez.


On va donc faire un ABR avec pour modelisation de celui-ci les liste chainée.

Voici le schema de la structure

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
typedef struct Case
{
    /*
        Ici seront stocker les informations concernant la structure
    */
 
    // Ceci permet de savoir quelle sera la prochaine case
    struct Case *suivant;
 
 
}Case, *pCase;

Pour cette structure, Case designe la structure et pCase designe un pointeur vers cette structure.

L'information que nous voulons retenir est un nombre (en l'occurence un entier). La structure que nous utiliserons est la suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
typedef struct Case
{
    //  informations
    int nombre;
 
    // Ceci permet de savoir quelle seront les fils
    struct Case *filsGauche;
    struct Case *filsDroit;
 
 
}Case, *pCase;

On va declarer une pointeur, appeler "Racine" qui pointera toujours sur la racine de ton ABR. (Dans ton exemple, c'est le nombre 8).
Au debut, le pointeur "Racine" sera initialiser a NULL car aucun nombre n'est inserer.
Puis, lorsque l'on veut inserer un nombre dans cet arbre, on creer dynamiquement une Case que l'on insere via "Racine".


Je pense ne pas avoir été suffisamment explicite, mais j'ai du mal a expliquer.
Dis moi ce qu'il en est.