Thread: Binary Search Tree problem

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    27

    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;
    }
    Last edited by aim4sky; 04-09-2008 at 10:22 PM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    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
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  4. #4
    Registered User
    Join Date
    Mar 2008
    Posts
    27
    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));
        }
    }

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Why are you using %s to print a node?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    Mar 2008
    Posts
    27
    I used %s to print out the item's key in string.

    Where do I allocate the memory for all cases?

  8. #8
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    At what point do you call Preorder()? Is it somewhere in DoCommand()?

  9. #9
    Registered User
    Join Date
    Mar 2008
    Posts
    27
    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;
        }
    }
    Last edited by aim4sky; 04-10-2008 at 06:17 PM.

  10. #10
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    What does CreateTree() look like? Also how are TreeNode and TreeEntry declared?
    Last edited by swoopy; 04-10-2008 at 09:22 PM.

  11. #11
    Registered User
    Join Date
    Mar 2008
    Posts
    27
    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.
    
    }

  12. #12
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    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.

  13. #13
    Registered User
    Join Date
    Mar 2008
    Posts
    27
    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;

  14. #14
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    Did you add a:
    Code:
    return root;
    at the end of DoCommand()? Actually the compiler should warn you about this.

  15. #15
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree - object instantiation problem
    By patricio2626 in forum C++ Programming
    Replies: 3
    Last Post: 11-14-2006, 02:11 AM
  2. binary tree token problem
    By OldSchool in forum C++ Programming
    Replies: 13
    Last Post: 05-28-2006, 10:42 PM
  3. Binary Search Tree
    By penance in forum C Programming
    Replies: 4
    Last Post: 08-05-2005, 05:35 PM
  4. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 03:53 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM