Trees->Threaded Binary Tree->Concepts

	Trees->Threaded Binary Tree->Concepts
	A Threaded Binary Tree is a binary tree in which every node that does not have a right child has a THREAD (in actual sense, 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 consumes a lot of memory and time. The node structure for a threaded binary tree varies a bit and its like this -- struct NODE { struct NODE leftchild; int node_value; struct NODE rightchild; struct NODE thread; } Let's make the Threaded Binary tree out of a normal binary tree... The INORDER traversal for the above tree is -- D B A E C*. So, the respective Threaded Binary tree will be -- B has no right child and its inorder successor is A and so a thread has been made in between them. Similarly, for D and E. C has no right child but it has no inorder successor even, so it has a hanging thread. Clear! Related Operations: Trees %u2013 concepts Binary tree creation Traversals of a binary tree %u2013 preorder, inorder and postorder Binary threaded tree Non-recursive implementation of traversals Expressions-to-Trees Balanced trees / AVL trees %u2013 Creation and Balancing of a binary tree Balanced m-way tree / B-tree %u2013 Creation and balancing	Your Ad Here




Index \|\| Doubts / Clarifications \|\| Related Topics \|\| Web Links