Thread: Binary Search Tree-Strange problem

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    6

    Binary Search Tree-Strange problem

    Hi there,
    I'm having a problem with my bst and I can't work out why. I've looked through so many pages of code but can't find a similar problem.

    In my program, I originally got it to read a file of numbers and create a bst using those numbers. This didn't seem to be working so I changed it to allow the user to input one number at a time to be added to the tree. Now I realise why the original code wasn't working. When the user is inputting data, the program exits suddenly depending on the input! It generally allows me to input 4 or 5 data items, then exits.

    eg.if the user inputs 2,1,4,3 then tries to input 5,it crashes.

    I have absolutely no idea why because my code seems to be very similar to any I can find on the internet.

    I assume the problem must be with the insert() function.

    I've attached the .c,.h and main files but it's my first post so tell me if I haven't added them the right way

    Any help would be much appreciated!
    Lydia

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Aside from the indentation being absolutely horrid, I can't actually see anything wrong (and I rand your program, and it did at least 8-9 digits of input, and printed what I expected too).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    6
    oops, sorry about the identation! i'm usually the only one who has to read my code so I just stick with the identation dev c++ gives me!

    Well it's still not working for me. No idea what the problem is. Exits for no apparent reason after I enter a couple of numbers.

    Thanks for the reply. I'll keep at it
    Lydia

  4. #4
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Worked fine (without crashing that is) for me after correcting one item that prevented me from compiling:
    Code:
    node* newNode(int data) { //create a new node 
        node* node = malloc(sizeof(node));
        node->data = data;
        node->right = NULL;
        node->left = NULL;
        return node;
    }
    error C2061: syntax error : identifier 'node'
    That was just because the name of the variable and the type were the same and it was confusing the compiler. I just renamed the variable in that case.

    Some nits:
    #1. Uninitialized variable "choice"
    Code:
    int data,choice;
    char ans;
    
    node* n = NULL;
    printf("Binary Trees-Main menu");
    printf("\n1.Insert data\n2.Print tree\n3.Get size of tree\n4.Get max depth of tree\n5.Quit\n");
    while(choice != 5){
    #2 Error message when selecting option 5 "quit"

    #3 MaxDepth function does not return proper result due to some missing bits of code:
    Code:
    else
    {
        ldepth = maxdepth(n->left);
        rdepth = maxdepth(n->right);
    Should probably be:
    Code:
    else
    {
        ldepth = 1 + maxdepth(n->left);
        rdepth = 1 + maxdepth(n->right);
    #4 At some point before the program ends you should think about taking care of the memory you've allocated for the nodes.
    Last edited by hk_mp5kpdw; 05-12-2009 at 09:32 AM.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  5. #5
    Registered User
    Join Date
    May 2009
    Posts
    6
    Thanks for your reply. I've still no idea why it won't run properly on my computer. The printTree function also causes it to crash after it outputs one or two numbers. very strange!

    Hadn't forgotten about deallocating the memory don't worry, just hadn't gotten around to it yet, being preoccupied with the insert function. Have a deleteTree function in there now.

    Thanks for the help ,
    Lydia

  6. #6
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by lydiab View Post
    oops, sorry about the identation! i'm usually the only one who has to read my code so I just stick with the identation dev c++ gives me!
    I downloaded Dev-C++ last week, figuring I'd give it a chance... I tossed it out the window because of the indentation (or rather, complete lack thereof). I tried fiddling settings. Nothing I did made it do anything reasonable. Ugh.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  7. #7
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    One thing I've noticed, your node creation function does no checking that the malloc call has succeeded. You can try altering that function a bit:
    Code:
    node* newNode(int data) { //create a new node 
        node* n = NULL;
        n = malloc(sizeof(node));
        if( n != NULL )
        {
            n->data = data;
            n->right = NULL;
            n->left = NULL;
        }
        return n;
    }
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by brewbuck
    I downloaded Dev-C++ last week, figuring I'd give it a chance... I tossed it out the window because of the indentation (or rather, complete lack thereof). I tried fiddling settings. Nothing I did made it do anything reasonable. Ugh.
    Did you disable smart tabs? It was the first thing I always did for a new installation back when I used Dev-C++.

    Quote Originally Posted by hk_mp5kpdw
    One thing I've noticed, your node creation function does no checking that the malloc call has succeeded. You can try altering that function a bit:
    Good point, though I note that this:
    Code:
    node* n = NULL;
    n = malloc(sizeof(node));
    can be simplified to:
    Code:
    node* n = malloc(sizeof(node));
    though I prefer:
    Code:
    node* n = malloc(sizeof(*n));
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    May 2009
    Posts
    6
    I'm finding dev c++ to be a bit of a nightmare. Any code that works error free on the college unix computers always brings up errors in dev c++ or, like in this case, doesn't run properly. I have a feeling that it might be the cause of my problems here because I've done similar programs on the college computers without issues.

    I've changed that now to make sure it checks that the malloc function worked. Thanks!

  10. #10
    Registered User
    Join Date
    May 2009
    Posts
    6
    Quote Originally Posted by laserlight View Post

    Good point, though I note that this:
    Code:
    node* n = NULL;
    n = malloc(sizeof(node));
    can be simplified to:
    Code:
    node* n = malloc(sizeof(node));
    though I prefer:
    Code:
    node* n = malloc(sizeof(*n));
    What's the difference between :
    Code:
    node* n = malloc(sizeof(node));
    and
    Code:
    node* n = malloc(sizeof(*n));
    [/QUOTE]

    The first one is creating a chunk of memory the size of a node (is that right?) but what does the second one do? Does it create memory space for a pointer to n? what size would that be?

  11. #11
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    *n is whatever n points to (it dereferences the n pointer), which is in this case a node object/struct. The difference comes when you change the n pointer from a node to something else. In the case of:
    Code:
    node * n = malloc(sizeof(node));
    ...changing the type that n points to means you must remember to also change the "node" bit in the malloc call to match the new definition. If you use *n, then the compiler already knows what n points to (regardless of how many times you might change it during development) and you never need to remember to change it elsewhere. It helps ease maintenance of code and potentially eliminate bugs if you happened to make a change one place but forgot somewhere else.
    Last edited by hk_mp5kpdw; 05-12-2009 at 11:18 AM.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  12. #12
    Registered User
    Join Date
    May 2009
    Posts
    6
    Ah ok, I understand. That seems like a good way to use malloc then if it's gonna help eliminate bugs when programs get more complicated and I (more than likely )forget to change the malloc!

    Thanks

  13. #13
    Registered User
    Join Date
    Apr 2009
    Location
    Sunny, Malta in the Mediterranean
    Posts
    9
    For what it's worth, I stopped using Dev C++ due to my cpu going to 95% all the time when I'm debugging. I noticed this on a Vista pc and an XP laptop. I started using Code::Blocks. I find it has better use of colours for diferent items and the fact that you can visually tell which open brace belongs to which closing one. For me, a newbie, it is infinetely better.

    Accidentally, I'm also writing a BST and would like to find some not so difficult alternative to pre-order print the tree when the traverse function is in dll without using the printf from within the traverse function but from the calling program.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree - one last question
    By tms43 in forum C++ Programming
    Replies: 2
    Last Post: 11-14-2006, 03:58 AM
  2. Binary Search Tree - object instantiation problem
    By patricio2626 in forum C++ Programming
    Replies: 3
    Last Post: 11-14-2006, 02:11 AM
  3. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  4. Searching a binary search tree - doesn't work
    By Ariod in forum C Programming
    Replies: 1
    Last Post: 08-11-2005, 03:53 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

Tags for this Thread