Tree Problem

i need to create a telephone book using a tree. so for example i type in bob 0723393434
bill 032423423
. (input is stopped on reading a '.')
i then have to prompt the user to type in a name, for example bob and get the program to respond with the telephone number , e.g. 072339344.

example:

bob 3234343223
bill 2210382131.
Type a name please bob
3234343223
.

this is my code so far:

Code:

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct tree
{
    char thisnode[20];
    struct tree *left;
    struct tree *right;
}Tree;    

Tree *makenode( char *in, Tree *l, Tree *r)
{
    Tree *t=malloc(sizeof(Tree));
    t->left =l;
    t->right =r;
    strncpy(t->thisnode, in, 9);
    return t;
}    

Tree *insert( Tree *root, char *what)
{
    if(root==NULL)
    {root=makenode(what, NULL,NULL);}
    else if(strcmp(what, root->thisnode)<0)
    {root->left =insert(root->left,what);}
    else{root->right =insert(root->right, what);
}
return root;
}     

char *search(Tree *root, char *what)
{ 
    if(root==NULL){return "Not found";}
    else if(strcmp(what,root->thisnode)==0) {return root->thisnode;}
    else if(strcmp(what,root->thisnode)<0) {return search(root->left,what);}
    else{return search(root->right,what);}
}    

int main(void)
{
    char s[20];
    Tree *tree =NULL;
    printf("Please Input some names and telephone numbers:\n");
	do{
        scanf("%s",s);
        if(strcmp(s,".")!=0)
        {tree=insert(tree, s);}
    }    
    while(strcmp(s,".")!=0);
	printf("Please enter in a name:\n");
    do{
        scanf("%s",s);
        if(strcmp(s,".")!=0)
        {printf("%s\n", search(tree,s));}
    }while(strcmp(s,".")!=0);
return 0;
}

it compiles but the problem is that instead of finding the name and printing the telephone number it prints out just the name, how do i get it to print out the telephone number instead of the name? also how do i get it to not be case sensitive?

> scanf("%s",s);
Typing in "bob 1234" gets you two nodes in the tree, since %s uses space as a separator.

Try for example
scanf( "%s %s", name, phone_num );

and have a name and phone_num members in your tree node

> strncpy(t->thisnode, in, 9);
If you're going to do this, at least use sizeof to maximise your use of the space available

Code:

strncpy(t->thisnode, in, sizeof t->thisnode);
t->thisnode[ sizeof(t->thisnode) - 1] = '\0';

how do i go about making name and phone_number members in my tree node? do i change my makenode function ?

Code:

typedef struct tree
{
    char name[20];
    char phone[20];
    struct tree *left;
    struct tree *right;
}Tree;

Everything else should follow as a consequence of that

Your search function matches name, and returns phone

thanks for the help salem , i have now go to the stage where its returning me something(but not the telephone number)i think its returning out random stuff previously stored in memory. here is my code

Code:

/* Coursework Week 9 - Trees - Part 1- Mehrdad Montakhab*/


#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct tree
{
    char name[20];
    char phone[20];
    struct tree *left;
    struct tree *right;
}Tree;    

Tree *makenode( char *in, Tree *l, Tree *r)
{
    Tree *t=malloc(sizeof(Tree));
    t->left =l;
    t->right =r;
    strncpy(t->name, in, 9);
    return t;
}    

Tree *insert( Tree *root, char *what)
{
    if(root==NULL)
    {root=makenode(what, NULL,NULL);}
    else if(strcmp(what, root->name)<0)
    {root->left =insert(root->left,what);}
    else{root->right =insert(root->right, what);
}
return root;
}     

char *search(Tree *root, char *what)
{ 
    if(root==NULL){return "Not found";}
    else if(strcmp(what,root->name)==0) {return root->phone;}
    else if(strcmp(what,root->name)<0) {return search(root->left,what);}
    else{return search(root->right,what);}
}    

int main(void)
{
    char s[20];
    char b[20];
    Tree *tree =NULL;
    printf("Please Input some names and telephone numbers:\n");
	do{
        scanf("%s %s",s,b);
        if(strcmp(s,".")!=0 &&strcmp(b,".")!=0);
        {tree=insert(tree, s);}
    }    
    while(strcmp(s,".")!=0 &&strcmp(b,".")!=0);
	printf("Please enter in a name:\n");
    do{
        scanf("%s",s);
        if(strcmp(s,".")!=0)
        {printf("%s\n", search(tree,b));}
    }while(strcmp(s,".")!=0);
return 0;
}

any help is greatly appreciated.

do i have to change my insert function to something like this:

Code:

    Tree *insert( Tree *root, char *what, char *what2)
{
    if(root==NULL)
    {root=makenode(what, NULL,NULL);}
    else if(strcmp(what, root->name)<0)
    {root->left =insert(root->left,what, what2);}
    else{root->right =insert(root->right,what,what2);
}
return root;
}

Well yes, you have to save both strings in your tree

ok i've edited everything but its still not working properly, can anyone spot whats going wrong?

Code:

  


#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct tree
{
    char name[20];
    char phone[20];
    struct tree *left;
    struct tree *right;
}Tree;    

