The threaded binary tree, Data Structure & Algorithms

By changing the NULL lines in a binary tree to the special links called threads, it is possible to execute traversal, insertion and deletion without using either a stack or recursion.

In a right in threaded binary tree each NULL link is replaced by a particular link to the successor of that node under the inorder traversal called right threaded. Using right threads we shall find it easy to perform an inorder traversal of the tree, since we need to only follow either an ordinary link or a threaded to find the next node to visit.

If we replace each NULL left link by a particular link to the predecessor of the node known as left threaded under inorder traversal the tree is called as left in threaded binary tree. If both the left and right threads are present in tree then it is called as fully threaded binary tree for example:

303_threaded binary tree.png

Posted Date: 7/12/2012 9:18:45 AM | Location : United States







Related Discussions:- The threaded binary tree, Assignment Help, Ask Question on The threaded binary tree, Get Answer, Expert's Help, The threaded binary tree Discussions

Write discussion on The threaded binary tree
Your posts are moderated
Related Questions
One of the main problems with the linear queue is the lack of appropriate utilization of space. Assume that the queue can store 100 elements & the complete queue is full. Thus, it

: Write an algorithm to evaluate a postfix expression. Execute your algorithm using the following postfix expression as your input: a b + c d +*f ­ .

The best average behaviour is shown by  Quick Sort

include include include /* Definition of structure node */ typedef struct node { int data; struct node *next; } ; /* Definition of push function */

A binary tree is a tree data structures in which each node have at most two child nodes, generally distinguished as "right" and "left". Nodes with children are called parent nodes,

implement multiple stacks in a single dimensional array. write algorithm for various stack operation for them

An interesting application or implementation of trees is the playing of games such as tie-tac-toe, chess, nim, kalam, chess, go etc. We can depict the sequence of possible moves

Write an algorithm for compound interest.

CIRCULARLY LINKED LISTS IMPLEMENTATION A linked list wherein the last element points to the first element is called as CIRCULAR linked list. The chains do not specified first o

Suppose there are exactly five packet switches (Figure 4) between a sending host and a receiving host connected by a virtual circuit line (shown as dotted line in figure 4). The tr