C语言生成中序遍历二叉树代码

在C语言中，我们可以使用递归的方式来生成一个完全二叉树并对其进行遍历。这里我将提供一个简单的例子，首先我们需要创建一个结构体表示二叉树节点： ```c #include <stdio.h> typedef struct TreeNode { int val; // 节点值 struct TreeNode* left; // 左子节点指针 struct TreeNode* right; // 右子节点指针 } TreeNode; ``` 生成完全二叉树的函数可以这样实现： ```c TreeNode* createCompleteTree(int n) { if (n <= 0) return NULL; TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); root->val = 1; // 根节点通常是第一个元素 int i = 2, level = 2; while (i <= n) { if (level % 2 == 1) { // 非空层，从左到右插入 while (root->left != NULL && i > 0) { root = root->left; i--; } root->right = (TreeNode*)malloc(sizeof(TreeNode)); root->right->val = i++; } else { // 空层，从右到左插入 while (root->right != NULL && i > 0) { root = root->right; i--; } root->left = (TreeNode*)malloc(sizeof(TreeNode)); root->left->val = i++; } level++; } return root; } ``` 接下来，我们编写三个遍历函数： 1. 前序遍历（根-左-右）： ```c void preOrderTraversal(TreeNode* root) { if (root != NULL) { printf("%d ", root->val); preOrderTraversal(root->left); preOrderTraversal(root->right); } } ``` 2. 中序遍历（左-根-右）： ```c void inOrderTraversal(TreeNode* root) { if (root != NULL) { inOrderTraversal(root->left); printf("%d ", root->val); inOrderTraversal(root->right); } } ``` 3. 后序遍历（左-右-根）： ```c void postOrderTraversal(TreeNode* root) { if (root != NULL) { postOrderTraversal(root->left); postOrderTraversal(root->right); printf("%d ", root->val); } } ``` 最后，你可以这样使用这些函数： ```c int main() { int n = 5; // 指定完全二叉树的节点数 TreeNode* tree = createCompleteTree(n); printf("Preorder traversal: "); preOrderTraversal(tree); // 输出前序遍历结果 printf("\nInorder traversal: "); inOrderTraversal(tree); // 输出中序遍历结果 printf("\nPostorder traversal: "); postOrderTraversal(tree); // 输出后序遍历结果 freeRecursive(tree); // 自定义的释放内存函数 return 0; } // 自定义释放内存的辅助函数 void freeRecursive(TreeNode* node) { if (node == NULL) return; freeRecursive(node->left); freeRecursive(node->right); free(node); } ```

在C语言中，我们可以使用递归的方式来构建和遍历完全二叉树。首先，我们创建一个结构体来表示二叉树节点： ```c typedef struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right; } TreeNode; ``` 下面是一个函数来创建一个空的二叉树节点： ```c TreeNode* createNode(int val) { TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); if (node != NULL) { node->val = val; node->left = NULL; node->right = NULL; } return node; } ``` 接着，我们创建一个函数来生成完全二叉树并进行遍历。这里以前序遍历为例： ```c void preOrderTraversal(TreeNode* root, void (*visit)(int)) { if (root != NULL) { visit(root->val); preOrderTraversal(root->left, visit); preOrderTraversal(root->right, visit); } } // 对于中序遍历和后序遍历，只需将访问函数的顺序调整即可 void inOrderTraversal(TreeNode* root, void (*visit)(int)) { if (root != NULL) { inOrderTraversal(root->left, visit); visit(root->val); inOrderTraversal(root->right, visit); } } void postOrderTraversal(TreeNode* root, void (*visit)(int)) { if (root != NULL) { postOrderTraversal(root->left, visit); postOrderTraversal(root->right, visit); visit(root->val); } } ``` 为了打印节点信息，你可以自定义一个`visit`函数，例如： ```c void printValue(int val) { printf("%d ", val); } int main() { // 创建一个完全二叉树示例 TreeNode* root = createNode(1); // ... (根据需要添加更多节点) // 遍历并打印节点值 preOrderTraversal(root, printValue); printf("\n"); inOrderTraversal(root, printValue); printf("\n"); postOrderTraversal(root, printValue); printf("\n"); return 0; } ```