Discussion :

[Pallas.]

Bonjour,

j'essaye d'implémenter un arbre binaire de recherche avec quelques opérations. Je n'ai presque aucunes expériences en c (et en programmation en général). Donc les erreurs que j'ai fais sont sûrement de "bête erreurs" mais je n'arrive pas à les corriger.

Voici mon code :

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
 
struct node {
	struct node *lChild; //Pointeur vers le fils gauche.
	struct node *rChild; //Pointeur vers le fils droit.
	int value; //Valeur, ou cle, du noeud.
};
 
struct tree {
	struct node *root; //Pointeur vers l'element racine;
};
 
struct tree* constructNewTree()
{
	//Fonction qui alloue un arbre vide.
	struct tree *T=malloc(sizeof(struct tree));
	T->root=NULL;
 
	return T;
}

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
 
void insertKey(int i, struct tree *T)
{
	if (root==NULL) { //On crée le nouveau noeud lorsqu'on a trouvé son emplacement.
	    root->value=i;
	    root->lChild=NULL;
	    root->rChild=NULL;
	}
	else { // On cherche l'emplacement du nouveau noeud.
        if (root->value>i) {
            root->lChild=insertkey(root->lChild,i);
        }
        else {
            root->rChild=insertkey(root->rChild,i);
        }
	}
        //Fonction qui insere l'element i dans l'arbre T.
}
 
 
void inOrder(struct tree *T)
{
    if(root->lChild!=NULL) { // On veut les noeuds dans l'ordre croissant donc on commence par les élément en bas à gauche puis on remonte vers la droite.
        inOrder(root->lChild);
    }
        printf(“ %d \n”,root->value);
    if(root->rChild!=NULL) {
        inOrder(root->rChild);
    }
}
//Fonction pour obtenir un parcour recursif "en-ordre" de l'arbre T.

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 main()
{
	struct tree *T;
	T=constructNewTree();
 
	insertKey(5,T);
	insertKey(2,T);
	insertKey(9,T);
	insertKey(1,T);
 
	inOrder(T);
 
	return 0;
}

Voici mes erreurs:

In function 'insertKey'
|29|error: 'root' undeclared (first use in this function)|
|29|error: (Each undeclared identifier is reported only once|
|29|error: for each function it appears in.)|
|36|warning: implicit declaration of function 'insertkey'|
In function 'inOrder'
|48|error: 'root' undeclared (first use in this function)|
|51|error: stray '\223' in program|
|51|error: expected expression before '%' token|
|51|error: stray '\' in program|
|51|error: stray '\224' in program|
In function 'main'
|70|warning: implicit declaration of function 'deleteTree'|

Je remercie déjà tout ceux qui prendront le temps de jeter un coup d'œil à mon problème. Et j'espère que quelqu'un pourra m'aider.
J'attends impatiemment vos réponses.

[quetzacoatl]

Le problème est:

void insertKey(int i, struct tree *T)
{
if (root==NULL) { //On crée le nouveau noeud lorsqu'on a trouvé son emplacement.
root->value=i;
root->lChild=NULL;
root->rChild=NULL;

Tu utilises "root" comme variable, alors que tu ne l'as pas declare
Je pense que tu voulais plutot mettre:

Code :

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

T->root

A la place de root

[Pallas.]

En effet, merci pour votre aide. Mais j'ai rechangé pas mal de choses en réfléchissant.

Voici mon code actuel:

Partie 1)

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
struct node {
	struct node *lChild; //Pointeur vers le fils gauche.
	struct node *rChild; //Pointeur vers le fils droit.
	int value; //Valeur, ou cle, du noeud.
};
 
struct tree {
	struct node *root; //Pointeur vers l'element racine;
};
 
void insertKey(int i, struct tree *T);
struct node * insertNode(int i, struct node *n);
 
struct tree* constructNewTree()
{
	//Fonction qui alloue un arbre vide.
	struct tree *T=malloc(sizeof(struct tree));
	T->root=NULL;
 
	return T;
}

Partie 2:

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
void insertKey(int i, struct tree *T)
{ 
    insertNode(i, T->root);
        //Fonction qui insere l'element i dans l'arbre T.
}
 
struct node* insertNode(int i, struct node *n)
{
        if (!n) {  //On crée le nouveau noeud lorsqu'on a trouvé son emplacement.
                struct node* n=malloc(sizeof(struct node));
        	    n->value=i;
                n->lChild=NULL;
                n->rChild=NULL;
        }
    	else { // On cherche l'emplacement du nouveau noeud.
            if (n->value>i) {
                n->lChild=insertNode(i,n->lChild);
            }
            else {
                n->rChild=insertNode(i,n->rChild);
            }
        return n;
        }
}

Partie 3:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
	struct tree *T;
	T=constructNewTree();
 
	insertKey(5,T);
	insertKey(2,T);
	insertKey(9,T);
	insertKey(1,T);
 
 
	return 0;
}

Là je n'ai plus d'erreurs lors de la compilation.
Mais lorsque j'utilise des printf à certains endroits, je remarque qu'en fait dans la fonction insertNode, n est toujours égal à NULL. Donc le programme crée à chaque fois le nouveau noeud/clé comme si il n'y avait pas de premier élément (racine) à mon arbre!

En principe, il ne devrait pas y avoir d'erreurs dans les partie 1 et 3.

Merci d'avance pour votre aide. Je ne comprends vraiment pas pq ça ne fonctionne pas comme je le voudrais.