用c语言二叉树中序遍历非递归
时间: 2024-01-23 09:13:30 浏览: 29
以下是用C语言实现二叉树中序遍历的非递归方法:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct Stack {
struct TreeNode **data;
int top;
int size;
};
void initStack(struct Stack *s, int size) {
s->data = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * size);
s->top = -1;
s->size = size;
}
void push(struct Stack *s, struct TreeNode *node) {
if (s->top == s->size - 1) {
return;
}
s->top++;
s->data[s->top] = node;
}
struct TreeNode *pop(struct Stack *s) {
if (s->top == -1) {
return NULL;
}
struct TreeNode *node = s->data[s->top];
s->top--;
return node;
}
int isEmpty(struct Stack *s) {
return s->top == -1;
}
int *inorderTraversal(struct TreeNode *root, int *returnSize) {
if (root == NULL) {
*returnSize = 0;
return NULL;
}
int *result = (int *)malloc(sizeof(int) * 100);
struct Stack s;
initStack(&s, 100);
struct TreeNode *p = root;
int i = 0;
while (p != NULL || !isEmpty(&s)) {
while (p != NULL) {
push(&s, p);
p = p->left;
}
if (!isEmpty(&s)) {
p = pop(&s);
result[i++] = p->val;
p = p->right;
}
}
*returnSize = i;
return result;
}
```