void MyTree::TraversePostorder( void (*pfnVisit)(void *) )
{
NODE *p = m_proot;
NODE *upfromthisnode = NULL;
m_pstack->clear();
while( p ) {
if( upfromthisnode ) {
// we just popped up from a lower node.
if( upfromthisnode==p->pleft && p->pright ) {
// go right
upfromthisnode = NULL;
m_pstack->push( p );
p = p->pright;
} else {
// either came up from the right, or up from
the left but there is no right
ASSERT( !p->pright || upfromthisnode==p->pright
); // just make sure :)
(*pfnVisit)( p->payload );
upfromthisnode = p;
p = (NODE *)m_pstack->pop();
}
} else {
// we came down from the parent. Go down unless we're
at a leaf.
if( p->pleft ) {
m_pstack->push( p );
p = p->pleft;
} else if ( p->pright ) {
m_pstack->push( p );
p = p->pright;
} else {
// we're at a leaf
(*pfnVisit)( p->payload );
upfromthisnode = p;
p = (NODE *)m_pstack->pop();
}
}
}
On Sun, Jan 18, 2009 at 6:14 PM, Miroslav Balaz <gpsla...@googlemail.com>wrote:
> you will use stack, and you have 2 kind of values in stack, one is visit
> node first time, and second is wisit node for second time
>
> when first time: you put visit this node for second time and then you put
> visit nododes for first time to stack for all descendands
>
> when second time: you calculate value, and store it in array
>
>
> if you want to just print the order, you only write its value when you are
> second time in the node
>
>
> This approach is not simulation of procedure call. It is more like using
> Stack instead of queue, in BFS search, to get DFS search.
>
>
> 2009/1/18 algorithm <prabagara...@gmail.com>
>
>
>> how to solve post - order traversal without using recursion ?
>>
>>
>>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
