用c语言实现并写出以下代码:请编写非递归程序,实现二叉树的后序遍历。
时间: 2024-05-11 21:16:08 浏览: 21
以下是用C语言实现二叉树后序遍历的非递归程序:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
typedef struct StackNode {
TreeNode *node;
struct StackNode *next;
} StackNode;
StackNode *createStackNode(TreeNode *node) {
StackNode *stackNode = malloc(sizeof(StackNode));
stackNode->node = node;
stackNode->next = NULL;
return stackNode;
}
void push(StackNode **stack, TreeNode *node) {
StackNode *stackNode = createStackNode(node);
stackNode->next = *stack;
*stack = stackNode;
}
TreeNode *pop(StackNode **stack) {
TreeNode *node = (*stack)->node;
*stack = (*stack)->next;
return node;
}
TreeNode **postorderTraversal(TreeNode *root, int *returnSize) {
int size = 0;
TreeNode **result = malloc(sizeof(TreeNode *) * 1000);
StackNode *stack = NULL;
TreeNode *prev = NULL;
while (root || stack) {
if (root) {
push(&stack, root);
root = root->left;
} else {
root = pop(&stack);
if (root->right && root->right != prev) {
push(&stack, root);
root = root->right;
} else {
result[size++] = root;
prev = root;
root = NULL;
}
}
}
*returnSize = size;
return result;
}
int main() {
// 构造二叉树
TreeNode *root = malloc(sizeof(TreeNode));
root->val = 1;
root->left = malloc(sizeof(TreeNode));
root->right = malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right->val = 3;
root->right->left = malloc(sizeof(TreeNode));
root->right->right = NULL;
root->right->left->val = 4;
root->right->left->left = NULL;
root->right->left->right = NULL;
int size;
TreeNode **result = postorderTraversal(root, &size);
for (int i = 0; i < size; i++) {
printf("%d ", result[i]->val);
}
printf("\n");
return 0;
}
```
输出结果为:
```
2 4 3 1
```
即二叉树的后序遍历结果。