PostOrder traversal: Is a method of visiting all nodes of a Binary
tree where the Left child of a node is visited first then the Right child of the node and in the end the Root(node). The term Post refers
to the position of the ROOT in the traversal result. The ROOT of the
tree is the last element in the result of this traversal.
deque(Pronunciation deck) is a data structure available in the C++ STL. Its a queue where insertions and deletions are done at both the ends.
deque(Pronunciation deck) is a data structure available in the C++ STL. Its a queue where insertions and deletions are done at both the ends.
/*
Wrapper function to call the recursive and non recursive methods.
*/
void LintkedIntTree::postOrder(bool isRecursive)
{
if(isRecursive == true)
{
postOrderRec(root);
}else
{
StacktNode* temp = new StacktNode(root,NULL);
StackInt* stack=new StackInt(temp,1);
postOrderNonRecDeck(stack);
stack=new StackInt(temp,1);
cout<<"\n POST Order COLOURING\n";
postOrderNonRecColour(stack);
}
return;
}
/*
Recursive implementation:
Logic:
the LeftChild is visited first
the Right child next
now its the root Print it out.
*/
void LintkedIntTree::postOrderRec(BinaryTreeIntNode* node)
{
if(node == NULL)
{
return;
}else
{
postOrderRec(node->left);
postOrderRec(node->right);
cout<<" "<<node->data;
return;
}
}
/*
NON Recursive implementation:
Logic:
push the root onto the stack
while Stack not empty
pop the node
push_front onto a deque(is a datastructure in which the insertions can be done either in the front or back,
push_front inserts from the back of the deque)
push the left child(we push the left child first as we are populating the traversal from behind and we need the right child first)
push the right child
end while
*/
void LintkedIntTree::postOrderNonRecDeck(StackInt* stack)
{
std::deque<int>* deck= new deque<int>();
if(stack == NULL)
{
return;
}
while(!stack->isEmpty())
{
StacktNode* temp = stack->pop();
if(temp==NULL)
{
continue;
}
BinaryTreeIntNode* t = temp->node;
temp->~StacktNode();
deck->push_front(t->data);
if(t->left!= NULL)
{
StacktNode* l= new StacktNode(t->left,NULL);
stack->push(l);
}
if(t->right != NULL)
{
StacktNode* r = new StacktNode(t->right,NULL);
stack->push(r);
}
}
deque<int>::iterator it;
it = deck->begin();
int x =deck->size();
cout<<"DECK SIZE = "<<x <<endl;
while(it!=deck->end())
{
cout<<" "<<*it++;
}
}
No comments:
Post a Comment