Page 211 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes struct NODE *right;
struct NODE *thread;
}
inorder(struct NODE *curr)
{
while(all the nodes are not over)
{
if(curr->left != NULL && ! visited(curr->left))
{
visit(curr->left);
curr = curr->left;
}
else
{
printf(“%d”, curr->value);
if(curr->right != NULL)
curr = curr->right;
else
if(curr->thread != NULL)
curr = curr->thread;
}
}
}
The looping condition has to be implemented. You can use your own logic for that. The
functions – visited( ) and visit( ) have to be written. Visit( ) maintains a linked list of already
visited nodes. Visited( ) returns a TRUE value if it finds a particular node, in the list maintained
by visit( ), otherwise FALSE.

Self Assessment

Fill in the blanks:
11. The process of systematically visiting all the nodes in a tree and performing some
computation at each node in the tree is called a ..........................

12. A binary tree is of ................................... nature.
13. In .........................., we visit the current node first, then we visit its left sub-tree and then its
right sub-tree.

14. A .......................... Binary Tree is a binary tree in which every node that does not have a
right child has a THREAD to its INORDER successor.
15. If the right sub-tree is not there, we check for the threaded link and make the threaded
node the .......................... node in consideration.

204 LOVELY PROFESSIONAL UNIVERSITY