Thread: Tree Problem

  1. #1
    Registered User
    Join Date
    Nov 2004
    Posts
    67

    Unhappy 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?

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    > 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';

  3. #3
    Registered User
    Join Date
    Nov 2004
    Posts
    67
    how do i go about making name and phone_number members in my tree node? do i change my makenode function ?

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    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

  5. #5
    Registered User
    Join Date
    Nov 2004
    Posts
    67
    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.

  6. #6
    Registered User
    Join Date
    Nov 2004
    Posts
    67
    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;
    }

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Well yes, you have to save both strings in your tree

  8. #8
    Registered User
    Join Date
    Nov 2004
    Posts
    67
    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.

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    > strncpy(t->name, in, 9);
    How about copying phone as well
    And see my previous comments on how to use strncpy

  10. #10
    Registered User
    Join Date
    Nov 2004
    Posts
    67
    Thank you salem ive got it working! (with lots of help from you) , how do i make it non-case sensitive?

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  12. #12
    Registered User
    Join Date
    Nov 2004
    Posts
    67
    thanks, ive just converted everything to uppercase upon input using toupper and then converted the searched surname to uppercase before actually searching.
    Last edited by recluse; 11-28-2004 at 01:56 PM. Reason: spelling error

  13. #13
    Registered User
    Join Date
    Nov 2004
    Posts
    1
    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;
    }

  14. #14
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    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.

  15. #15
    Registered User
    Join Date
    Nov 2004
    Posts
    67
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Undirected graph and Binary Tree problem
    By arafat21 in forum C Programming
    Replies: 3
    Last Post: 05-02-2008, 05:52 AM
  2. BST delete again, but this time I think I'm close
    By tms43 in forum C++ Programming
    Replies: 9
    Last Post: 11-05-2006, 06:24 PM
  3. AVL tree balancing problem
    By sweets in forum C++ Programming
    Replies: 4
    Last Post: 05-06-2004, 12:17 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM