Threaded Binary Tree, Data Structure & Algorithms

If a node in a binary tree is not containing left or right child or it is a leaf node then that absence of child node can be represented by the null pointers. The space engaged by these null entries can be utilized to store any kind of valuable information. One possible way to utilize or use this space is to have special pointer that point to nodes higher in the tree that is ancestors. Such special pointers are called threads and the binary tree having such pointers is called as threaded binary tree. There are various ways to thread a binary tree each of these  ways  either  correspond  either  in-order  or  pre-order  traversal  of  T. A Threaded Binary Tree is a type of binary tree in which every node that does not have a right child has a THREAD (or a link) to its INORDER successor. By doing this threading we avoid the recursive method of traversing a Tree, which makes use of stacks and wastes a lot of time and memory.

The node structure for a threaded binary tree differs a bit and its like this

struct NODE

{

struct NODE *leftchild;

int node_value;

struct NODE *rightchild;

struct NODE *thread;

}

The Threaded Binary tree made from normal binary tree...

2066_Threaded binary tree.png

The INORDER traversal for the above drawn tree is -- D B A E C. Then the respective

Threaded Binary tree will be --

1538_Threaded binary tree1.png

B does not have right child and its inorder successor is A and so a thread has been made in between them. Likewise, for D and E. C have no right child but it has no inorder successor even, therefore it has a hanging thread.

Posted Date: 7/10/2012 3:35:44 AM | Location : United States







Related Discussions:- Threaded Binary Tree, Assignment Help, Ask Question on Threaded Binary Tree, Get Answer, Expert's Help, Threaded Binary Tree Discussions

Write discussion on Threaded Binary Tree
Your posts are moderated
Related Questions
#include #include int sumFact(int numb); int calculateFactorial(int digit); main() { int numb, sumfact; do{ printf ("Enter a number 1 to 9999\n"); scanf("%

List various problem solving techniques. There are two techniques:- 1.  Top down 2.  Bottom- up

how we will make projects on stack in c?

The complexity of multiplying two matrices of order m*n and n*p is    mnp

Insertion & deletion of target key requires splaying of the tree. In case of insertion, the tree is splayed to find the target. If, target key is found out, then we have a duplicat

Explain an efficient way of storing a sparse matrix in memory.   A matrix in which number of zero entries are much higher than the number of non zero entries is called sparse mat

Abstract Data Types :- A useful tool for specifying the logical properties of a data type is the abstract data type or ADT. The term "abstract data type" refers to the basic mathem

The operations of the Symbol ADT The operations of the Symbol ADT are the following. a==b-returns true if and only if symbols a and bare identical. a symbol bin Unico

how do we use 4-discs stack to solve tower of hanoi problem and write an algorithm to solve it?

Define neotaxonomy. Discuss how electron microscopy can help in solving a zoological problem faced by taxonomist.