iterative postorder traverse bst?

I have two questions, 1) for any recursive algorithm, there exists a iterative algorithm, is that right? I think it's right, because you just have to use the stack explicit.And it is confirmed in this question Way to go from recursion to iteration

2) probably the same question like the above one, I really dont think the iterative solution is obvious or easy to write even with the recursive algorithm. For example: for a postorder (LRN) or inorder(LNR) bst traverse, how could you write it with iterative method? In these two cases, it's not easy to find the first object to insert into the stack. That's where I got stuck.

Any suggestions? Actually, my p开发者_运维问答urpose is the same as the above question, try to find a general pattern to change recursive algorithm to iterative ones.

I feel you haven't asked the question properly. I will try to answer the question as to how one can think about implementing the iterative version of in-order traversal(I just happen to have given this some thought and implemented it very recently. I feel I will help myself too by putting this down) given that one knows the recursive version.

Each function call in a recursive version seeks to visit the node associated with the function call. The function is coded such that activation-frame corresponding to a node is saved onto the system stack(stack area of that process) before the it can do its main job, i.e. visit the node. This is so because we want to visit the left subtree of the node before visiting the node itself.

After the left subtree is visited, a return to the frame of our saved node results in the language environment popping the same from the internal stack and a visit to our node is now allowed.

We have to mimic this pushing and popping with an explicit stack.

template<class T>
void inorder(node<T> *root)
{
    // The stack stores the parent nodes who have to be traversed after their
    // left sub-tree has been traversed
    stack<node<T>*> s;

    // points to the currently processing node
    node<T>* cur = root;

    // Stack-not-empty implies that trees represented by nodes in the stack
    // have their right sub-tree un-traversed
    // cur-not-null implies that the tree represented by 'cur' has its root
    //   node and left sub-tree un-traversed
    while (cur != NULL || !s.empty())
    {
        if (cur != NULL)
        {
            for (; cur->l != NULL; cur = cur->l) // traverse to the leftmost child because every other left child will have a left subtree
                s.push(cur);
            visit(cur); // visit him. At this point the left subtree and the parent is visited
            cur = cur->r; // set course to visit the right sub-tree
        }
        else
        {// the right sub-tree is empty. cur was set in the last iteration to the right subtree
            node<T> *parent = s.top();
            s.pop();
            visit(parent);
            cur = parent->r;
        }
    }
}

The best way to understand this is to draw the functioning of the internal stack on paper on each call and return of the recursive version.