Tree Pointers

This is a discussion on Tree Pointers within the C Programming forums, part of the General Programming Boards category; Lets say I have a simple tree such as this: Code: struct tree { int item; struct treeNode *left; struct ...

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    16

    Tree Pointers

    Lets say I have a simple tree such as this:

    Code:
    struct tree {
        int  item;
        struct treeNode *left;
        struct treeNode *right;
      };
    I can point ahead manually a few nodes ahead with the syntax:

    mytree->left->right->right;

    If I want to a pointer to a node x amount of nodes ahead how does one do this? I know the position of the node I want, but I do not know how to get a pointer to it.

    I can do the syntax:

    Code:
    BINARY_TREE *t;
    t = &mytree->right
    but what I want to be able to do is essentially:

    Code:
    t = &(t->right);
    but it doesn't work and I don't know why.
    Last edited by RedWind; 12-04-2008 at 02:06 PM.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    What do you mean by "know the position of the node"?

    Is this a binary search tree, or just a regular tree?

    What are you actually trying to accomplish?

  3. #3
    Registered User
    Join Date
    Sep 2008
    Posts
    16
    I've already looked ahead to a an item that's say 7 layers deep. However based on the item of the node 7 layers deep I need to change the node of an item 4 layers deep. So I know where it is however I do not have a pointer to it.

    I want to be able to recursively move a pointer down the tree until I get to the item I want,

    EDIT: meant to say:
    t = &(t->right);
    not
    t = &(t->second);

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    So you currently looking at item X. How do you know where item Y is? Is it the great-grandparent of the node you've got, or some other node that's three levels up?

  5. #5
    Registered User
    Join Date
    Sep 2008
    Posts
    16
    Quote Originally Posted by tabstop View Post
    So you currently looking at item X. How do you know where item Y is? Is it the great-grandparent of the node you've got, or some other node that's three levels up?
    great-grandparent

  6. #6
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    This tree is not currently designed to be looking upward easily. So perhaps you can simply add a pointer to the previous node as part of the structure.

  7. #7
    Registered User
    Join Date
    Sep 2008
    Posts
    16
    To look ahead in my tree I'm sending copies of it to functions (as these trees may also be manipulated in ways I don't want my main tree to be), so even if I have a pointers to previous nodes, they will change the previous nodes of the copies of the tree not the node of my main tree, so I still have the same problem.

    Can anyone give me the correct syntax for moving down in a tree in (for example) a for-loop such as

    Code:
    int i;
    for(i = 0; i<variable;i++)
    {
       t = &(t->right);
    }

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    In the for-loop, the & is extra -- it should just be t = t->right.

  9. #9
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    602
    You could view the stack within GDB, if you happen to know how much memory is used up per recursive call as addresses grow down the stack by subtraction. If you know the address at depth layer 7, then add back in the the amount of memory to place you back to depth layer 4. This may sound a bit convoluted and probably ill advised. Just a thought.

  10. #10
    Registered User
    Join Date
    Sep 2008
    Posts
    16
    Quote Originally Posted by tabstop View Post
    In the for-loop, the & is extra -- it should just be t = t->right.
    I get the errors with that code:

    "error: request for member 'right' in something not a structure or union"

  11. #11
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Probably best if you post (a bit of) the code in question.

    --
    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.

  12. #12
    Registered User
    Join Date
    Sep 2008
    Posts
    16
    There's not really anything to show, all I'm literally doing is sticking in three lines of code:
    Code:
    BINARY_TREE *t;
    t = &myTree->left;
    t = t->right;
    the code
    Code:
    myTree = myTree->right;
    works fine so I don't know what to do..

  13. #13
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    So how is BINARY_TREE defined? Since you take the address of myTree->left, I presume it is a BINARY_TREE is a struct tree *, whcih make t a pointer to a pointer to struct tree. If that's the case, you need (*t)->right. Parenthesis are necessary, as -> binds before *, so *t->right means whatever right points to, whilst (*t)->right means the member right pointed to by the the value pointed to by t. [Sorry, writing out how pointers works is quite "wordy"].

    --
    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.

  14. #14
    Registered User
    Join Date
    Sep 2008
    Posts
    16
    Yay! ok the correct code that works is t = &(*t)->right;

    I've been trying for ages to figure out how to that -I originally before my thread almost had it with t = &(*t->right). Thanks a lot

    EDIT: Try wording what the pointer 't' is actually pointing to coherently - it's impossible!
    Last edited by RedWind; 12-04-2008 at 04:14 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  3. Building B-Tree from Arrays
    By 0rion in forum C Programming
    Replies: 1
    Last Post: 04-09-2005, 02:34 AM
  4. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 04:15 PM
  5. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 03:53 AM

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