迭代後序遍歷bst？

-1

我有兩個問題， 1）對於任何遞歸算法，都存在迭代算法，對嗎？我認爲這是正確的，因爲你只需要明確地使用堆棧。並且在這個問題上得到確認 Way to go from recursion to iteration 迭代後序遍歷bst？

2）可能與上面的問題相同，我真的不認爲迭代解決方案是明顯的或簡單的甚至用遞歸算法來編寫。例如：對於一個後置訂單（LRN）或inorder（LNR）bst遍歷，你怎麼能用迭代方法來編寫它？在這兩種情況下，找到第一個插入堆棧的對象並不容易。那就是我陷入困境的地方。

有什麼建議嗎？實際上，我的目的與上述問題相同，試圖找到一種將遞歸算法更改爲迭代算法的一般模式。

來源

2011-05-24 user268451

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

瞭解這一點的最好方法是在每次調用時繪製內部堆棧的函數並返回遞歸版本。

來源

2011-05-24 14:31:50

迭代後序遍歷bst？

回答

相關問題