C语言中序遍历详解（手把手教你实现二叉树中序遍历算法）

为什么叫“中序”？

因为“根节点”被访问的顺序在“中间”——先访问左子树，再访问根，最后访问右子树。这与前序（根-左-右）和后序（左-右-根）形成对比。

C语言实现中序遍历

下面我们用C语言一步步实现中序遍历算法教程中最经典的递归方法。

第1步：定义二叉树节点结构

#include <stdio.h>#include <stdlib.h>// 定义二叉树节点结构typedef struct TreeNode {    int data;    struct TreeNode* left;    struct TreeNode* right;} TreeNode;

第2步：编写中序遍历函数（递归版）

// 中序遍历函数void inorderTraversal(TreeNode* root) {    if (root == NULL) {        return; // 递归终止条件    }        inorderTraversal(root->left);   // 1. 遍历左子树    printf("%d ", root->data);      // 2. 访问根节点    inorderTraversal(root->right);  // 3. 遍历右子树}

第3步：创建测试二叉树并调用遍历

// 辅助函数：创建新节点TreeNode* createNode(int value) {    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));    newNode->data = value;    newNode->left = NULL;    newNode->right = NULL;    return newNode;}// 主函数int main() {    // 构建如下二叉树：    //       4    //      / \    //     2   6    //    / \ / \    //   1  3 5  7    TreeNode* root = createNode(4);    root->left = createNode(2);    root->right = createNode(6);    root->left->left = createNode(1);    root->left->right = createNode(3);    root->right->left = createNode(5);    root->right->right = createNode(7);    printf("中序遍历结果: ");    inorderTraversal(root);    printf("\n");    return 0;}

运行结果

当你编译并运行上述代码，输出将是：

中序遍历结果: 1 2 3 4 5 6 7

进阶：非递归实现（使用栈）

虽然递归写法简洁，但在某些场景下（如树很深时）可能导致栈溢出。我们可以用显式栈来实现非递归版本：

#include <stdio.h>#include <stdlib.h>#define MAX_SIZE 100typedef struct Stack {    TreeNode* items[MAX_SIZE];    int top;} Stack;void push(Stack* s, TreeNode* node) {    s->items[++(s->top)] = node;}TreeNode* pop(Stack* s) {    return s->items[(s->top)--];}int isEmpty(Stack* s) {    return s->top == -1;}void inorderIterative(TreeNode* root) {    Stack s;    s.top = -1;    TreeNode* current = root;    while (current != NULL || !isEmpty(&s)) {        // 一直向左走到底        while (current != NULL) {            push(&s, current);            current = current->left;        }        // 弹出栈顶并访问        current = pop(&s);        printf("%d ", current->data);        // 转向右子树        current = current->right;    }}

总结

通过本教程，你已经掌握了C语言中序遍历的基本原理和两种实现方式（递归与非递归）。记住，中序遍历的关键在于“左→根→右”的访问顺序。这对于理解二叉搜索树、表达式求值等高级应用非常有帮助。

建议你动手敲一遍代码，修改树的结构，观察输出变化，加深理解。掌握C语言二叉树遍历是迈向更复杂算法的重要一步！