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

Q. Write an algorithm that counts number of nodes in a linked list.                                       A n s . Algo rithm to Count No. of Nodes in Linked List C

algorithm of output restricted queue.

Draw trace table and determine output from the following flowchart using following data: Number = 45, -2, 20.5

By taking an appropriate example explain how a general tree can be represented as a Binary Tree.                                                                    C onversio

How to construct a data flow diagram for a college assignment and marking systemA

Threaded Binary Tree:- By changing the NULL lines in a binary tree to special links known as threads, it is possible to perform traversal, insertion and deletion without using

Have you ever thought about the handling of our files in operating system? Why do we contain a hierarchical file system? How do files saved & deleted under hierarchical directories

Any binary search tree must contain following properties to be called as a red-black tree. 1. Each node of a tree should be either red or black. 2. The root node is always bl

Explain Floyd's algorithm It is convenient to record the lengths of shortest paths in an n by n matrix D known as the  distance matrix: the element d ij   in the i th   row an