[教程]C语言入门必学：深入浅出掌握中序遍历

引言中序遍历是二叉树遍历中的一种基本方式，它按照“左子树 根节点 右子树”的顺序访问二叉树的每个节点。中序遍历在二叉搜索树中非常有用，因为它可以按照有序的方式访问所有节点。对于C语言初学者来说，理...

引言

中序遍历是二叉树遍历中的一种基本方式，它按照“左子树 - 根节点 - 右子树”的顺序访问二叉树的每个节点。中序遍历在二叉搜索树中非常有用，因为它可以按照有序的方式访问所有节点。对于C语言初学者来说，理解并实现中序遍历是学习二叉树操作的重要一步。

中序遍历的概念

在介绍中序遍历的代码实现之前，我们先来理解一下它的基本概念。假设我们有一个二叉树，其结构如下：

 1 / \ 2 3 / \ 4 5

按照中序遍历的顺序，我们应该首先访问左子树（4），然后访问根节点（1），最后访问右子树（5）。因此，中序遍历的结果是：4, 1, 5。

中序遍历的递归实现

递归是实现中序遍历的一种简单有效的方法。以下是一个使用递归实现中序遍历的C语言代码示例：

#include 
#include 
// 定义二叉树节点结构体
typedef struct TreeNode { int value; struct TreeNode *left; struct TreeNode *right;
} TreeNode;
// 创建新节点的函数
TreeNode* createNode(int value) { TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); newNode->value = value; newNode->left = NULL; newNode->right = NULL; return newNode;
}
// 递归实现中序遍历的函数
void inorderTraversal(TreeNode* root) { if (root != NULL) { inorderTraversal(root->left); // 遍历左子树 printf("%d ", root->value); // 访问根节点 inorderTraversal(root->right); // 遍历右子树 }
}
// 主函数
int main() { // 创建示例二叉树 TreeNode* root = createNode(1); root->left = createNode(2); root->right = createNode(3); root->left->left = createNode(4); root->left->right = createNode(5); // 执行中序遍历 printf("中序遍历结果："); inorderTraversal(root); printf("\n"); return 0;
}

在上面的代码中，我们首先定义了二叉树节点的结构体TreeNode，然后创建了几个辅助函数，如createNode用于创建新节点，inorderTraversal用于递归实现中序遍历。在main函数中，我们创建了一个示例二叉树，并调用了inorderTraversal函数来执行中序遍历。

中序遍历的非递归实现

除了递归方法，我们还可以使用栈来实现非递归的中序遍历。以下是一个使用栈实现中序遍历的C语言代码示例：

#include 
#include 
// 定义二叉树节点结构体
typedef struct TreeNode { int value; struct TreeNode *left; struct TreeNode *right;
} TreeNode;
// 创建新节点的函数
TreeNode* createNode(int value) { TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); newNode->value = value; newNode->left = NULL; newNode->right = NULL; return newNode;
}
// 使用栈实现中序遍历的函数
void inorderTraversalNonRecursive(TreeNode* root) { TreeNode* stack[100]; // 假设栈的最大容量为100 int top = -1; TreeNode* current = root; while (current != NULL || top != -1) { // 循环遍历左子树 while (current != NULL) { stack[++top] = current; current = current->left; } // 访问根节点 current = stack[top--]; printf("%d ", current->value); // 遍历右子树 current = current->right; }
}
// 主函数
int main() { // 创建示例二叉树 TreeNode* root = createNode(1); root->left = createNode(2); root->right = createNode(3); root->left->left = createNode(4); root->left->right = createNode(5); // 执行中序遍历 printf("中序遍历结果（非递归）："); inorderTraversalNonRecursive(root); printf("\n"); return 0;
}

在上面的代码中，我们使用了一个固定大小的栈stack来存储遍历过程中访问的节点。通过循环遍历左子树并将节点压入栈中，然后访问栈顶节点（即根节点），最后遍历右子树，我们可以实现非递归的中序遍历。

总结

中序遍历是二叉树遍历中的一种基本方式，它按照“左子树 - 根节点 - 右子树”的顺序访问二叉树的每个节点。本文介绍了两种实现中序遍历的方法：递归和非递归。通过学习这些方法，C语言初学者可以更好地理解和掌握二叉树的操作。