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!

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!