Zorba the Hutt (zorbathut) wrote,
Zorba the Hutt

<Yuhjn> I'm reading a TOC for a datastruct book and one section is on "non-recursive binary tree traversal" ... this is obviously impossible so do you think they are talking about using your own stack to do your own recursion? (ie, no system stack)
<ZorbaTHut> it's not entirely impossible
<ZorbaTHut> if the tree has a "parent" node, it's quite possible.
<Yuhjn> hmm
<ZorbaTHut> though a little tricky to work out the logic :P but possible.
<ZorbaTHut> and how on earth do I know that?
<Yuhjn> naaa, using a parent pointer cannot avoid recursion as far as i can tell
<ZorbaTHut> I think it can.
<ZorbaTHut> *considers*
<Yuhjn> hrm, yes
<Yuhjn> appreanly it can
<ZorbaTHut> just takes some work. :)
<Yuhjn> http://datastructures.itgo.com/trees/nrtraversal.htm
<Yuhjn> you have to use a linked list as well
<ZorbaTHut> I think it may be possible to do it without the linked list also
<ZorbaTHut> I'm just not sure.
<ZorbaTHut> *considers*
<Yuhjn> you need it for your loop condition
<ZorbaTHut> if( curnode->right ) { curnode = curnode->right; while( curnode->left ) { curnode = curnode->left; } } else { . . . something nasty here involving which side of the parent this node is on . . . }
<ZorbaTHut> I think it may be possible.
<ZorbaTHut> can you prove it isn't? ;)
<Yuhjn> I've yet to see one that suggests a solution without a linked list
<Yuhjn> but no i probably cant prove it :)
<ZorbaTHut> ooh, I bet I can find one
<ZorbaTHut> yep. bingo.
<ZorbaTHut> MSVC.NET's iterator for trees contains, as data, _Nodeptr _Ptr; // pointer to node
<ZorbaTHut> and that's all.
<ZorbaTHut> and, yeah, the logic is the same as I was working out
<Yuhjn> O
<Yuhjn> I'm not convinced yet
<ZorbaTHut> if( curnode->right ) { curnode = curnode->right; while( curnode->left ) { curnode = curnode->left; } } else { while( curnode->parent && curnode->parent->right == curnode ) curnode = curnode->parent; curnode = curnode->parent; } return curnode->data;
<ZorbaTHut> and, yeah, that matches the algorithm in the MSVC STL. :P

where do I come up with this stuff? I know I've never seen the algorithm before . . . I might have heard it mentioned as possible, but I certainly don't remember it.


welcome to my life.
  • Post a new comment


    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.