
Threads :
In my previous post I discussed about preorder , postorder and inorder binary tree traversals used stacks and level order traversals used queues as an auxiliary data structure . I highly recommend to know the basic binary tree traversals from the last post .In this article I will discuss new traversal algorithms which do not need both stacks and queues and such traversal algorithms and called Threaded Binary Tree Traversals or stack/queue less traversals .
Issues with regular Binary Tree Traversals :
 The storage space required for stack and queue is large .
 The majority of pointers in any binary tree are NULL . For example a binary tree with n nodes has n+1 NULL pointers and these were wasted .
 It is difficult to find successor node ( preorder ,inorder and postorder successors ) for a given node .
Motivation for Threaded Binary Trees :
To solve these problems , one idea is to store some useful information in NULL pointers . If we observe previous traversals carefully , stack/queue is required because we have to record the current position in order to move to right subtree after processing the left subtree . If we store the useful information in NULL pointers then we don't have to store such information in stack / queue. The binary trees which store such information in NULL pointers are called Threaded Binary Trees .The next question is what to store ?
The common convention is pust predecessor/successor information . That means , of we are dealing with preorder traversals then for a given node . NULL left pointer will contain preorder predecessor information and NULL right pointer will contain preorder successor information . These special Pointers are called Threads .
Classifying Threaded Binary Trees :
The classification is based on whether we are storing useful information in both NULL pointers or only on one of them , If we store predecessor information in NULL left pointers only then we call such binary trees as Left Threaded binary trees .
 If we store successor information in NULL right pointers only then we call such binary trees as right threaded binary trees .
 If we store predecessor information in NULL left pointers only then we call such binary trees as Fully threaded binary trees or simply threaded binary trees .
Types of Threaded Binary Trees :
Based on above forms we get three representations for threaded binary trees . Preorder Threaded Binary Trees : NULL left pointer will contain Preorder predecessor information and NULL right pointer will contain preorder successor information .
 Inorder Threaded Binary Trees : NULL left pointer will contain Inorder predecessor information and NULL right pointer will contain Inorder successor information .
 Postorder Threaded Binary Trees : NULL left pointer will contain Postorder predecessor information and NULL right pointer will contain Postorder successor information .
Threaded Binary Tree Structure :
Any program examining the tree must be able to differentiate between a regular left/right pointer and a thread . To do this we use two additional fields onto each node giving us for threaded trees nodes of the following form .struct threadedbtnodeAs an example let us try representing a tree in inorder threaded binary tree form . The below tree shows how an inorder threaded binary tree will look like . The dotted arrows indicated the threads . If we observe the left pointer of left most node (2) and right pointer of right most node node (31) are hanging.
{
struct threadedbtnode *left;
int Ltag;
int data;
int Rtag;
struct threadedbtnode *right;
};
Inorder Traversal of a Threaded Binary Tree :
To find inorder successor of a given node without using a stack , assume that the node for which we want to find the inorder successor is P.Strategy : If P has a no right subtree then return the right child if P. If P has right subtree then return the left of the nearest node whose ledt subtree contains P.
struct threadedbtnode * inordersuccessor(struct threadedbtnode *P) { struct threadedbtnode *position; if(P>Rtag==0) return P>right; else { position =P>right ; while(position>Ltag==1) position=position>left; return position; } };
Time complexity : O(n)
space complexity : O(1)
Inorder Traversal in Inorder Threaded Binary Tree : We can start with dummy node and call inordersuccessor() to visit each node until we reach dummy node .
void inordertraversal(struct threadedbtnode *root) { struct threadedbtnode *P=inordersuccessor(root); while(P!=root) { P=inordersuccessor(P); printf("%d",P>data); } }
Time complexity : O(n)
space complexity : O(1)
Inserting a Node into a Threaded Binary Tree
For simplicity let us assume that there are two nodes P and Q and we want to attach Q to right of P. For this we will have 2 cases .1. Node P does not has right child : In this case we just need to attach Q to P and change its left and right pointers .
2. Node P has right child (say R) : In this case we need to traverse R's left subtree and find the left most node and then update the left and right pointer of that node .
0 comments:
Post a Comment