adding nodes to a binary search tree randomly deletes nodes
- by SDLFunTimes
Hi, stack. I've got a binary tree of type TYPE (TYPE is a typedef of data*) that can add and remove elements. However for some reason certain values added will overwrite previous elements. Here's my code with examples of it inserting without overwriting elements and it not overwriting elements.
the data I'm storing:
struct data {
int number;
char *name;
};
typedef struct data data;
# ifndef TYPE
# define TYPE data*
# define TYPE_SIZE sizeof(data*)
# endif
The tree struct:
struct Node {
TYPE val;
struct Node *left;
struct Node *rght;
};
struct BSTree {
struct Node *root;
int cnt;
};
The comparator for the data.
int compare(TYPE left, TYPE right) {
int left_len; int right_len; int shortest_string;
/* find longest string */
left_len = strlen(left->name);
right_len = strlen(right->name);
if(right_len < left_len) { shortest_string = right_len; } else { shortest_string = left_len; }
/* compare strings */
if(strncmp(left->name, right->name, shortest_string) > 1) {
return 1;
}
else if(strncmp(left->name, right->name, shortest_string) < 1) {
return -1;
}
else {
/* strings are equal */
if(left->number > right->number) {
return 1;
}
else if(left->number < right->number) {
return -1;
}
else {
return 0;
}
}
}
And the add method
struct Node* _addNode(struct Node* cur, TYPE val) {
if(cur == NULL) {
/* no root has been made */
cur = _createNode(val);
return cur;
}
else {
int cmp;
cmp = compare(cur->val, val);
if(cmp == -1) {
/* go left */
if(cur->left == NULL) {
printf("adding on left node val %d\n", cur->val->number);
cur->left = _createNode(val);
}
else {
return _addNode(cur->left, val);
}
}
else if(cmp >= 0) {
/* go right */
if(cur->rght == NULL) {
printf("adding on right node val %d\n", cur->val->number);
cur->rght = _createNode(val);
}
else {
return _addNode(cur->rght, val);
}
}
return cur;
}
}
void addBSTree(struct BSTree *tree, TYPE val)
{
tree->root = _addNode(tree->root, val);
tree->cnt++;
}
The function to print the tree:
void printTree(struct Node *cur) {
if (cur == 0) {
printf("\n");
}
else {
printf("(");
printTree(cur->left);
printf(" %s, %d ", cur->val->name, cur->val->number);
printTree(cur->rght);
printf(")\n");
}
}
Here's an example of some data that will overwrite previous elements:
struct BSTree myTree;
struct data myData1, myData2, myData3;
myData1.number = 5;
myData1.name = "rooty";
myData2.number = 1;
myData2.name = "lefty";
myData3.number = 10;
myData3.name = "righty";
initBSTree(&myTree);
addBSTree(&myTree, &myData1);
addBSTree(&myTree, &myData2);
addBSTree(&myTree, &myData3);
printTree(myTree.root);
Which will print:
((
righty, 10
)
lefty, 1
)
Finally here's some test data that will go in the exact same spot as the previous data, but this time no data is overwritten:
struct BSTree myTree;
struct data myData1, myData2, myData3;
myData1.number = 5;
myData1.name = "i";
myData2.number = 5;
myData2.name = "h";
myData3.number = 5;
myData3.name = "j";
initBSTree(&myTree);
addBSTree(&myTree, &myData1);
addBSTree(&myTree, &myData2);
addBSTree(&myTree, &myData3);
printTree(myTree.root);
Which prints:
((
j, 5
)
i, 5 (
h, 5
)
)
Does anyone know what might be going wrong? Sorry if this post was kind of long.
