Thread: Binary Search Tree problem

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!

>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()?

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.

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);

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.

>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.