Question
|
Difficulty Level:
2
|
Solution
|
Explanation Quality:4
|
It's a good idea to know these three tree traversal algorithms since they can also
be asked in relation to other questions. First let us understand each of these algorithms
and see some examples and then we will write the code for each. Say we have the
following tree:
In-Order Traversal
In order traversal of a tree means visiting the left child first, then the parent
and finally the right child. Let's apply this scheme on our tree
Now note that we actually have a subtree rooted at the left child 2 and another
subtree rooted at right child 6. We apply the same algorithm recursively on these
subtrees.
Now subtree at 2 expands as:
Now subtree at 6 expands as:
Now we simply substitute these expanded subtrees back
(2) 4 (6)
(1 2 3) 4 (5 6 7)
1 2 3 4 5 6 7
The code for in order traversal is given as follows:
void InOrderTraversal(*node){
if(!node->leftChild && !node->rightChild){
cout<<"Print value"<<node->value<<endl;
return;
}
if(node->leftChild)
InOrderTraversal(node->leftChild);
cout<<"Print value"<<node->value<<endl;
if(node->rightChild)
InOrderTraversal(node->rightChild);
}
Post-Order Traversal
For the post-order traversal we visit the left child first, the right child second
and finally the parent
(2) (6) 4
(1 3 2) (5 7 6) 4
1 3 2 5 7 6 4
The code for post-order traversal is as follows:
void PostOrderTraversal(*node){
if(!node->leftChild && !node->rightChild){
cout<<"Print value"<<node->value<<endl;
return;
}
if(node->leftChild)
InOrderTraversal(node->leftChild);
if(node->rightChild)
InOrderTraversal(node->rightChild);
cout<<"Print value"<<node->value<<endl;
}
Pre-Order Traversal
Pre-order traversa means we visit the parent first, then the left child and finally
the right child. That is we visit the children first and then the parent. For our
tree the expansion would look like as follows:
4 (2) (6)
4 (2 1 3) (6 5 7)
4 2 1 3 6 5 7
The code for pre-order traversal is as follows:
void PreOrderTraversal(*node){
if(!node->leftChild && !node->rightChild){
cout<<"Print value"<<node->value<<endl;
return;
}
cout<<"Print value"<<node->value<<endl;
if(node->leftChild)
InOrderTraversal(node->leftChild);
if(node->rightChild)
InOrderTraversal(node->rightChild);
}
|