Home > Net >  Binary Search Tree root node stays NULL
Binary Search Tree root node stays NULL

Time:11-16

for some reason my root node consistently stays NULL and nothing gets added to it. I am unsure as to why, and was wondering if someone could guide me as to what I am doing wrong. I am trying to read a file and perform different actions for every word based on the number I get. If it is a 1, I am trying to insert the word into the binary tree unless it is a duplicate in which case, I am trying to get the frequency to go up by 1. If it is a 2, I want to be able to print out the depth and number of times the word appears. In the end I want to display the words based on most frequent to least. The part I am stuck at now is that the root node always stays NULL so I am unable to build my tree, I also am unaware as to what the problem really is.

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

#define MAXSIZE 50

typedef struct node
{
    int depth;
    int frequency;
    struct node *left, *right;
    char word[MAXSIZE];
} node;


node* insert(node* root, char newWord[MAXSIZE])
{
    node *temp;
    printf("insert Function is being called\n %s\n", newWord);
    if(root == NULL)
    {
        temp = (node*) malloc(sizeof(node));
        temp->frequency = 1;
        temp->depth = 1;
        temp->left = NULL;
        temp->right = NULL;
        strcpy(temp->word, newWord);
        root = temp;
        printf("You should only recieve this message once.\n");
    }
    else if(strcmp(newWord, root->word)<0)
    {
        printf("Word being added towards left\n");
        insert(root->left, newWord);
        root->depth  =1;
    }
    else if(strcmp(newWord, root->word)>0)
    {
        insert(root->left, newWord);
        printf("Word being added towards right\n");
        root->depth  =1;
    }
    else if(strcmp(newWord, root->word)==0)
    {
        printf("Word being duplicated");
        root->frequency  =1;
    }
    return(root);
}

int inOrder(node* root)
{
    if(root != NULL)
    {
        inOrder(root->left);
        printf("BADAM %s\t", root->word);
        printf("%d\n", root->frequency);
        inOrder(root->right);
    }
}



void main()
{
    FILE *infile;
    FILE *outfile;
    char string[MAXSIZE];
    int i, c, n, j, k;
    node *root;
    root = NULL;
    infile = fopen("in.txt", "r");
    fscanf(infile, "%d\n", &n);
    for(i=0;i<n;i  )
    {
        printf("%d\n", i);
        fscanf(infile, "%d %s\n", &c, string);
        printf("the action is %d\n", c);
        switch (c)
        {
            case 1:
                printf("insert %s\n", string);
                insert(root, string);
                break;
            case 2:
                printf("print frequency of %s\n", string);
                break;
            default:
                printf("error in input\n");
                break;
            inOrder(root);
        }
    }
}

CodePudding user response:

You need to assign the returned pointer from the function insert to the pointer root

root = insert(root, string);

and within the function you need to write

root->left = insert(root->left, newWord);

and instead of using root->left in this code snippet

else if(strcmp(newWord, root->word)>0)
{
    insert(root->left, newWord);
    //...

you need to use the pointer root->right

else if(strcmp(newWord, root->word)>0)
{
    root->right = insert(root->right, newWord);
    //...  
  • Related