Discussion :

[nevroo]

Bonjour,

je fais un arbre tout simple, arbre binaire qui ajoute des chaines de caracteres et les tris selons l'ordre alphabetique,le probleme, c'est que mon arbre ne marche pas, et je n'arrive pas a savoir pourquoi :

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>
#include <assert.h>
 
typedef struct node{
	struct node* left;
	struct node* right;
	char* value;
}Node;
 
Node* noeud(char* s, Node* r, Node* l){
	Node* res = malloc(sizeof(Node));
	assert( res != NULL);
	res->value = s;
	res->left = l;
	res->right = r;
	return res;
}
 
void insert(char* str, Node* tree){
 
	if(tree == NULL){
		 tree = noeud(str,NULL,NULL);
		 printf("%s\n", tree->value);
	}
	else if (strcmp(str,tree->value) != 0) {
		if(strcmp(str,tree->value) < 0) insert(str,tree->left);
		if(strcmp(str,tree->value) < 0) insert(str,tree->right);
	}
}
 
Node* search(char* str, Node* tree){
	while(tree != NULL){
		if(strcmp(str,tree->value) ==0)	return tree;
		else{
			if(strcmp(str,tree->value) < 0)	tree = tree->left;
			else tree = tree->right;
		}
	}
	return tree;
}
 
void parcours(Node* tree){
	if(tree != NULL){
		parcours(tree->left);
		printf("%s ", tree->value);
		parcours(tree->right);
	}
	printf("tree is null");
}
 
int main(void){
    Node* root= NULL;
    int i, x;
 
    char* s="hello";
    insert(s,root);
    insert("ron",root);
    insert("jo",root);
    insert("david",root);
    parcours(root);
    printf("\n");
 
 
    for (i = 0; i < 100; i++)
        if (search("hello", root) != NULL)  printf("%d", i);
    printf("\n");
 
  	return 0;
}

enfin je sais ou ça plante, ça plante a la methode insert ou il n'arrive pas a comparer tree avec NULL, donc ma question est : peut on comparer tree avec NULL de cette façon :

Code :

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

1
2
3
4
 
void insert(char* str, Node* tree){
 
	if(tree == NULL){

merci beaucoup

[salseropom]

Salut, bien sûr que tu peux comparer deux pointeurs. Mais si tree == NULL cela veut dire que tu n'as pas alloué ton noeud

Code :

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

1
2
3
4
5
6
7
 
Node = tree=malloc(sizeof(*tree));
if(tree==NULL)
{
  printf("erreur malloc");
  exit(EXIT_FAILURE);
}

et donc maintenant tree != NULL

[salseropom]

petite erreur de frappe

Code :

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

1
2
3
4
5
6
7
 
Node * tree=malloc(sizeof(*tree));
if(tree==NULL)
{
  printf("erreur malloc");
  exit(EXIT_FAILURE);
}

[pharel]

Oui on peut sans probleme car tree est un pointeur,donc on peut le comparer avec NULL.

C'est quoi ton erreur en faite (sa t'affiche quoi plutot).

[nevroo]

ca n'affiche rien justement,il ne rentre pas dans la methode d'insertion car il considere que tree == NULL or ce qui ne devrait pas etre le cas

[Tchetch]

Salut,

Déjà il me semble que la fonction :

Code :

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

void insert(char* str, Node* tree)

devrait être

Code :

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

void insert(char * str, Node ** tree)

Parce que comme tu fais, tu passe un pointeur vers Node, mais tu le modifies dans la fonction si il est null, donc il faut plutôt passer un pointeur vers ce pointeur pour pouvoir le modifier. De là, avec les modifications nécessaires ça marche.

Sinon ajoute quand même

Code :

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

1
2
#include <stdlib.h> /* malloc(...) */
#include <string.h> /* strcmp(...) */

[pharel]

C'est vrai que l'arbre sera toujours a NULL,mais je suis pas sur que le probleme vient de la car le faite de comparai tree a NULL ne devrais pas poser de probleme.

[diogene]

Tchetch a entièrement raison : tree est une variable locale à la fonction qui sera détruite en sortie et

Code :

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

tree = noeud(str,NULL,NULL);

est sans effet sur le programme appelant cette fonction, ce qui est la cause du problème
Tu peux aussi te dispenser d'appeler 3 fois pour faire la même chose strcmp et corriger le troisième

Code :

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

if(strcmp(str,tree->value) > 0) insert(str,tree->right);

ou te contenter d'un else : Si c'est pas nul et pas négatif, c'est que c'est >0 .
Enfin tu ignores les doublons ( == 0) Est-ce volontaire ?

[nevroo]

en effet, il y a une petit erreur dans mon code, merci a tous,je vais tester ca demain a la premiere heure, et je vous tiens au courant

[Tchetch]

Et puis tu as un "bohr bug" ...

Code :

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

1
2
		if(strcmp(str,tree->value) < 0) insert(str,tree->left);
		if(strcmp(str,tree->value) < 0) insert(str,tree->right);

Je pense que tu voulais écrire :

Code :

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

1
2
		if(strcmp(str,tree->value) < 0) insert(str,tree->left);
		if(strcmp(str,tree->value) > 0) insert(str,tree->right);