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?