编写二叉树的后序遍历的非递归算法。
时间: 2024-05-13 20:19:08 浏览: 69
二叉树的后序遍历可以使用非递归算法来实现,具体步骤如下:
1. 定义一个栈和一个指针p,初始时p指向根节点,将p入栈。
2. 当栈不为空时,取出栈顶元素,如果该元素没有左右子节点或者左右子节点都已经被访问过了,则输出该节点的值,并将p指向栈顶元素。
3. 如果栈顶元素有左右子节点且左右子节点中至少有一个没有被访问过,则将p指向左子节点或右子节点,并将该子节点入栈。
下面是具体的代码实现:
```c++
void postorderTraversal(TreeNode* root) {
if (!root) return;
stack<TreeNode*> s;
TreeNode *p = root, *lastVisited = nullptr;
while (p || !s.empty()) {
while (p) {
s.push(p);
p = p->left;
}
p = s.top();
if (!p->right || p->right == lastVisited) {
cout << p->val << " ";
s.pop();
lastVisited = p;
p = nullptr;
} else {
p = p->right;
}
}
}
```
其中,lastVisited用于记录上一次访问的节点,如果当前节点的右子节点已经被访问过了,那么说明该节点的左右子节点都已经被访问过了,可以输出该节点的值并将其弹出栈。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)