Perhaps the simplest way is to do a normal inorder traversal and, as
you visit nodes, keep track of the last one visited in an external
(global or class) variable. When you visit a new node and the last
node has a NULL right child pointer, you can update it with the new
node. If the new node has a NULL left child pointer, you can update it
with the last node.
// UNTESTED!
// Last tree node visited in order
static NODE *last;
// local recursive tree walk
static void do_enthreading(NODE *tree)
{
if (tree->left)
do_enthreading(tree->left);
else {
tree->left_child_is_thread = TRUE;
tree->left = last;
}
if (last && last->right == NULL) {
last->right_child_is_thread = TRUE;
last->right = tree;
}
last = tree;
if (tree->right)
do_enthreading(tree->right)
}
// Start the recursion and clean up afterward.
void enthread_tree(NODE *tree)
{
if (tree) {
last = NULL;
do_enthreading(tree);
last->right_child_is_thread = TRUE;
}
}
On Nov 25, 5:55 am, kumar raja <[email protected]> wrote:
> How to convert a given binary tree into threaded binary tree??
> what is the algorithm...
>
> --
> Regards
> Kumar Raja
> M.Tech(SIT)
> IIT Kharagpur,
> [email protected]
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