Tree *makenode( char *in, char *in2, Tree *l, Tree *r)
{
    Tree *t=malloc(sizeof(Tree));
    t->left =l;
    t->right =r;
    strncpy(t->name, in, 9);
    return t;
}    

Tree *insert( Tree *root, char *what, char *what2)
{
    if(root==NULL)
    {root=makenode(what,what2,NULL,NULL);}
    else if(strcmp(what, root->name)<0)
    {root->left =insert(root->left,what, what2);}
    else{root->right =insert(root->right,what,what2);
}
return root;
}     

char *search(Tree *root, char *what)
{ 
    if(root==NULL){return "Not found";}
    else if(strcmp(what,root->name)==0) {return root->phone;}
    else if(strcmp(what,root->name)<0) {return search(root->left,what);}
    else{return search(root->right,what);}
}    

int main(void)
{
    char s[20];
    char b[20];
    Tree *tree =NULL;
    printf("Please Input some names and telephone numbers:\n");
	do{
        scanf("%s %s",s,b);
        if(strcmp(s,".")!=0 &&strcmp(b,".")!=0);
        {tree=insert(tree, s,b);}
    }    
    while(strcmp(s,".")!=0 &&strcmp(b,".")!=0);
	printf("Please enter in a name:\n");
    do{
        scanf("%s",s);
        if(strcmp(s,".")!=0)
        {printf("%s\n", search(tree,b));}
    }while(strcmp(s,".")!=0);
return 0;
}

thanks.

> strncpy(t->name, in, 9);
How about copying phone as well
And see my previous comments on how to use strncpy

Thank you salem ive got it working! (with lots of help from you) , how do i make it non-case sensitive?

Write your own, or hope your compiler has the non-standard stricmp. The forums have a lot of posts on making characters upper or lower case.

Quzah.

thanks, ive just converted everything to uppercase upon input using toupper and then converted the searched surname to uppercase before actually searching.

first,
Tree *makenode( char *in, char *in2, Tree *l, Tree *r)
{
Tree *t=malloc(sizeof(Tree));
t->left =l;
t->right =r;
strncpy(t->name, in, 9);
strncpy(t->phone,in2,9);
return t;
}

second; in the main function:
init a new array for the second scanf.
for example,
int main(void)
{
char s[20];
char b[20];
char c[20];
Tree *tree =NULL;
printf("Please Input some names and telephone numbers:\n");
do{
fflush(stdin);
scanf("%s %s",s,b);
if(strcmp(s,".")!=0 &&strcmp(b,".")!=0);
{tree=insert(tree, s,b);}
}
while(strcmp(s,".")!=0 &&strcmp(b,".")!=0);
printf("Please enter in a name:\n");
do{
fflush(stdin);
scanf("%s",c);
if(strcmp(c,".")!=0)
{printf("%s\n", search(tree,c));}
}while(strcmp(c,".")!=0);
return 0;
}

Read Before Posting Code - Or how I learned to use code tags and love the moderators

> fflush(stdin);
Mmm, time to read the FAQ

> if(strcmp(s,".")!=0 &&strcmp(b,".")!=0);
Guess what that ; at the end of the line does.

i now want to be able to input a name and a telephone number , and then the same name with a different telephone number and get the program to print out both numbers:

e.g. tom 34233423
matt 3424334
tom 32343322
.
please type a name: tom
34233423
32343322

i was thinking about creating a lookup table or changing my search function somehow(however i couldnt keep looping through it as you would eventually get to NOT FOUND) , does anyone have any ideas of how to do this?

here is my code:

Code:

 #include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct tree
{
    char name[20];
    char phone[20];
    struct tree *left;
    struct tree *right;
}Tree;    

Tree *makenode( char *in, char *in2, Tree *l, Tree *r)
{
    Tree *t=malloc(sizeof(Tree));
    t->left =l;
    t->right =r;
    strncpy(t->name,in,19);
    strncpy(t->phone,in2,19);
    return t;
}    

Tree *insert( Tree *root, char *what, char *what2)
{
    if(root==NULL)
    {root=makenode(what,what2,NULL,NULL);}
    else if(strcmp(what, root->name)<0)
    {root->left =insert(root->left,what, what2);}
    else{root->right =insert(root->right,what,what2);
}
return root;
}     

char *search(Tree *root, char *what)
{
    if(root==NULL){return "NOT FOUND";}
    else if(strcmp(what,root->name)==0) {return root->phone;}
    else if(strcmp(what,root->name)<0) {return search(root->left,what);}
    else{return search(root->right,what);}
}

int main(void)
{
    int i;
    char s[20];
    char b[20];
    Tree *tree =NULL;
    do{
        scanf("%s",s);
	if(strcmp(s,".")==0)
	{break;}
	scanf("%s",b);
   for(i=0;i<20;i++)
    {s[i]=toupper(s[i]);}

	if(strcmp(s,".")!=0);
        {tree=insert(tree, s,b);}
    }
    while(strcmp(s,".")!=0);
	do{
		printf("Type a name name please ");
        scanf("%s",s);
        for(i=0;i<20;i++)
        {s[i]=toupper(s[i]);}
        if(strcmp(s,".")!=0)
        {printf("%s\n", search(tree,s));}
    }while(strcmp(s,".")!=0);
return 0;
}

thanks