阅读量:0
在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; } 这两种方法都可以实现二叉树的中序遍历。递归方法更简洁直观，但可能受到栈空间限制；迭代方法使用显式栈来避免栈溢出的问题，但代码相对复杂。
