|
|
Tree Traversal :
In order to process trees , we need a mechanism for traversing them and that forms the subject of this post . The process of visiting all the nodes of a tree is called Tree Traversal . Each of the nodes is processed only once but they may be visited more than once . As I had already discussed linear data structures ( like linked list , stacks , queues ,etc ) the elements are visited sequential order . But in three structures there are many different ways .Tree traversal is like searching the tree except that in traversal the goal is to move through the tree in some particular order . In addition , all nodes are processed in the traversal but searching stops when the required node is found .
Also check : Program for Merging two Linkedlist in C++
Traversal Posssibilities :
Starting at the root binary tree there are three main steps that can be performed and the order in which they are performed defines the traversal type .These steps are performing an action on the current node , traversing to the left child node and traversing to the right child node . This process can be easily described through recursion.Classifying the Traversals :
The sequence in which these entities processed defines a particular traversal method . There are 3 Traversal methods :1. Preorder Traversal
2. Inorder Traversal
3. Post order Traversal
Inorder Traversal :
In Inorder traversal the root is visited between the subtrees . Inorder traversal is defined as follows ,1. Traverse the Left subtree in Inorder .
2. Visit the root.
3. Traverse the right subtree Inorder .
Time complexity : O(n)
Space complexity : O(n)
Example :
Inorder traversal : C B D A F E I H G
Program:
void inorder(stuct binarytreenode *root)
{
inorder(root->left);
printf("%d",root->data);
inorder(root->right);
}
Preorder Traversal :
In preorder traversal , each node is processed before ( pre) either of its sub trees . This is the simplest traversal to understand . However , even though each node is processes before the subtrees , it still requires that some information must be maintained while moving down the tree . In the example above , the 1 is processed first , then the left sub tree followed by the right subtree .Therefore , processing must return to the right sub tree after finishing the processing left sub tree we must maintain root information . The obvious ADT for such information is a stack .Because of its "Last in First Out " Structure it is possible to get the information about the right subtrees back in the reverse order .Preorder traversal is defined as follows ,
1. Visit the root
2. Traverse to the left subtree in preorder
3. Traverse the right subtree in preorder
Time complexity :O(n)
Space complexity : O(n)
Program :
void preorder(struct binarytreenode *root)
{
if(root)
{
printf("%d",root->data);
preorder(root->left);
preorder(root->right);
}
}
Non Recursive Preorder Traversal :
In recursive version a stack is required as we need to remember the current node so that after completing the left structures we can go to right subtree .To simulate the same , first we process the current node and before going to the left subtree , we store the current node on stack . After completing the left subtree processing , pop the element and go to its right subtree .Continue this process until stack is nonempty .Time complexity : O(n)
Space complexity : O(n)
Example :
Pre Order Traversal : A B D E F C G H J L M K O
void preorder(struct binarytreenode *root)
{
struct stack *s=createstack();
while(1)
{
printf("%d",root->data);
push(s,root);
root=root->left;
}
if(isemptystack(s))
break;
root=pop(s);
root=root->right;
deletestack(s);
}
Postorder Traversal :
In postorder traversal , the root is visited after both subtrees . Postorder traversal is defined as follows ,1. Traverse the left subtree in postorder .
2. Traverse the right subtree in postorder
3. Visit the root .
Time complexity : O(n)
Space complexity : O(n)
void postorder(struct binarytreenode *root)
{
struct stack *s=createstack();
while(1)
{
if(root)
{
push(s,root);
root=root->left;
}
else
{
if(isemptystack(s))
{
printf("Stack is empty");
return ;
}
else if(top(s)->right==NULL)
{
root=pop(s);
printf("%d",root->data);
if(root==top(s)->right)
{
printf("%d",top(s)->data);
pop(s);
}
}
if(!isempty(s))
root=top(s)->right;
else
root=NULL;
}
}
deletestack(s);
}
Non Recursive Postorder Traversal :
In preorder and inorder traversals , after poping the stack element we do not need to visit the same vertex again . But in postorder traversal each node is visited twice . That means after processing left subtree we will be visiting the current node and also after processing the right subtree we will be visiting the same current node . But we should be processing the node during the second visit . Here the problem is how to differentiate whether we are returning from left subtree or right subtree ?Trick for this problem is after popping an element from stack , check whether that element and right of top of the stack are same or not . If they are same then we are done with processing of left subtree and right subtree .In this case we just need to pop the stack one more time and print its data .
Iterative Inorder Traversal :
To implement inorder iterator first we need to implement the inorder traversal method using non-recursion method shown in the program.Non Recursive inorder Traversal:
Non recursive version of inorder traversal is very much similar to Preorder. The only change is, instead of processing the node before going to left subtree, process it after popping (which indicates after completion of left subtree processing):Time Complexity: O(n).
Space Complexity: O(n).
We use the function Norrecinorder to abtain an inorder iterator for a tree.
Program contains the class definition of Inorderiterator. The constructor for this class initializes current Node to the tree root. The code implemented by using Next ( ) corresponding to a single iteration of the while loop. instead of visiting the next element, we return this element, Program gives the resulting code.
Level Order Traversal :
Level order traversal is defined as follows :1. Visit the root.
2. While traversing level 1 , keep all the elements at level 1 + 1 in queue .
3. Go to the next level and visit all the nodes at that level .
4. Repeat this until all levels are completed .
0 comments:
Post a Comment