后序遍历的非递归C语言代码
时间: 2023-11-29 07:39:13 浏览: 34
后序遍历的非递归 C 语言代码可以使用栈来实现。以下是一个示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
struct Stack {
struct TreeNode* data[MAX_SIZE];
int top;
};
void push(struct Stack* stack, struct TreeNode* node) {
if (stack->top == MAX_SIZE - 1) {
printf("Stack overflow\n");
return;
}
stack->top++;
stack->data[stack->top] = node;
}
struct TreeNode* pop(struct Stack* stack) {
if (stack->top == -1) {
printf("Stack underflow\n");
return NULL;
}
struct TreeNode* node = stack->data[stack->top];
stack->top--;
return node;
}
void postorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
struct Stack* stack1 = (struct Stack*)malloc(sizeof(struct Stack));
struct Stack* stack2 = (struct Stack*)malloc(sizeof(struct Stack));
stack1->top = -1;
stack2->top = -1;
push(stack1, root);
while (stack1->top != -1) {
struct TreeNode* node = pop(stack1);
push(stack2, node);
if (node->left) {
push(stack1, node->left);
}
if (node->right) {
push(stack1, node->right);
}
}
while (stack2->top != -1) {
struct TreeNode* node = pop(stack2);
printf("%d ", node->val);
}
free(stack1);
free(stack2);
}
int main() {
// 构造示例二叉树
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = 1;
struct TreeNode* node1 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node1->val = 2;
struct TreeNode* node2 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node2->val = 3;
root->left = node1;
root->right = node2;
node1->left = NULL;
node1->right = NULL;
node2->left = NULL;
node2->right = NULL;
printf("Postorder traversal: ");
postorderTraversal(root);
free(root);
free(node1);
free(node2);
return 0;
}
```