Binary Search Tree Not Working

Question

I had a rather confusing problem in creating a binary tree. Apparently this should be a simple task, but somehow I can mess up the pointers in it.

Here's a simplified code (of course, this is not real code):

#include <string.h> #include <iostream> using namespace std; #define DIM1 2 typedef enum {LEFT,RIGHT} direction; typedef char tName[MAX_NAME_LEN + 1]; struct Rectangle { tName _name; struct Rectangle *_binSon[DIM1]; }; struct Rectangle *recTree; void insertRectToTree(char str[]){ struct Rectangle rect; struct Rectangle *point; struct Rectangle *parent; strcpy(rect._name,str); rect._binSon[RIGHT] = NULL; rect._binSon[LEFT] = NULL; point = &rect; if (recTree == NULL){ recTree = point; } else { struct Rectangle *current; current = recTree; while (current){ parent = current; if (strcmp(point -> _name, current -> _name) > 0){ current = current -> _binSon[RIGHT]; } else { current = current -> _binSon[LEFT]; } } if (strcmp(point -> _name, parent -> _name) < 0){ parent -> _binSon[LEFT] = point; } else { parent -> _binSon[RIGHT] = point; } } } int main(){ recTree = NULL; char str[] = "LIKE"; insertRectToTree(str); char str2[] = "GUIDE"; insertRectToTree(str2); printf(recTree -> _name); return 0; } 

As you can see, this binary tree is trying to organize a record based on its name, so the smallest alphabetical order will go left, etc.

The problem is that after the first insertion of “LIKE” I want “GUIDE” to be inserted into the tree as well, and “LIKE” still be as root. However, printf () shows that "GUIDE" takes care of its root. (In other words, “GUIDE” is the way out). Any good explanation for this? Ask me if I need to add something else to this question. Thanks for all your help.

Answer 1

In the following lines

 struct Rectangle rect; ... point = ▭ ... recTree = point; 

you assign a link to a local variable to a global pointer. After exiting the function, it may no longer contain reliable data.

Answer 2

Howard is right. But to fix the problem, use the new one.

i.e. instead of point = ▭

Put point = new struct Rectangle;