二叉树中序遍历c语言
时间: 2023-11-24 09:06:27 浏览: 53
以下是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;
}
// 判断栈是否为空
int isEmpty(struct Stack *s) {
return s->top == -1;
}
// 判断栈是否已满
int isFull(struct Stack *s) {
return s->top == s->size - 1;
}
// 入栈
void push(struct Stack *s, struct TreeNode *node) {
if (isFull(s)) {
return;
}
s->data[++s->top] = node;
}
// 出栈
struct TreeNode *pop(struct Stack *s) {
if (isEmpty(s)) {
return NULL;
}
return s->data[s->top--];
}
// 中序遍历
void inorderTraversal(struct TreeNode *root) {
if (root == NULL) {
return;
}
struct Stack s;
initStack(&s, 100);
struct TreeNode *p = root;
while (p != NULL || !isEmpty(&s)) {
while (p != NULL) {
push(&s, p);
p = p->left;
}
if (!isEmpty(&s)) {
p = pop(&s);
printf("%d ", p->val);
p = p->right;
}
}
}
// 创建二叉树
struct TreeNode *createTree() {
int val;
scanf("%d", &val);
if (val == -1) {
return NULL;
}
struct TreeNode *node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = createTree();
node->right = createTree();
return node;
}
int main() {
struct TreeNode *root = createTree();
inorderTraversal(root);
return 0;
}
```
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)