Page 210 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 12: Introduction to Trees

Notes
List of visited INORDER:
nodes:
step-1: 'A' has a left child i.e. B, which has not been B
visited. So, we put B in our "list of visited nodes" and B
becomes our current node in consideration.
step-2: 'B' also has a left child, 'D', which is not there in B D
our list of visited nodes. So, we put 'D' in that list and
make it our current node in consideration.
step-3: 'D' has no left child, so we print 'D'. Then we BD D
check for its right child. 'D' has no right child and thus
we check for its thread-link. It has a thread going till
node 'B'. So, we make 'B' as our current node in
consideration.
step-4: 'B' certainly has a left child but its already in our BD DB
list of visited nodes. So, we print 'B'. Then we check for
its right child but it doesn't exist. So, we make its
threaded node (i.e. 'A') as our current node in
consideration.
step-5: 'A' has a left child, 'B', but its already there in BDC DBA
the list of visited nodes. So, we print 'A'. Then we check
for its right child. 'A' has a right child, 'C' and its not
there in our list of visited nodes. So, we add it to that
list and we make it our current node in consideration.
step-6: 'C' has 'E' as the left child and its not there in B D C E D B A
our list of visited nodes even. So, we add it to that list
and make it our current node in consideration.
D B E A C

Algorithm is given as below:

1. Step-1: For the current node check whether it has a left child which is not there in the
visited list. If it has then go to step-2 or else step-3.
2. Step-2: Put that left child in the list of visited nodes and make it your current node in
consideration. Go to step-6.
3. Step-3: For the current node check whether it has a right child. If it has then go to step-4
else go to step-5.

4. Step-4: Make that right child as your current node in consideration. Go to step-6.
5. Step-5: Check for the threaded node and if its there make it your current node.
6. Step-6: Go to step-1 if all the nodes are not over otherwise quit.

C implementation is given below:
struct NODE
{
struct NODE *left;
int value;

LOVELY PROFESSIONAL UNIVERSITY 203