在C语言中,可以通过递归或迭代的方式来实现二叉树的中序遍历。这里给出两种方法的代码示例:
方法一:递归
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 中序遍历的递归函数
void inorderTraversal(struct TreeNode* node) {
if (node == NULL) {
return;
}
inorderTraversal(node->left); // 遍历左子树
printf("%d ", node->val); // 访问根节点
inorderTraversal(node->right); // 遍历右子树
}
// 创建新节点的辅助函数
struct TreeNode* newNode(int val) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
int main() {
// 创建示例二叉树
struct TreeNode* root = newNode(1);
root->right = newNode(2);
root->right->left = newNode(3);
// 执行中序遍历
inorderTraversal(root);
return 0;
}
方法二:迭代(使用栈)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 定义二叉树节点结构体
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 中序遍历的迭代函数
void inorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
struct TreeNode* currentNode = root;
while (currentNode != NULL || !isEmpty(stack)) {
// 遍历左子树,将节点压入栈中
while (currentNode != NULL) {
stackPush(stack, currentNode);
currentNode = currentNode->left;
}
// 弹出栈顶元素,访问节点,并转向右子树
currentNode = stackPop(stack);
printf("%d ", currentNode->val);
currentNode = currentNode->right;
}
free(stack);
}
// 栈结构体定义及操作函数
struct Stack {
struct TreeNode** data;
int top;
int capacity;
};
void initStack(struct Stack* stack, int capacity) {
stack->data = (struct TreeNode**)malloc(capacity * sizeof(struct TreeNode*));
stack->top = -1;
stack->capacity = capacity;
}
bool isEmpty(struct Stack* stack) {
return stack->top == -1;
}
void stackPush(struct Stack* stack, struct TreeNode* node) {
if (stackIsFull(stack)) {
printf("Stack overflow\n");
return;
}
stack->data[++stack->top] = node;
}
struct TreeNode* stackPop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack underflow\n");
return NULL;
}
return stack->data[stack->top--];
}
bool stackIsFull(struct Stack* stack) {
return stack->top == stack->capacity - 1;
}
int main() {
// 创建示例二叉树
struct TreeNode* root = newNode(1);
root->right = newNode(2);
root->right->left = newNode(3);
// 执行中序遍历
inorderTraversal(root);
return 0;
}
这两种方法都可以实现二叉树的中序遍历。递归方法更简洁直观,但可能受到栈空间限制;迭代方法使用显式栈来避免栈溢出的问题,但代码相对复杂。