试着用C语言写一个二叉树后序遍历的非递归算法的核心代码。
时间: 2024-05-04 15:20:59 浏览: 104
二叉树后序遍历的非递归算法可以使用栈来实现,具体实现如下:
```c
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
TreeNode* stack[1000];
int top = -1;
TreeNode* last = NULL;
while (root != NULL || top != -1) {
if (root != NULL) {
stack[++top] = root;
root = root->left;
} else {
TreeNode* tmp = stack[top];
if (tmp->right != NULL && tmp->right != last) {
root = tmp->right;
} else {
printf("%d ", tmp->val);
last = tmp;
top--;
}
}
}
}
```
其中,使用一个栈来保存节点,top表示栈顶元素的下标,last表示上一个被访问的节点。首先将根节点入栈,然后依次将其左子节点入栈。当左子节点为空时,弹出栈顶元素,如果该元素的右子节点不为空且没有被访问过,则将其右子节点入栈。如果右子节点为空或者已经被访问过,则访问该节点并将其标记为已访问,继续弹出栈顶元素。最终,栈为空时遍历结束。
阅读全文
相关推荐















