Thread: 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);

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;

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*/
    }
}

oh I see, so I would have to type

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

something like that?

ooohh silly me. Ok I got it working thanks hammer.

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.

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.