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
Linked lists are among the most common and easiest data structures. They may be used to implement various other common abstract data types, including queues, stacks, symbolic expre

explain the prims''s algorithm with suitable example?

1. Write a pseudocode algorithm to print the numbers from 1 to 10, and then from 10 to 1, using exactly one loop. 2. The function contains() takes a food as an argument and tell

one to many one to one many to many many to one

1. Use the Weierstrass condition, find the (Strongly) minimizing curve and the value of J min for the cases where x(1) = 0, x(2) = 3. 2. The system = x 1 + 2u; where

Let us assume a sparse matrix from storage view point. Assume that the entire sparse matrix is stored. Then, a significant amount of memory that stores the matrix consists of zeroe

One can change a binary tree into its mirror image by traversing it in Postorder is the only proecess whcih can convert binary tree into its mirror image.

Explain the representations of graph. The different ways of representing a graph is: Adjacency list representation : This representation of graph having of an array Adj of

The minimum cost spanning tree has broad applications in distinct fields. It represents several complicated real world problems such as: 1. Minimum distance for travelling all o

example of stack using flowchart