Binary Search Tree problem

Hi, I am having a problem with my program. It does not insert anything to the tree. Any help are appreciated. Thanks in advance.

driver:

Code:

---


int main(void)
{
        TreeNode *root;

        system("clear");

        Introduction();

        CreateTree(&root);

        /*endless loop: DoCommand() will call exit() to end the program.  */
        while(TRUE)
                DoCommand(GetCommand(), root);
        return 1;  //This statement should never be executed.

}

void DoCommand(char command, TreeNode *root)
{
        TreeEntry target;        // search item
        int flag;                // records EOF condition from scanf
        FILE *fp;                // pointer to file to open
        char file[MAXCHAR];            // file name to be opened
        char c;
        int i;
        TreeNode *newnode, *targetnode;

        switch(command)
        {
                /*  Reading File  */
                case 'r':
                  printf("\nEnter the filename: ");
                  scanf("%s", file);

                  if((fp = fopen(file,"r")) == NULL)
                    Error("File failed to open.\n");

                  else
                  {
                        /* Read file */
                        newnode = (TreeNode*)malloc(sizeof(TreeNode));

                        while(fscanf(fp, "%s", &newnode->entry.key) != EOF)
                        {
                          if(newnode)
                          {
                                /*  Inserting item into tree */
                                root = InsertTree(root, newnode);
                                printf("newnode = %s\n", newnode);
                                newnode = (TreeNode *)malloc(sizeof(TreeNode));
                          else
                                printf("memory exhausted.\n");

                        }

                  }

                  fclose(fp);

                  break;
        }
}

---

insert function:

Code:

---


/* InsertTree: insert a new node in the tree.
 * Pre:  The binary search tree to which root points has been created.
 *        The parameter newnode points to a node that has been created and
 *        contains a key in its entry.
 * Post: The node newnode has been inserted into the tree in such a
 *      way that the properties of a binary search tree are preserved.
*/
TreeNode *InsertTree(TreeNode *root, TreeNode *newnode)
{
    if(!root)
    {
        root = newnode;
        root->left = root->right = NULL;
    }


    else if (LT(newnode->entry.key, root->entry.key))
        root->left = InsertTree(root->left, newnode);

    else
        root->right = InsertTree(root->right, newnode);

    return root;
}

---

Have you tried stepping through the code with a debugger?

Does it for example take the if(!root) the first time through the function?
Does it evaluate the LT part just once for the 2nd time through?

Also, how do you know that it doesn't insert? Maybe it's your printing function that's screwed and not your insertion function.
Either use a debugger like Salem suggests or pepper your code with printf statements to trace the flow

QuantumPete

I did think that it was my printing function's problem but it i don't think it's the problem.

printing function:

Code:

---

void Print(TreeEntry x)
{
        printf("%s\n", x.key);

}

---

I had printfs in the InsertTree function and it was printing the inputs correctly.
My original insertion function which included the printf:

Code:

---

/* InsertTree: insert a new node in the tree.
 * Pre:  The binary search tree to which root points has been created.
 *        The parameter newnode points to a node that has been created and
 *        contains a key in its entry.
 * Post: The node newnode has been inserted into the tree in such a
 *      way that the properties of a binary search tree are preserved.
*/
TreeNode *InsertTree(TreeNode *root, TreeNode *newnode)
{
    //root = (TreeNode *)malloc(sizeof(TreeNode));
    //newnode = (TreeNode *)malloc(sizeof(TreeNode));

    if(!root)
    {
        root = newnode;
        root->left = root->right = NULL;
    }


    else if (LT(newnode->entry.key, root->entry.key))
    {
        root->left = InsertTree(root->left, newnode);
        printf("left = %s\n", root->left);
    }
    else
    {
        root->right = InsertTree(root->right, newnode);
        printf("root = %s\nright = %s\n", root,root->right);
    }

printf("root = %s\n", root);
    return root;
}

---

I used the preorder function and it was this part that told me the items are not been inserted into the tree. If I change if(root) to if(!root), it executes the if loop. If it was just if(root), it doesn't do anything.

The preorder function:

Code:

---

/* Preorder: visit each node of the tree in preorder.
 * Pre:  The binary tree to which root points has been created.
 * Post: The function Visit has been performed on every entry in the binary
 *      tree in preorder sequence.
 */
void Preorder(TreeNode *root, void (*Visit)(TreeEntry x))
{
printf("in preorder\n");
    if(root)
    {
        Visit(root->entry);
        Preorder(root->left, (*Visit));
        Preorder(root->right, (*Visit));
    }
}

---

Why are you using %s to print a node?

You do memory allocation in strange places and aren't actually properly handling failure to allocate memory in all cases. It can still crash if malloc returns null on the 'while' line.

That said, your InsertTree function is fine. The problem lies elsewhere.

I used %s to print out the item's key in string.

Where do I allocate the memory for all cases?

At what point do you call Preorder()? Is it somewhere in DoCommand()?

Yes it is in the DoCommand(). I also have inorder and postorder in a similiar format to preorder in DoCommand().

When I run the program after reading in the file and choose preorder. It gives me segmentation fault. When I try to search for an item, it says null for items that I entered which was also in the input file. This leads me to think that the items are not being inserted into the tree.

a portion of DoCommand:

Code:

---

void DoCommand(char command, TreeNode *root)
{
        TreeEntry target;        // search item
        TreeEntry item;          //input
        int flag;                // records EOF condition from scanf
        FILE *fp;                // pointer to file to open
        char file[MAXCHAR];            // file name to be opened
        char c;
        int i;
        TreeNode *newnode, *targetnode;

        switch(command)
        {
                /*  Reading File  */
                case 'r':
                  printf("\nEnter the filename: ");
                  scanf("%s", file);

                  if((fp = fopen(file,"r")) == NULL)
                    Error("File failed to open.\n");

                  else
                  {
                        /* Read file */
                        newnode = (TreeNode*)malloc(sizeof(TreeNode));

             
                        while(fscanf(fp, "%s", &newnode->entry.key) != EOF)
                        {

                          if(newnode)
                          {
                                root = InsertTree(root, newnode);
                                printf("newnode = %s\n", newnode);
                                newnode = (TreeNode *)malloc(sizeof(TreeNode));
                          }

                          else
                                printf("memory exhausted.\n");


                        }
                  }
           

                  fclose(fp);

                  break;

                /*  Search  */
                case 's':
                  printf("Enter the name that you would like to search: ");
                  scanf("%s", &target.key);
                  targetnode = TreeSearch(root, target.key);
                  printf("target = %s\n", targetnode);
                  break;


                case 'p':  //preorder
                  printf("Preorder of list is:\n");
                  Preorder(root, Print);
                  break;
    }
}

---

What does CreateTree() look like? Also how are TreeNode and TreeEntry declared?

CreateTree:

Code:

---

/* CreateTree:  create a tree.
 * Pre:  None.
 * Post: An empty binary search tree has been created to which root points.
*/
void CreateTree(TreeNode **root)
{
        *root = NULL;
}

---

CreateTree is used in the driver:

Code:

---

int main(void)
{
        TreeNode *root;

        system("clear");

        Introduction();

        CreateTree(&root);

        /*endless loop: DoCommand() will call exit() to end the program.  */
        while(TRUE)
                DoCommand(GetCommand(), root);
        return 1;  //This statement should never be executed.

}

---

I see the problem. DoCommand() should be declared to return the root. Otherwise you lose the pointer since a copy is passed:

Code:

---

TreeNode *DoCommand(char command, TreeNode *root)

---

And then in main the call should be:

Code:

---

                root = DoCommand(GetCommand(), root);

---

Alternately you could pass DoCommand() a pointer to pointer to root.

I changed the code to the way you stated and the problems are still there.
When I search for an item that is in the input file, it gives me null.
When I choose preorder, it gives me segmentation fault.

TreeNode and TreeEntry is declared:

Code:

---

typedef struct treeentry{
        char key[MAXCHAR];
}TreeEntry;

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

---

Did you add a:

Code:

---

return root;

---

at the end of DoCommand()? Actually the compiler should warn you about this.

Have you decided whether things are getting inserted or not? You've never shown your search function, so can't say anything about that. What's the current code look like?

Also I just noticed you're missing a right brace here, right before the else:

Code:

---

>                          if(newnode)
>                          {
>                                /*  Inserting item into tree */
>                                root = InsertTree(root, newnode);
>                                printf("newnode = %s\n", newnode);
>                                newnode = (TreeNode *)malloc(sizeof(TreeNode));
>                          else
>                                printf("memory exhausted.\n");

---

I'm surprised it would compile like that. And the malloc() line I've highlighted is not necessary, and should probably be removed.

Yes, I forgot to add

Code:

---

return root;

---

The complier didn't say anything about it. =/

With that been added, the preorder is working now. So this means the items are inserted into the tree. I've been using, for example:

Code:

---

void DoCommand(char command, List *list]

---

for most of the programs. Can you explain why changing DoCommand() to return something or to:

Code:

---

TreeNode *DoCommand(char command, TreeNode *root);

---

?

However, the search is still not working. When I search for the item, it still gives me null.

The current code of DoCommand with search in red:

Code:

---

TreeNode *DoCommand(char command, TreeNode *root)
{
        TreeEntry target;        // search item
        TreeEntry item;          //input
        int flag;                // records EOF condition from scanf
        FILE *fp;                // pointer to file to open
        char file[MAXCHAR];            // file name to be opened
        char c;
        int i;
        TreeNode *newnode, *targetnode;

        switch(command)
        {
                /*  Reading File  */
                case 'r':
                  printf("\nEnter the filename: ");
                  scanf("%s", file);

                  if((fp = fopen(file,"r")) == NULL)
                    Error("File failed to open.\n");

                  else
                  {
                        /* Read file */
                        newnode = (TreeNode*)malloc(sizeof(TreeNode));
                        while(fscanf(fp, "%s", &newnode->entry.key) != EOF)
                        {

                          if(newnode)
                          {
                                root = InsertTree(root, newnode);
                                printf("newnode = %s\n", newnode);
                                newnode = (TreeNode *)malloc(sizeof(TreeNode));
                          }

                          else
                                printf("memory exhausted.\n");


                        }

                  }

                  fclose(fp);

                  break;
                /*  Search  */
                case 's':
                  printf("Enter the name that you would like to search: ");
                  scanf("%s", &target.key);
                  targetnode = TreeSearch(root, target.key);
                  printf("target = %s\n", targetnode);
                  break;

                case 'p':  //preorder
                  printf("Preorder of list is:\n");
                  Preorder(root, Print);
                  break;


                case 'i': //inorder
                  printf("Inorder of list is:\n");
                  Inorder(root, Print);
                  break;

                case 'o': //postorder
                  printf("Postorder of list is:\n");
                  Postorder(root, Print);
                  break;

                case 'h':
                  Help();
                  break;
                case 'q':
                  printf("\nBinary Search Tree ended\n\n");
                  exit(0);
        }

        return root;
}

---

Thank you for helping!

There's probably something wrong with TreeSearch, but you wrote the function in invisible ink, so I don't know what.

And the rationale behind changing DoCommand is that parameters are passed by value -- so any changes to root that occur inside DoCommand are not reflected in main.

>Can you explain why changing DoCommand() to return something or to:
It's for the same reason you declared CreateTree() to return a **root instead of a single pointer.

In C, any time you pass an argument to a function it makes a copy of the argument. This is true for pointers as well as variables. So any changes to the variable within the function are not seen by the caller. In order to make changes to a variable, you must pass a pointer to that variable. The same is true for pointer. You can change the data the pointer is pointing to, and that will be seen by the caller. But if the pointer's value (where it's pointing) is changed, the caller will not see that (for example a call to malloc() to allocate memory that the pointer points to). If you had defined CreateTree() like this:

Code:

---

void CreateTree(TreeNode *root)
{
        root = NULL;
}

---

It would not have worked correctly, because back in main(), root would no longer be NULL.

Can you post the code for function TreeSearch()?

And also: you can (probably!) get away with using %s to print a TreeNode *, since the address of the struct should also be the address of the first element, which is your char array, but it's still not good practice. targetnode.entry would be better.

By the way, if you ever have a question about whether a pointer value was changed by a function, you can always print the pointer's value with:

Code:

---

printf("%p\n", (void *) root);

---

If you had done this in main() after each call to DoCommand(), and prior to the changes you have made, you would have seen that root probably would be printed as null or 0, indicating it never got updated, except within DoCommand(). If you had printed it's value in DoCommand(), you would see root had a different value.

Thank you for the help and explanations! Things are a lot clearer now.

TreeSearch():

Code:

---

/* TreeSearch: search for target starting at node root.
 * Pre:  The tree to which root points has been created.
 * Post: The function returns a pointer to a tree node that matches target
 *      or NULL if the target is not in the tree.
 */
TreeNode *TreeSearch(TreeNode *root, KeyType target)
{
    if(root)
        if(LT(&target, root->entry.key))
            root = TreeSearch(root->left, target);
        else if (GT(&target, root->entry.key))
            root = TreeSearch(root->right, target);
    return root;
}

---

Also I've been getting a warning from the complier for search in DoCommand() for the line in red:
warning: passing argument 2 of âTreeSearchâ makes integer from pointer without a cast

Code:

---

                /*  Search  */
                case 's':
                  printf("Enter the name that you would like to search: ");
                  scanf("%s", &target.key);
                  targetnode = TreeSearch(root, target.key);
                  printf("target = %s\n", targetnode);
                  break;

---

That's a good point tabstop. This code:

Code:

---

                                printf("newnode = %s\n", newnode);

---

is asking to print the pointer. So it should be:

Code:

---

                                printf("newnode = %p\n", (void *) newnode);

---

And if wanted the key:

Code:

---

                                printf("newnode = %s\n", newnode->entry.key);

---

Quote:

---

Originally Posted by aim4sky

Thank you for the help and explanations! Things are a lot clearer now.

TreeSearch():

Code:

---

/* TreeSearch: search for target starting at node root.
 * Pre:  The tree to which root points has been created.
 * Post: The function returns a pointer to a tree node that matches target
 *      or NULL if the target is not in the tree.
 */
TreeNode *TreeSearch(TreeNode *root, KeyType target)
{
    if(root)
        if(LT(&target, root->entry.key))
            root = TreeSearch(root->left, target);
        else if (GT(&target, root->entry.key))
            root = TreeSearch(root->right, target);
    return root;
}

---

Also I've been getting a warning from the complier for search in DoCommand() for the line in red:
warning: passing argument 2 of âTreeSearchâ makes integer from pointer without a cast

---

Oh of course. Well: what's a KeyType then? You're passing it a char *, so if that's not the answer, we're in trouble.

Well target.key is of type array of char ( char key[MAXCHAR];
), so KeyType should be declared the same. Or as a pointer to char (char *).

ahh...I have KeyType declared as:

Code:

---

typedef char KeyType;

---

When I change it to:

Code:

---

typedef char KeyType[MAXCHAR];

---

or

Code:

---

typedef char *KeyType;

---

It gives me segmentation fault after I enter the item that I would like to search.
[/code]

Code:

---

>                  printf("target = %s\n", targetnode);

---

Change the print to print the key:

Code:

---

                  printf("target = %s\n", targetnode->entry.key);

---

And if you want to print the pointer also add another printf():

Code:

---

                  printf("target = %p\n", (void *) targetnode);

---

See if you still get a segmentation fault after those changes.

Thank you very much!!
Corret me if i'm worng. The following code prints out the address of the pointer?

Code:

---

printf("target = %p\n", (void *) targetnode);

---

I have it working now. It's time to add on inserting new items from keyboard and deleting any items user doesn't want from the tree.

>I have it working now
Glad you got it working. :)

>The following code prints out the address of the pointer?
That's correct. Anytime you want to print a pointer's address, use the %p format.

As to why your List *list worked without returned the list, I'm not sure. It could be the CreateList() function was different from CreateTree(), or maybe main() was arranged in a different manner.

I think it is weird because for the CreateList, it traverses fine after the program gets the item from the file and added into the list.

Thank you very much for helping and explaining!
I've learned a lot from you guys!

>Thank you very much for helping and explaining!
Glad we could help. :)