probleme arbre binaire de chaine

Version imprimable

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:

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:

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

merci beaucoup

31/10/2006, 16h55
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:

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

petite erreur de frappe

Code:

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

31/10/2006, 16h59
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).
31/10/2006, 17h02
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
31/10/2006, 17h06
Tchetch
Salut,

Déjà il me semble que la fonction :

Code:

void insert(char* str, Node* tree)

devrait être

Code:

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:

1 2 #include <stdlib.h> /* malloc(...) */ #include <string.h> /* strcmp(...) */
31/10/2006, 17h10
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.
31/10/2006, 18h35
diogene

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

Code:

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:

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 ?
31/10/2006, 21h08
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 :P

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

Code:

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:

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