后序遍历的非递归算法c语言栈实现
时间: 2023-09-02 20:15:40 浏览: 61
后序遍历的非递归算法可以使用栈来实现。具体步骤如下:
1. 初始化一个空栈,将根节点压入栈中。
2. 取出栈顶元素,如果该元素没有左右子节点,则输出该元素的值,如果有,则按照右节点、左节点的顺序依次将其子节点压入栈中。
3. 重复第2步,直到栈为空。
下面是C语言代码实现:
```c
void postOrderTraversal(TreeNode* root) {
if (root == NULL) return;
Stack stack;
TreeNode* prev = NULL;
push(&stack, root);
while (!isEmpty(&stack)) {
TreeNode* curr = peek(&stack);
if (prev == NULL || prev->left == curr || prev->right == curr) {
// 如果当前节点是根节点或者上一次访问的节点是它的子节点,则将其子节点(如果有)压入栈中
if (curr->left != NULL) push(&stack, curr->left);
else if (curr->right != NULL) push(&stack, curr->right);
} else if (curr->left == prev) {
// 如果当前节点的左子节点是上一次访问的节点,则将其右子节点(如果有)压入栈中
if (curr->right != NULL) push(&stack, curr->right);
} else {
// 否则,输出当前节点的值并弹出栈顶元素
printf("%d ", curr->val);
pop(&stack);
}
prev = curr;
}
}
```
其中,`TreeNode` 表示二叉树节点的结构体,`Stack` 表示栈的结构体,`push`、`pop`、`isEmpty` 和 `peek` 分别表示入栈、出栈、判断栈是否为空和获取栈顶元素的函数。在实现时需要注意,因为要输出每个节点的值,所以需要保存上一次访问的节点,用于判断当前节点是其父节点的左子节点还是右子节点。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)