Thread: Binary Search Tree does not seem to be adding nodes correctly...

Well earlier today I was having a problem reading the strings into an array. After that was fixed I spent the next 5 hours trying to get this binary tree set up but after fiddling with everything I can think of it still spits out the wrong order.

I am pretty sure the problem has something to do with how I am passing the strings to the insert function but I can not figure out what and I have tried switching it around so many ways now. Does anything pop out as being extremely obvious as to why it is doing this?


This is the loop I am trying to use to add all of the strings in wordArray to the tree, and where I assume the problem is located. Not sure if the top part is relevant but edited to include it in case it is.

Code:

else {
	  while(!feof(file)) {
	    fgets(wordString, 30, file);
	    numWords++;
	  } 
	  rewind(file);
	  
	  wordArray = (char **)checked_malloc(numWords*sizeof(char*));
	  for(i = 0; fgets(wordString, sizeof(wordString), file); ++i) {
	    wordArray[i] = (char*)checked_malloc(strlen(wordString)*sizeof(char)+1);
	    strcpy(wordArray[i], wordString);	    
	  } fclose(file);
	}
for(j = 0; j < numWords-1; j++) {
	  tmp = newNode(wordArray[j]);
	  root = InsertTree(root, tmp);
	  free(wordArray[j]);
	}

These are the newNode and InsertTree functions.

Code:

struct TreeEntry {
	char *key;
	int freq;
};
typedef struct TreeEntry TreeEntry;

typedef struct TreeNode {
	TreeEntry entry;
	struct TreeNode *left;
	struct TreeNode *right;
} TreeNode;

TreeNode *newNode(char *key) {
	TreeNode *new = (TreeNode*)checked_malloc(sizeof(TreeNode));
	strcpy(new->entry.key, key);  //this could also be the problem but I have tried it as new->entry.key = key and I have the same problem, strings are just killing me today...
	new->right = NULL;
	new->left = NULL;
	return new;
}


TreeNode *InsertTree(TreeNode *root, TreeNode *newnode) {
	if(root == NULL)
	  root = newnode;
	else if(strcmp(newnode->entry.key, root->entry.key) < 0) 
	  root->left = InsertTree(root->left, newnode);
	else
	  root->right = InsertTree(root->right, newnode);
	return root;
}

Sometimes the program spits out crazy characters, depending on what I fiddle with.

root right:mousH�H�H�X���X���`���`���h���h���p���p���x� ��x����������������������������������������������� ����������������������������ȱ��ȱ��б��б��ر��ر������ ����������������������������

And here are some of the nodes that are being set in the tree. Some entries are being added twice somehow even though they are only on the word list once. Cat is the only one that is always correct, since it is the first word in the .txt file. wtfbbq is the last word yet it is somehow being placed as the right child of the root which should be impossible...

root:cat
root left:bear
root right:wtfbbq
root left left:animal
root left right:wtfbbq
root right left:llama
root right right:llama
root right right right:haha

Spitting out those chars is probably related to bad pointers/string issues. This is your problem:

Code:

strcpy(new->entry.key, key);

Took me awhile to realize you're not allocating any memory for new->entry.key. You have to malloc a buffer... something like this:

Code:

TreeNode *newNode(char *key) {
	TreeNode *new = (TreeNode*)checked_malloc(sizeof(TreeNode));
	new->entry.key = checked_malloc(strlen(key)); /* Does checked_malloc() take care of checking for NULL?  I hope so.  :) */
	strcpy(new->entry.key, key);
	new->right = NULL;
	new->left = NULL;
	return new;
}

Incidentally.....

Code:

while(!feof(file)) {
	    fgets(wordString, 30, file);
	    numWords++;
	  }

This is wrong. See the FAQ and use fgets() as the loop condition. feof() isn't to be used as a control loop, but as a way to figure out why a file function failed.

I realized the same thing after posting what I did. After changing it too... (checked_malloc just checks to make sure there is enough memory to allocate)

Code:

TreeNode *newNode(char *key) {
	TreeNode *new = (TreeNode*)checked_malloc(sizeof(TreeNode));
	new->entry.key = (char*)checked_malloc(20*sizeof(char)+1);
	new->entry.key = key;
	new->right = NULL;
	new->left = NULL;
	return new;
}

.....

	
for(j = 0; j < numWords-1; j++) {
	  tmp = newNode(strcpy(wordString, wordArray[j]));
	  root = InsertTree(root, tmp);
	  free(wordArray[j]);
	}

At the end of all the code I have some simple printf statements to check the root and its children, etc... well now it is printing the root as wtfbbq followed bye a "Segmentation Fault (core dumped)"

Wish my professor would show us how to program more instead of just giving us the basic ideas behind what a queue, tree, hash, etc are... grr

Edit: You where right! all I needed was the allocation, instead of also changing how I set entry->key = key... once I switched it back to strcpy(x1, x2) it works great now. It always amazes me in programming how a newbie such as myself can spend hours trying to fix a problem when it takes a pro seconds, and only 1 line of code. Thank you man! I will keep trying to do my own homework as your sig suggests