codebytes: Threaded Binary Tree : Construction and Inorder Traversal [Java]
Threaded Binary Trees: Instead of containing a null pointer in its right field, a node with an empty right subtree points to its inorder successor. Such a pointer is called a thread. Note that the rightmost node in each tree still has a null right pointer, since it has no inorder successor. Such trees are called right in--threaded binary trees. A threaded binary tree eliminates the need for a stack in a nonrecursive traversal even if a father field is not available.
To implement a right in-threaded binary tree under the dynamic node implementation of a binary tree, and extra logical field, rthread, is included within each node to indicate whether or not its right pointer is a thread. For consistency, the rthread field of the rightmost node of a tree (i.e. the last node in the tree's inorder traversal) is also set to true, although its right field remains null.
Read full article from codebytes: Threaded Binary Tree : Construction and Inorder Traversal [Java]
