用c++代码实现二叉树后序遍历的非递归算法:结点要入两次栈,出两次栈;为了区别同一个结点的两次出栈,设置标志flag,当结点进、出栈时,其标志flag也同时进、出栈。
时间: 2024-03-18 18:42:16 浏览: 96
好的,下面是用C++实现二叉树后序遍历的非递归算法的代码:
```c++
#include <iostream>
#include <stack>
using namespace std;
// 二叉树结点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
bool flag; // 标志是否被访问过
TreeNode(int x) : val(x), left(NULL), right(NULL), flag(false) {}
};
// 非递归后序遍历
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
stack<TreeNode*> s;
TreeNode* cur = root;
TreeNode* last = NULL; // 标记上一个被访问的结点
while (cur != NULL || !s.empty()) {
// 将左子树全部入栈
while (cur != NULL) {
s.push(cur);
cur = cur->left;
}
// 获取栈顶结点
cur = s.top();
// 右子树为空或右子树已被访问过
if (cur->right == NULL || cur->right == last) {
// 访问当前结点
cout << cur->val << " ";
// 标记当前结点已被访问过
cur->flag = true;
// 出栈
s.pop();
// 标记上一个被访问的结点
last = cur;
// 将当前结点置空,表示已经处理完毕
cur = NULL;
} else {
// 右子树未被访问过,将右子树压栈
cur->flag = true;
s.push(cur->right);
cur = cur->right->left;
}
}
}
int main() {
// 构造二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
// 后序遍历
postorderTraversal(root);
cout << endl;
return 0;
}
```
注意到我们在二叉树结点的定义中增加了一个`flag`标志,表示该结点是否被访问过。当我们访问一个结点时,将该结点的`flag`标志设为`true`,表示该结点已被访问过。二叉树后序遍历的非递归算法需要访问每个结点两次,所以在每次进栈和出栈时,都要将该结点的`flag`标志同时进栈和出栈。
阅读全文