Inserting words into a binary search tree

This is a discussion on Inserting words into a binary search tree within the C Programming forums, part of the General Programming Boards category; I'm writing a program where I have to randomly choose 100 words from an array and put it into a ...

  1. #1
    Registered User
    Join Date
    Jul 2003
    Posts
    32

    Inserting words into a binary search tree

    I'm writing a program where I have to randomly choose 100 words from an array and put it into a binary search tree. I got the array working the random selection working but putting the words into the tree is not working for me. I've got the code to compile but get an error when I try to run it.

    Can somebody please check this code and give me some feedback as to why the program won't run?

    This is most of the code relating to the tree:
    Code:
    /*create tree*/
    void createtree(NODE *root)
    {
        root=(NODE *)malloc(sizeof(NODE));
        root->left=NULL;
        root->right=NULL;
    }
    
    /*insert words into the tree*/
    void insert(NODE *node, char *word)
    {
        if(node=NULL){
            node=(NODE *) malloc(sizeof(NODE));
            strcpy(node->data, word);
            node->left=NULL;
            node->right=NULL;
        }
        else{
            if(strcmp(word, node->data)<0)
                insert(node->left, word);
            else if(strcmp(word, node->data)>0)
                insert(node->right, word);
        }
    }
    and this is the line i use to call the function insert
    Code:
    insert(root, words[randnum].word);

  2. #2
    Peace
    Join Date
    Aug 2001
    Posts
    1,510
    Right off the bat:

    if(node=NULL)

    should be

    if(node==NULL)

    But could I get some more information? Whats yyour definition of 'node'. What error are you getting?
    "There's always another way"
    -lightatdawn (lightatdawn.cprogramming.com)

  3. #3
    Registered User
    Join Date
    Jul 2003
    Posts
    32
    Thanks lightatdawn. I changed that to '=='.

    And thanks Salem. I used your suggestion and took out createtree and used your code for NODE insert(etc...). That seemed to fix the error I was getting but now, I'm not so sure that I put the word in the node correctly because when I used this traversal function to print out the words in the tree, the program just ends.

    Do you think you could take a look at this problem as well?

    Code:
    /*traversal function that prints in order*/
    void traverse(NODE *root)
    {
        if(root!=NULL){
            traverse(root->left); /*recur left*/
            printf("%s ", root->data);
            traverse(root->right); /*recur right*/
        }
    }
    if it helps, here is my NODE stucture:
    Code:
    struct treenode{
        char data[N+1];
        struct treenode *left;
        struct treenode *right;
    };
    typedef struct treenode NODE;

  4. #4
    Registered User
    Join Date
    Jul 2003
    Posts
    32
    In that case I suppose I should just post it all. Thanks for helping me with this problem by the way.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h> /*to use strcpy*/
    #include <stddef.h> /*to use NULL*/
    
    #define N 4
    #define SEED 1234567
    
    struct words{
        char word[N+1];
        int used; /*If used is 1, word has been used and if used is 0, it has not.*/
    };
    typedef struct words WORDS;
    
    struct treenode{
        char data[N+1];
        struct treenode *left;
        struct treenode *right;
    };
    typedef struct treenode NODE;
    
    WORDS words[1000]={0};
    NODE data[N+1]={0};
    FILE *W4;
    NODE *root;
    
    void getWords(void);
    void printWords(void);
    void randomWords(void);
    NODE *insert(NODE *root, char *word);
    void traverse(NODE *root);
    
    
    int main(void)
    {
        getWords();
        /*printWords();*/
        randomWords();
        root=NULL;
        traverse(root);
        system("PAUSE");
        return 0;
    }
    
    void getWords(void)
    {
        int c=0, i=0, j=0; /*i increments words, j increments string*/
        char string[N+1];
    
        /*read in 1000 words from W4*/
        W4=fopen("W4", "r");
        while((c=getc(W4))!=EOF){
            if(i!=1000){
                if(c!='\n'&&c!=' ')
        		{
                    if(j==N){
                        i++;
                        string[j]='\0'; /*terminate string*/
                        /*printf("%s ", string);*/
                        strcpy(words[i].word, string);/*store string into an array*/
                        j=0; /*reset string incrementer to 0*/
                        string[j]=c; /*read in next character*/
                        j++;
                    }
                    else{
                        string[j]=c; /*read in a character*/
                        j++;
                    }
                }
                else
                    j=0;
            }
        }
        fclose(W4);
        printf("\n%d words have been put in the array words[1000].\n", i);
    }
    
    void printWords(void)
    {
        int i;
    
        for(i=0;i<1000;i++)
            printf("%s%d ", words[i].word, words[i].used);
    }
    
    void randomWords(void)
    {
        int i, randnum;
        /* initialize random generator */
        srand(SEED);
    
        for(i=0;i<100;i++){
            randnum=rand()%1000;
            if(words[randnum].used!=1)/* generate a random number */
                /*printf("%d:%d ", i+1, randnum);*/
                /*printf("%s ", words[randnum].word);*/
                insert(root, words[randnum].word);
                words[randnum].used=1;
        }
    }
    
    NODE *insert(NODE *node, char *word)
    {
        if(node==NULL){
            node=(NODE *) malloc(sizeof(NODE));
            strcpy(node->data, word);
            node->left=NULL;
            node->right=NULL;
        }
        else{
            if(strcmp(word, node->data)<0)
                insert(node->left, word);
            else if(strcmp(word, node->data)>0)
                insert(node->right, word);
        }
        return node;
    }
    
    void traverse(NODE *root)
    {
        if(root!=NULL){
            traverse(root->left); /*recur left*/
            printf("%s ", root->data);
            traverse(root->right); /*recur right*/
        }
    }

  5. #5
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    From a quick look, it seems your insert() function doesn't actually insert anything!

    The insert() function returns a pointer to the new node, but where do you store it?
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  6. #6
    Registered User
    Join Date
    Jul 2003
    Posts
    32
    oh I see, so I would have to type

    NODE *somenode;
    somenode=insert(root, words[randnum].word);

    something like that?

  7. #7
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Read Salems post, and check his code.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  8. #8
    Registered User
    Join Date
    Jul 2003
    Posts
    32
    ooohh silly me. Ok I got it working thanks hammer.

  9. #9
    Registered User
    Join Date
    Jul 2003
    Posts
    32
    Ok i do have it working but not properly. This time, it's giving me 192 random words when it should be giving me 100. I also noticed that when I traverse the tree and print the words out, I only get 96.

    I think the problem might be in my randomWords function. I'll post my whole program code just in case the error isn't there but somewhere else.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h> /*to use strcpy*/
    #include <stddef.h> /*to use NULL*/
    
    #define N 4
    #define SEED 1234567
    
    struct words{
        char word[N+1];
        int used; /*If used is 1, word has been used and if used is 0, it has not.*/
    };
    typedef struct words WORDS;
    
    struct treenode{
        char data[N+1];
        struct treenode *left;
        struct treenode *right;
    };
    typedef struct treenode NODE;
    
    WORDS words[1000]={0};
    NODE data[N+1]={0};
    FILE *W4;
    NODE *root=NULL;
    
    void getWords(void); /*reads 1000 words into an array*/
    void printWords(void); /*prints the words in the array*/
    NODE *randomWords(void); /*adds 100 random words into a binary search tree*/
    NODE *insert(NODE *root, char *word); /*adds a node to a binary tree*/
    void traverse(NODE *root); /*traverses a binary tree in order*/
    void reverse(NODE *root); /*traverses a binary tree in reverse order*/
    
    int main(void)
    {
        root=NULL;/*initialize root node*/
    
        getWords();
        /*printWords();*/
        root=randomWords();
        traverse(root);
        reverse(root);
    
        system("PAUSE");
        return 0;
    }
    
    void getWords(void)
    {
        int c=0, i=0, j=0; /*i increments words, j increments string*/
        char string[N+1];
    
        /*read in 1000 words from W4*/
        W4=fopen("W4", "r");
        while((c=getc(W4))!=EOF){
            if(i!=1000){
                if(c!='\n'&&c!=' ')
        		{
                    if(j==N){
                        i++;
                        string[j]='\0'; /*terminate string*/
                        /*printf("%s ", string);*/
                        strcpy(words[i].word, string);/*store string into an array*/
                        j=0; /*reset string incrementer to 0*/
                        string[j]=c; /*read in next character*/
                        j++;
                    }
                    else{
                        string[j]=c; /*read in a character*/
                        j++;
                    }
                }
                else
                    j=0;
            }
        }
        fclose(W4);
        printf("\n%d words have been put in the array words[1000].\n", i);
    }
    
    void printWords(void)
    {
        int i;
    
        for(i=0;i<1000;i++)
            printf("%s ", words[i].word);
    }
    
    NODE* randomWords(void)
    {
        int i, randnum;
        /* initialize random generator */
        srand(SEED);
    
        for(i=0;i<100;i++){ 
            randnum=rand()%1000; /* generate a random number */
            if(words[randnum].used!=1){
                printf("%s ", words[randnum].word);
                root=insert(root, words[randnum].word);
                words[randnum].used=1;
            }
        }
        return root;
    }
    
    NODE *insert(NODE *node, char *word)
    {
        if(node==NULL){
            node= malloc(sizeof(NODE));
            strcpy(node->data, word);
            node->left=NULL;
            node->right=NULL;
        }
        else{
            if(strcmp(word, node->data)<0)
                node->left=insert(node->left, word);
            else if(strcmp(word, node->data)>0)
                node->right=insert(node->right, word);
        }
        return node;
    }
    
    void traverse(NODE *root)
    {
        if(root!=NULL){
            traverse(root->left); /*recur left*/
            printf("%s ", root->data);
            traverse(root->right); /*recur right*/
        }
    }
    
    void reverse(NODE *root)
    {
        if(root!=NULL){
            reverse(root->right); /*recur right*/
            printf("%s ", root->data);
            reverse(root->left); /*recur left*/
        }
    }
    Unfortunately it's a bit long, sorry.

  10. #10
    Registered User
    Join Date
    Jul 2003
    Posts
    32
    AHA I figured it out. I have to add an else statement to decrement i (in the for loop in the randomWords function) if a repeated word has been found. (because the for loop would stop at 100 anyways and i would always be incremented)
    k i hope i don't have to bother you all again ...until next time haha.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 08:11 AM
  2. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 08:09 PM
  3. deleting all nodes of a binary search tree...
    By sachitha in forum C++ Programming
    Replies: 3
    Last Post: 09-29-2004, 06:19 AM
  4. inserting characters into a binary tree
    By sballew in forum C Programming
    Replies: 4
    Last Post: 12-06-2001, 03:08 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21