迭代后序遍历bst？

问题描述：

我有两个问题， 1）对于任何递归算法，都存在迭代算法，对吗？我认为这是正确的，因为你只需要明确地使用堆栈。并且在这个问题上得到确认 Way to go from recursion to iteration 迭代后序遍历bst？

2）可能与上面的问题相同，我真的不认为迭代解决方案是明显的或简单的甚至用递归算法来编写。例如：对于一个后置订单（LRN）或inorder（LNR）bst遍历，你怎么能用迭代方法来编写它？在这两种情况下，找到第一个插入堆栈的对象并不容易。那就是我陷入困境的地方。

有什么建议吗？实际上，我的目的与上述问题相同，试图找到一种将递归算法更改为迭代算法的一般模式。

1）是的。 2）我相信你链接的问题已经回答了你自己的问题。请仔细阅读那里的答案。 – 2011-05-24 07:58:25

那么你真正的问题是什么？只要搜索迭代树遍历就可以得到一堆链接，也可以在[wikipedia]（http://en.wikipedia.org/wiki/Tree_traversal）上找到。 – zvrba 2011-05-24 08:43:19

答

我觉得你还没有正确地问过这个问题。我会试着回答一个问题，那就是如何考虑实现迭代版本的有序遍历（我恰好在最近给了这个思想并实现了它，我觉得我也会帮助自己，把它放下）因为知道递归版本。

递归版本中的每个函数调用都试图访问与函数调用相关的节点。该功能被编码为使得与节点相对应的激活帧在其能够完成其主要工作（即访问该节点）之前被保存到系统堆栈（该过程的堆栈区域）上。这是因为我们想在访问节点本身之前访问节点的左侧子树。

访问左侧子树后，返回到我们保存的节点的框架会导致语言环境从内部堆栈中弹出相同，并且现在允许访问我们的节点。

我们必须用明确的堆栈来模拟这种推送和弹出。

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; 
     } 
    } 
}

了解这一点的最好方法是在每次调用时绘制内部堆栈的函数并返回递归版本。

迭代后序遍历bst？

相关推荐