非递归形式的二叉树后序遍历该怎么写
时间: 2023-11-03 21:04:27 浏览: 34
非递归形式的二叉树后序遍历可以使用栈来实现,具体实现步骤如下:
1. 定义一个栈和一个指针p,将根节点压入栈中,然后将根节点的右子节点和左子节点依次压入栈中。
2. 当栈不为空时,弹出栈顶元素,判断该节点是否有左右子节点,如果没有则输出该节点的值,否则将该节点重新压入栈中,并将其右子节点和左子节点依次压入栈中。
3. 重复步骤2,直到栈为空。
代码实现如下:
```
void postOrderTraversal(TreeNode *root) {
if (root == NULL) return;
stack<TreeNode*> st;
TreeNode *p = root;
while (!st.empty() || p) {
if (p) {
st.push(p);
p = p->right;
if (p) st.push(p);
p = p->left;
} else {
p = st.top();
st.pop();
if (p->left == NULL && p->right == NULL) {
cout << p->val << " ";
} else {
st.push(p);
}
p = NULL;
}
}
}
```
其中,TreeNode是二叉树节点的结构体,包含val、left和right三个成员变量。在该函数中,先判断根节点是否为空,如果为空则直接返回。然后定义一个栈和一个指针p,将根节点压入栈中,然后进入循环,只要栈不为空或者指针p不为空,就执行循环体中的代码。
在循环体中,首先判断指针p是否为空,如果不为空,则将其右子节点和左子节点依次压入栈中,然后将指针p移动到左子节点上。
如果指针p为空,则弹出栈顶元素,判断该节点是否为叶子节点,如果是,则输出该节点的值,否则将该节点重新压入栈中,并将指针p置为空。
最后,当循环结束时,就完成了二叉树的后序遍历。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)