中序遍历和后序遍历的C语言实现是什么样的？

中序遍历和后序遍历通常用于二叉树的数据结构中，下面是它们在C语言中的实现示例[^1]：

**中序遍历**

void inorderTraversal(TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data); // 先访问左子树，然后访问根节点
        inorderTraversal(root->right);
    }
}

在这个函数中，我们首先递归地遍历左子树，接着访问当前节点，最后遍历右子树。

**后序遍历**

void postorderTraversal(TreeNode* root) {
    if (root != NULL) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        printf("%d ", root->data); // 先访问左右子树，最后访问根节点
    }
}

后序遍历的顺序是先左子树，再右子树，最后根节点。

为了从这两个遍历得到先序遍历，我们需要知道一个事实：先序遍历的顺序是根节点 -> 左子树 -> 右子树。所以，当你找到最后一个元素（即后序遍历的右子树的最右边节点）时，它的父节点就是前一个节点（因为后序是左->右->根），而这个父节点就是先序遍历中的下一个节点。

具体到`preOrder(last, in, i)`函数，这里的`last`代表后序遍历的栈顶元素，`in`是中序遍历数组，`i`是当前处理的中序遍历索引。当`i`等于后序遍历数组的长度时，意味着已经找到了右子树的最右边，因此`last`就是根节点，应该添加到先序序列中，此时传递的`i`实际上应该是`i-1`（因为它指向的是上一个中序元素），这样可以找到正确的父节点并继续向前。