C语言用栈实现二叉树的后序遍历
时间: 2024-08-14 20:09:58 浏览: 52
在C语言中,使用栈可以实现二叉树的后序遍历(Postorder Traversal)。后序遍历的顺序通常是左子树、右子树、根节点。下面是使用递归和栈的一种常见实现方法:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 后序遍历函数,利用栈辅助实现
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
// 使用两个栈:一个存放当前路径中的节点,另一个用于临时保存左子树的结点
stack<TreeNode*> s1, s2;
s1.push(root);
while (!s1.empty()) {
TreeNode* node = s1.top();
s1.pop();
// 先将左子节点压入栈,然后右子节点
if (node->left != NULL) s2.push(node->left);
if (node->right != NULL) s2.push(node->right);
// 当前节点已处理完,将其加入后序结果(此时s2栈顶就是当前结点)
printf("%d ", node->val);
// 如果右子节点已经访问过了,说明我们回到了左子树的位置,将左子节点弹出并再次检查
if (s2.top()->left == node) {
s2.pop(); // 弹出左子节点
if (s2.top() != NULL) s1.push(s2.top()); // 将下一个节点放回s1栈
}
}
}
// 示例:创建一个简单的二叉树,并调用后序遍历
int main() {
// 创建示例二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 3;
root->left->left = NULL;
root->left->right = NULL;
root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
root->right->left->val = 4;
root->right->right = NULL;
printf("后序遍历结果: ");
postorderTraversal(root);
return 0;
}
```
阅读全文