Binary tree problem

This is a discussion on Binary tree problem within the C++ Programming forums, part of the General Programming Boards category; hello, I wrote a recursive function to try and find the depth of a binary tree, but when I run ...

  1. #1
    Registered User
    Join Date
    Jun 2007
    Posts
    26

    Binary tree problem

    hello,

    I wrote a recursive function to try and find the depth of a binary tree, but when I run the program I keep getting an invalid memory access error.

    A couple notes about the tree. The tree is NOT a linked list (not my choice), it is basically a giant array with indices of the daughters rather than pointers. Also, every box will be gauranteed to have two daughters.

    Code:
    int findNumLayers(int currentLayer,int whichBox, KDtree<DIM> myTree) {
        int branch1=0,branch2=0;   
        cout << "CurrentLayer = " << currentLayer << endl;
        cout << "WhichBox = " << whichBox << endl;
        //Every Leaf should have two daughters
        if(myTree.boxes[whichBox].dau1 != 0 && myTree.boxes[whichBox].dau2 != 0) {
            //Increment tree depth
            currentLayer++;  
            //Find depth of each branch
            branch1 = findNumLayers(currentLayer,myTree.boxes[whichBox].dau1,myTree);
            branch2 = findNumLayers(currentLayer,myTree.boxes[whichBox].dau2,myTree);
        }
        //Return maximum branch depth
        else if (currentLayer < branch1 && branch1 > branch2) return branch1;
        else if (currentLayer < branch2 && branch1 < branch2) return branch2;
        else return currentLayer;
    }
    The output I get when running this is
    Code:
    Number of Boxes: 8191
    CurrentLayer = 0
    WhichBox = 0
    CurrentLayer = 1
    WhichBox = 1
    CurrentLayer = 2
    WhichBox = 4097
    CurrentLayer = 3
    WhichBox = 6145
    CurrentLayer = 4
    WhichBox = 7169
    CurrentLayer = 5
    WhichBox = 7681
    CurrentLayer = 6
    WhichBox = 7937
    CurrentLayer = 7
    WhichBox = 8065
    CurrentLayer = 8
    WhichBox = 8129
    CurrentLayer = 9
    WhichBox = 8161
    CurrentLayer = 10
    WhichBox = 8177
    CurrentLayer = 11
    WhichBox = 8185
    CurrentLayer = 12
    WhichBox = 8189
    Invalid memory access of location 1adf2ebc eip=1ad0c89e
    I was able to calculate that there should be 12 layers in this example, so I think the problem lies in the return statement, although I can't seem to find it myself.

    All help is appreciated.

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,788
    What happens after the "if" portion of the code gets executed? Does the function return any value?

    ...may not be the issue, but it is "return" related.
    "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

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,344
    Use a debugger, let it catch the invalid memory access, then start working your way back to the problem.
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    Jun 2007
    Posts
    26
    The problem with trying to use the debugger, is this C++ code is run through JAVA's JNI. I tried the debugger, but it was unhelpful.

    I changed the return statement to something simple, such as "return 5;". I'm still getting the same issue. I can put print statements after the if statement and they execute fine.

    EDIT: Just as a side note, I'm using the Netbeans IDE for the main editing but compiling my C++ code from command line using g++
    Last edited by moddinati; 06-19-2008 at 01:38 PM.

  5. #5
    Registered User
    Join Date
    Jun 2007
    Posts
    26
    Another Note, comment out the line
    Code:
    branch2 = findNumLayers(currentLayer,myTree.boxes[whichBox].dau2,myTree);
    So it only goes down one branch of the tree, it seems to work fine.

    I still need to to traverse the entire tree though.

  6. #6
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    > else if (currentLayer < branch1 && branch1 > branch2) return branch1;
    This shouldn't be an else if. If you print out the values of branch1 and branch2 at this point, branch1 will equal 0, and so will branch2.

  7. #7
    Registered User
    Join Date
    Jun 2007
    Posts
    26
    thanks swoopy, fixed that issue.

    That still doesn't resolve my main issue.

    I did notice though, that (when I only traverse half the branch so it actually works), that as I return to java i get the following message

    Code:
    malloc: ***  Deallocation of a pointer not malloced: 0x1ad64000; This could be a double free(), or free() called with the middle of an allocated block;
    I get this message 12 times, the number of times my recursive function gets called. This makes no sense to me. Any ideas?

    EDIT: So I just started commenting stuff out until it works. I don't think it has anything to do with the recursive function. I commented the entire function out except for a single return statement, and I still got one of the errors above. I then commented out my input parameter 'KDtree<DIM> myTree' and it runs fine. Thanks for the help guys, I think this may be more of a JNI issue than a C++ issue. I'll move to some JNI forums.
    Last edited by moddinati; 06-19-2008 at 03:24 PM.

  8. #8
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    >I then commented out my input parameter 'KDtree<DIM> myTree' and it runs fine.
    It probably won't help, but you might try passing myTree as a reference:
    Code:
    int findNumLayers(int currentLayer,int whichBox, KDtree<DIM> &myTree) {

  9. #9
    Registered User
    Join Date
    Jun 2007
    Posts
    26
    That was exactly the problem. Thanks swoopy, everything works great now.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 01:02 PM
  2. binary tree problem
    By spank in forum C Programming
    Replies: 4
    Last Post: 04-24-2006, 05:27 AM
  3. problem in storing data in a binary search tree
    By alavardi in forum C Programming
    Replies: 5
    Last Post: 02-13-2005, 02:20 PM
  4. Tree Problem
    By recluse in forum C Programming
    Replies: 36
    Last Post: 12-04-2004, 02:06 PM
  5. Array, Linked List, or Binary Tree?
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 01-05-2002, 09:07 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21