Trees->Threaded Binary tree->Concept

	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 – concepts Binary tree creation Traversals of a binary tree – preorder, inorder and postorder Binary threaded tree Non-recursive implementation of traversals Expressions-to-Trees Balanced trees / AVL trees – Creation and Balancing of a binary tree Balanced m-way tree / B-tree – Creation and balancing




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