I'm trying to add strings to a Binary Search Tree using a recursive insert method (the usual for BSTs, IIRC) so I can later print them out using recursion as well.
Trouble is, I've been getting a segmentation faults I don't really understand. Related code follows (this block of code is from my main function):
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
// Stores the size of the C-strings we will use;
// Standardized to 100 (assignment specifications say
// ALL strings will be no more than 100 characters long)
// Please note that I defined this as a preprocessor
// directive because using the const keyword makes it
// impossible to define the size of the C-String array
// (C doesn't allow for static array struct members whose
// size is given as a variable)
#define STRING_SIZE 100
// The flags for case sensitivity
// and an output file
int cflag = 0, oflag = 0;
// These are intended to represent the boolean
// values true and false (there's no native bool
// data type in C, apparently)
const int TRUE = 1;
const int FALSE = 0;
// Type alias for the bool type
typedef int bool;
// This is the BST struct. A BST is basically just
// a Node with at most two children (left and right)
// and a data element.
typedef struct BST
{
struct BST *left;
struct BST *right;
char *key;
int counter;
} BST;
// ----- FUNCTION PROTOTYPES -----
void insert(BST **root, char *key);
int caseSenStrCmp(char *str1, char *str2);
int caseInsenStrCmp(char *str1, char *str2);
bool existsInTree(BST *root, char *key, int cflag);
void inOrderPrint(BST *root, int oflag, FILE *outFile);
void deallocateTree(BST *root);
int main(int argc, char **argv) {
extern char *optarg;
extern int optind;
int c, err = 0;
// Holds the current line in the file/user-provided string.
char currentLine[STRING_SIZE];
// This will store the input/output file
// directories
char fileDirectory[STRING_SIZE];
static char usage[] = "Usage: %s [-c] [-o output_file_name] [input_file_name]\n";
while ((c = getopt(argc, argv, "co:")) != -1)
switch (c)
{
case 'c':
cflag = 1;
break;
case 'o':
oflag = 1;
// If an output file name
// was entered, copy it
// to fileDirectory
if (argv[optind] != NULL)
{
strcpy(fileDirectory, argv[optind]);
}
break;
case '?':
err = 1;
break;
default:
err = 1;
break;
}
if (err)
{
// Generic error message
printf("ERROR: Invalid input.\n");
fprintf(stderr, usage, argv[0]);
exit(1);
}
// --- BST SORT CODE STARTS HERE ---
printf("This is BEFORE setting root to NULL\n");
// This is the BST. As the assignment instructions
// specify, it is initially set to NULL
BST *root = NULL;
// Pointer to the mode the files
// will be opened in. Starts as
// "w" since we're opening the output file
// first
printf("This is AFTER setting root to NULL\n");
char *mode = (char*)malloc(sizeof(char*));
strcpy(mode, "w");
printf("Wrote w to mode pointer");
// Pointer to the output file
FILE *outFile;
// Attempt to open output file
outFile = fopen(fileDirectory, mode);
printf("Opened outfile \n");
// Now update mode and fileDirectory so
// we can open the INPUT file
strcpy(mode, "r");
printf("Wrote r to mode\n");
// Check if we have an input file name
// If argv[optind] isn't NULL, that means we have
// an input file name, so copy it into fileDirectory
if (argv[optind] != NULL)
{
strcpy(fileDirectory, argv[optind]);
}
printf("Wrote input file name to fileDirectory.\n");
// Pointer to the input file
FILE *inFile;
// Attempt to open the input file
//printf("%d", inFile = fopen(fileDirectory, mode));
printf("Opened input file\n");
// If the input file was opened successfully, process it
if (inFile != NULL)
{
// Process the file while EOF isn't
// returned
while (!feof(inFile))
{
// Get a single line (one string)
//fgets(currentLine, STRING_SIZE, inFile);
printf("Wrote to currentLine; it now contains: %s\n", currentLine);
// Check whether the line is an empty line
if (*currentLine != '\n')
{
// If the string isn't an empty line, call
// the insert function
printf("currentLine wasn't the NULL CHAR");
insert(&root, currentLine);
}
}
// At this point, we're done processing
// the input file, so close it
fclose(inFile);
}
// Otherwise, process user input from standard input
else
{
do
{
printf("Please enter a string (or blank line to exit): ");
// Scanf takes user's input from stdin. Note the use
// of the regex [^\n], allowing the scanf statement
// to read input until the newline character is encountered
// (which happens when the user is done writing their string
// and presses the Enter key)
scanf("%[^\n]s", currentLine);
// Call the insert function on the line
// provided
insert(&root, currentLine);
} while (caseSenStrCmp(currentLine, "") != 0);
}
// At this point, we've read all the input, so
// perform in-order traversal and print all the
// strings as per assignment specification
inOrderPrint(root, oflag, outFile);
// We're done, so reclaim the tree
deallocateTree(root);
}
// ===== AUXILIARY METHODS ======
// Creates a new branch for the BST and returns a
// pointer to it. Will be called by the insert()
// function. Intended to keep the main() function
// as clutter-free as possible.
BST* createBranch(char *keyVal)
{
// Create the new branch to be inserted into
// the tree
BST* newBranch = (BST*)malloc(sizeof(BST));
// Allocate memory for newBranch's C-string
newBranch->key = (char*)malloc(STRING_SIZE * sizeof(char));
// Copy the user-provided string into newBranch's
// key field
strcpy(newBranch->key, keyVal);
// Set newBranch's counter value to 1. This
// will be incremented if/when other instances
// of the key are inserted into the tree
newBranch->counter = 1;
// Set newBranch's child branches to null
newBranch->left = NULL;
newBranch->right = NULL;
// Return the newly created branch
return newBranch;
}
// Adds items to the BST. Includes functionality
// to verify whether an item already exists in the tree
// Note that we pass the tree's root to the insert function
// as a POINTER TO A POINTER so that changes made to it
// affect the actual memory location that was passed in
// rather than just the local pointer
void insert(BST **root, char *key)
{
printf("We made it to the insert function!");
// Check if the current branch is empty
if (*root == NULL)
{
// If it is, create a new
// branch here and insert it
// This will also initialize the
// entire tree when the first element
// is inserted (i.e. when the tree is
// empty)
*root = createBranch(key);
}
// If the tree ISN'T empty, check whether
// the element we're trying to insert
// into the tree is already in it
// If it is, don't insert anything (the
// existsInTree function takes care of
// incrementing the counter associated
// with the provided string)
if (!existsInTree(*root, key, cflag))
{
// If it isn't, check if the case sensitivity
// flag is set; if it is, perform the
// checks using case-sensitive string
// comparison function
if (cflag) {
// Is the string provided (key) is
// greater than the string stored
// at the current branch?
if (caseSenStrCmp((*root)->key, key))
{
// If so, recursively call the
// insert() function on root's
// right child (that is, insert into
// the right side of the tree)
// Note that we pass the ADDRESS
// of root's right branch, since
// the insert function takes a
// pointer to a pointer to a BST
// as an argument
insert(&((*root)->right), key);
}
// If not, the key passed in is either less than
// or equal to the current branch's key,
// so recursively call the insert()
// function on root's LEFT child (that is,
// insert into the left side of the tree)
else
{
insert(&((*root)->left), key);
}
}
// If it isn't, perform the checks using
// the case-INsensitive string comparison
// function
else {
// The logic here is exactly the same
// as the comparisons above, except
// it uses the case-insensitive comparison
// function
if (caseInsenStrCmp((*root)->key, key))
{
insert(&((*root)->right), key);
}
else
{
insert(&((*root)->left), key);
}
}
}
}
// CASE SENSITIVE STRING COMPARISON function. Returns:
// -1 if str1 is lexicographically less than str2
// 0 if str1 is lexicographically equal to str2
// 1 if str2 is lexicographically greater than str1
I'm using getopt to parse options that the user enters. I've been doing a little bit of basic debugging using printf statements just to see how far I get into the code before it crashes, and I've more or less narrowed down the cause. It seems to be this part here:
do
{
printf("Please enter a string (or blank line to exit): ");
// Scanf takes user's input from stdin. Note the use
// of the regex [^\n], allowing the scanf statement
// to read input until the newline character is encountered
// (which happens when the user is done writing their string
// and presses the Enter key)
scanf("%[^\n]s", currentLine);
// Call the insert function on the line
// provided
insert(&root, currentLine);
} while (caseSenStrCmp(currentLine, "\n") != 0);
Or rather, calls to the insert function in general, since the printf statement I put at the beginning of the insert function ("We made it to the insert function!) gets printed over and over again until the program finally crashes with a segmentation fault, which probably means the problem is infinite recursion?
If so, I don't understand why it's happening. I initialized the root node to NULL at the beginning of main, so it should go directly into the insert functions *root == NULL case, at least on its first call.
Does it maybe have something to do with the way I pass root as a pointer to a pointer (BST **root in parameter list of insert function)? Am I improperly recursing, i.e. is this statement (and others similar to it)
insert(&((*root)->right), key);
incorrect somehow? This was my first guess, but I don't see how that would cause infinite recursion - if anything, it should fail without recursing at all if that was the case? Either way, it doesn't explain why infinite recursion happens when root is NULL (i.e. on the first call to insert, wherein I pass in &root - a pointer to the root pointer - to the insert function).
I'm really stuck on this one. At first I thought it might have something to do with the way I was copying strings to currentLine, since the line
if(*currentLine != '\0')
in the while (!feof(inFile)) loop also crashes the program with a segmentation fault, but even when I commented that whole part out just to test the rest of the code I ended up with the infinite recursion problem.
Any help at all is appreciated here, I've been trying to fix this for over 5 hours to no avail. I legitimately don't know what to do.
**EDIT: Since a lot of the comments involved questions regarding the way I declared other variables and such in the rest of the code, I've decided to include the entirety of my code, at least until the insert() function, which is where the problem (presumably) is. I only omitted things to try and keep the code to a minimum - I'm sure nobody likes to read through large blocks of code.
Barmar:
Regarding fopen() and fgets(): these were commented out so that inFile would remain NULL and the relevant conditional check would fail, since that part of the code also fails with a segmentation fault
createBranch() does initialize both the left and right children of the node it creates to NULL (as can be seen above)
currentLine is declared as an array with a static size.
@coderredoc:
My understanding of it is that it reads from standard input until it encounters the newline character (i.e. user hits the enter button), which isn't recorded as part of the string
I can already see where you were going with this! My loop conditional was set for the do/while loop was set to check for the newline character, so the loop would never have terminated. That's absolutely my fault; it was a carryover from a previous implementation of that block that I forgot to change.
I did change it after you pointed it out (see new code above), but unfortunately it didn't fix the problem (I'm guessing it's because of the infinite recursion happening inside the insert() function - once it gets called the first time, it never returns and just crashes with a segfault). **
