C语言后序中序遍历构造树

### 构造二叉树的方法 为了实现基于后序遍历和中序遍历来构造二叉树的功能，在C语言中的具体方法如下所示： 定义一个结构体用于表示二叉树节点，该结构体应至少包含三个成员变量：存储数据的数据域、指向左孩子的指针以及指向右孩子的指针。 ```c typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; ``` 编写`buildTree`函数接收两个参数分别为inorder（中序序列）与postorder（后续序列），这两个都是整型数组形式传入。此函数内部调用了辅助性的递归函数`helper`来进行实际的构建工作[^1]。 #### 辅助函数 `helper` 辅助函数接受四个额外参数用来界定当前处理范围内的起始位置索引值，分别是`inStart`, `inEnd`代表本次操作对应的中序序列区间边界；而`postIndex`则是记录此时正在考察哪一个元素作为根节点的位置指标。每次迭代过程中都会创建新的TreeNode实例对象，并尝试将其左右子树也按照相同逻辑继续细分直到完成整个重建过程为止。 ```c TreeNode* helper(int* inorder, int inStart, int inEnd, int* postorder, int* postIndex) { if (inStart > inEnd || *postIndex < 0) return NULL; // 创建新节点 TreeNode* node = malloc(sizeof(TreeNode)); node->val = postorder[*postIndex]; (*postIndex)--; // 更新下一个要访问的后序下标 // 查找分割点 int index; for (index = inStart; index <= inEnd; ++index) if (inorder[index] == node->val) break; // 建立右子树 -> 左子树顺序很重要因为是从后往前取postOrder里的元素 node->right = helper(inorder, index + 1, inEnd, postorder, postIndex); node->left = helper(inorder, inStart, index - 1, postorder, postIndex); return node; } ``` 最后一步是在主程序里初始化必要的环境配置比如读取输入数据到相应的数组当中去，设置初始状态下的`postIndex`等于最后一个有效数值所在处即`n-1`(假设总共有n个节点)，接着就可以直接调用上述提到过的`helper()`方法得到最终想要的结果了[^4]。 ```c int main(){ int n; scanf("%d", &n); // 输入结点数量 int inorder[n], postorder[n]; for(int i=0;i<n;++i){ scanf("%d",&inorder[i]); // 中序遍历结果 } for(int j=0;j<n;++j){ scanf("%d",&postorder[j]); // 后序遍历结果 } int postIndex=n-1; TreeNode* root = helper(inorder, 0, n-1, postorder,&postIndex); // 可选部分：打印先序遍历验证正确性 printf("Pre-order traversal:\n"); preOrderTraversal(root); } void preOrderTraversal(struct TreeNode* tree){ if(tree != NULL){ printf("%d ",tree->val); preOrderTraversal(tree->left); preOrderTraversal(tree->right); } } ```