C语言实现:中序遍历二叉树的非递归算法
时间: 2023-12-01 13:05:46 浏览: 32
中序遍历二叉树的非递归算法可以使用栈来实现。具体步骤如下:
1. 初始化当前节点为根节点,将其压入栈中。
2. 如果当前节点不为空,则将其左子树中的所有节点依次入栈,直到当前节点为空。
3. 弹出栈顶节点,进行访问。
4. 将当前节点指向弹出节点的右子树。
5. 重复步骤2-4,直到栈为空且当前节点为空。
以下是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 定义栈
typedef struct Stack {
TreeNode **data; // 存储节点指针的数组
int top; // 栈顶指针
int capacity; // 栈容量
} Stack;
// 初始化栈
Stack* initStack(int capacity) {
Stack *stack = (Stack*)malloc(sizeof(Stack));
stack->data = (TreeNode**)malloc(capacity * sizeof(TreeNode*));
stack->top = -1;
stack->capacity = capacity;
return stack;
}
// 判断栈是否为空
int isEmpty(Stack *stack) {
return stack->top == -1;
}
// 判断栈是否已满
int isFull(Stack *stack) {
return stack->top == stack->capacity - 1;
}
// 入栈
void push(Stack *stack, TreeNode *node) {
if (isFull(stack)) {
printf("Stack is full.\n");
return;
}
stack->top++;
stack->data[stack->top] = node;
}
// 出栈
TreeNode* pop(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty.\n");
return NULL;
}
TreeNode *node = stack->data[stack->top];
stack->top--;
return node;
}
// 中序遍历二叉树的非递归算法
void inorderTraversal(TreeNode *root) {
if (!root) return;
Stack *stack = initStack(100); // 栈容量为100
TreeNode *curr = root;
while (!isEmpty(stack) || curr) {
// 将当前节点的所有左子节点入栈
while (curr) {
push(stack, curr);
curr = curr->left;
}
// 弹出栈顶节点并访问
curr = pop(stack);
printf("%d ", curr->val);
// 移动到右子节点
curr = curr->right;
}
free(stack->data);
free(stack);
}
int main() {
// 构造二叉树
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
root->right->left->val = 4;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->val = 5;
root->right->right->left = NULL;
root->right->right->right = NULL;
// 中序遍历二叉树
inorderTraversal(root);
// 释放内存
free(root->left);
free(root->right->left);
free(root->right->right);
free(root->right);
free(root);
return 0;
}
```