>any helpful hints would be appreciated
You're on the right track. Consider this logic:
Code:
if root == null
return
v = not_seen
stack = root, not_seen
root = root.left
while stack != empty
if root != null && v == not_seen
stack = root, not_visited
root = root.left
else
root, v = stack
if v == not_visited
stack = root, visited
root = root.right
v = not_seen
else
visit ( root )
And since I've effectively given you the solution, here is the above pseudocode translated into C/C++ (don't look if you want to do it yourself ):
Code:
#define NOT_SEEN 0
#define NOT_VISITED 1
#define VISITED 2
void pretree_postorder (
struct pretree_node *header,
void (*action) ( struct pretree_node *node ) )
{
struct save_stack {
struct pretree_node *node;
int visited;
} save[50];
int top = 0;
int visited = NOT_SEEN;
if ( header == NULL )
return;
save[top].node = header;
save[top++].visited = NOT_VISITED;
header = header->link[0];
while ( top != 0 ) {
if ( header != NULL && visited == NOT_SEEN ) {
save[top].node = header;
save[top++].visited = NOT_VISITED;
header = header->link[0];
}
else {
header = save[--top].node;
visited = save[top].visited;
if ( visited == NOT_VISITED ) {
save[top].node = header;
save[top++].visited = VISITED;
header = header->link[1];
visited = NOT_SEEN;
}
else
action ( header );
}
}
}