How to make a threaded tree??

[netsuki]

I want to make my AVL tree threaded, so I can implement iterators. I've looked everywhere for how to implement threading, but all I find is examples of how to do the inorder traversal of an already threaded tree. What I want to know is how to actually implement the threading itself. I can't find a single example. Please help!

[Peter87]

What advantages would a threaded tree have? I'm just asking because I can't see how tree traversal could take advantage of multiple threads.

[netsuki]

I need it to be threaded so I can implement an iterator class for it. Threading is the only way I can think of that I would be able to easily implement iterators.

[Peter87]

When you say "threading", are you talking about this: http://en.wikipedia.org/wiki/Thread_%28computing%29 ... or something else?

If that's what you talking about you should now that all the iterators in the standard library works fine without threads.

[netsuki]

Oh, no not that at all. This: http://en.wikipedia.org/wiki/Threaded_binary_tree

Using a NULL right subtree pointer to instead point to the inorder successor.

[netsuki]

I'm not using the STL, and I have to implement the iterators on an AVL tree where I feel it would be more difficult to backtrack using a previous node pointer. I really just want to know how to implement threading as I can't find an example for it anywhere.

[Peter87]

Aha, now it makes more sense.

I don't really know much about that kind of threading but I found this http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_bst1.aspx#thread

EDIT: using a previous node pointer isn't really that difficult. My guess is that it's easier than using threading.

[netsuki]

I got stuck trying to implement a previous node pointer before.
http://www.cplusplus.com/forum/general/63746/

No one ever replied, so I tried to see if I could figure out threading. I am fairly sure I would know how to do the iterator once threading is established, but I'm pretty lost when thinking about how to write them using the previous. This is probably because I've never written an iterator before.