非递归的后序遍历c++
时间: 2023-09-26 22:09:08 浏览: 45
以下是非递归的后序遍历的C++代码:
```c++
void postorderTraversal(Node* root) {
if (!root) {
return;
}
stack<Node*> s;
s.push(root);
Node* prev = NULL;
while (!s.empty()) {
Node* curr = s.top();
if (!prev || prev->left == curr || prev->right == curr) {
// Traverse down the tree
if (curr->left) {
s.push(curr->left);
} else if (curr->right) {
s.push(curr->right);
}
} else if (curr->left == prev) {
// Traverse up the tree from left
if (curr->right) {
s.push(curr->right);
}
} else {
// Traverse up the tree from right
cout << curr->val << " ";
s.pop();
}
prev = curr;
}
}
```
在这个算法中,我们使用一个栈来模拟递归的行为。我们从根节点开始将节点压入栈中,然后进入一个循环,直到栈为空。在循环中,我们每次将栈顶的节点取出,然后判断其子树是否已经遍历完成,如果是,则将节点的值输出并将节点弹出栈;否则,我们将节点的右子树和左子树依次压入栈中。
在这个算法中,我们使用一个变量`prev`来记录上一个被访问的节点。如果当前节点的左子节点或右子节点是`prev`,则说明需要向上遍历树;否则,说明需要向下遍历树。