Friday, March 9, 2012

What is Threaded binary tree?

The Binary tree traversals mostly involves stack manipulations which will take lot of memory. If the stack memory is low, Binary trees could be problems. Here comes the Threaded binary trees. These cane be useful where stack memory is limited or where stack of the parent pointers are not available.

Properties of threade binary tree:
  • if the left sub tree is empty, left link points to the in-order predecessor
  • if the right sub tree is empty, right link points to the in-order successor.



Fig: Threaded binary tree
 In-order traversals for the above binary tree is DBHEIAFCJG. As per the threaded binary tree rules , links are connected in the above image. The basic difference between binary tree and threaded binary tree is that in binary tree childs are null if there is no child associated with it, so there is no way to traverse back. Where as in threaded binary tree child nodes are assosiated with in-order successor or predessosor if no child assosiated with it. So back traversals is easy in this. There are many ways to implement the threaded binary tree. Below is the simple node structure for this.
struct node
{
    int info;
    struct node *left;
    struct node *right;
    //two boolian variables are true for only child nodes to make thread links. 
    bool llink,rlink; 
};

No comments:

Popular Posts