迭代后置遍历BST？
|
我有两个问题，
1）对于任何递归算法，都有一个迭代算法，对吗？我认为这是正确的，因为您只需要显式使用堆栈即可。此问题已得到证实
从递归到迭代的方法
2）可能与上述问题相同，即使使用递归算法，我也不认为迭代解决方案是显而易见的或易于编写的。例如：对于后置（LRN）或inorder（LNR）遍历，如何用迭代方法编写？在这两种情况下，要找到要插入堆栈的第一个对象并不容易。那就是我被困住的地方。
有什么建议么？实际上，我的目的与上述问题相同，尝试找到一种将递归算法更改为迭代算法的通用模式。
没有找到相关结果
已邀请:
1 个回复
犀耽澄协吻
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; } } }