Threaded Binary Trees
A binary tree with n nodes usually has n + 1 NULL nodes. The idea of a
threaded binary tree is to replace these NULL pointers with pointers to
nodes in the tree to aid in the preorder, inorder, and postorder
traversals of a binary tree. A nonrecursive tree traversal algorithm
results from using threads.
For purposes of this discussion we will define the following terms:
1) left inthreaded - each node that has a NULL left child is replaced with a pointer to the node's inorder predecessor.
2) right inthreaded - each node that has a NULL right child is replaced with a pointer to the node's inorder successor.
3) inthreaded - is a tree that is both left and right inthreaded.
Let's take a look at a possible iterative inorder tree traversal algorithm implemented in C using threads.
void fnThreadedInorderBT (TreeNodePtr psNode)
{
TreeNodePtr psTemp = psNode;
while (NULL != psTemp)
{
while (NULL != psTemp->psLeftChild)
{
psTemp = psTemp->psLeftChild;
}
printf ("%d", psTemp->data);
while (TRUE == psTemp->rightThread)
{
psTemp = psTemp->psRightChild;
printf ("%d", psTemp->data);
}
psTemp = psTemp->psRightChild;
}
}
P#2: Create an inthreaded tree for the above data.
P#3: Would the above algorithm algorithm work on an inthreaded tree? Why or why not?
P#4: If not, fix the above C function to handle an inthreaded tree.