Resources » Articles/Knowledge Sharing » Education

Storage representation of binary tree using thread.


Posted Date: 09-Jul-2011  Last Updated:   Category: Education    
Author: Member Level: Silver    Points: 10


In this article I will explain storage representation of binary tree. How threads are formed in representation are explained here. Threaded Storage representation of Tree is very efficient while traversing the tree in pre-order, in-order, post-order. This Article also shows example of representation of tree using threads.



Threaded storage representation of binary tree


Introduction


Basically in normal binary tree representation there are two links i.e. left and right link. Right link of node is points to address of right sub-tree and left link of node is points to address of left sub-tree. But when there is no sub-tree on its right or left than that link is replaced by NULL i.e. if left sub-tree is absent then left link of node is replaced by NULL, if right sub-tree is absent then right link of node is replaced by NULL.

When there is big tree having large number of nodes than it is wastage of memory while placing NULL. To Solve this wastage of memory problem threaded binary tree is introduced in which left or right link of nodes are replaced by address of other node according to particular traversal technique on which it is formed, these links are known as threads.

Thread link is denoted with dashed arrow.Head node serves as predecessor and successor of the first and last nodes with respect to particular traversal technique.

Normally in binary tree the valid pointers that pointed to left sub-tree or left sub-tree as considered as positive values or non-negative values. But in case of threaded binary tree threads are denoted by negative values because it is easily differentiated by regular pointers.

Before first node of tree is created head node is created, which is displayed as
Empty Tree

Example


Consider following example
a tree having 7 nodes are displayed as follows
Normal Tree

Now normal linked list representation are displayed here having NULL values.
LINKED TREE
Now to form threaded representation of above binary tree we have to form in-order traversal of above tree, which is CBAEFDG

Now its time to making threads.
1. Left link of node C is points to head and right link of node G points to head node because there is no node in in-order traversal
2. Right link of node C is points to address of node B because node B succeeds node C
3. Left link of node F is points to address of node E because node E precedes node F So like this all the NULL link is replaced by address of other node according to in-order traversal.

Threaded binary tree of main tree is presented as
Threaded Tree

Advantages


1. By using threaded binary tree traversing of tree is very faster as compared to normal representation of binary tree.
2. Other advantage of using threaded binary tree is anyone can easily find successor or predecessor of any node.

Disadvantages


1. One of the disadvantage using threaded binary tree is we can not share common sub-tree.
2. It is possibly to confuse which is threads and which are actual link.


Read related articles: Binary Tree Thread    Binary Tree    Storage Representation    Thread    

Did you like this resource? Share it with your friends and show your love!




Responses to "Storage representation of binary tree using thread."

No responses found. Be the first to respond...

Feedbacks      

Post Comment:




  • Do not include your name, "with regards" etc in the comment. Write detailed comment, relevant to the topic.
  • No HTML formatting and links to other web sites are allowed.
  • This is a strictly moderated site. Absolutely no spam allowed.
  • Name:   Sign In to fill automatically.
    Email: (Will not be published, but required to validate comment)



    Type the numbers and letters shown on the left.


    Submit Article     Return to Article Index

    Awards & Gifts
    Active Members
    TodayLast 7 Daysmore...

    ISC Technologies, Kochi - India. Copyright © All Rights Reserved.