写一段C语言代码，要求已知前序序列和后序序列求中序序列

以下是一段递归实现的C语言代码，可以根据前序序列和后序序列求出中序序列：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
char pre[30],post[30];
 
void build(char* p,char* q,int n)
{
    if(n<=0)
        return;
    int i,l=0,r=0;
    for(i=0;i<n;i++)
    {
        if(q[i]==p[0])
            break;
        l++;
    }
    r=n-l-1;
    build(p+1,q,l);
    build(p+l+1,q+l,r);
    printf("%c",p[0]);
}
 
int main()
{
    scanf("%s%s",pre,post);
    int n=strlen(pre);
    build(pre,post,n);
    return 0;
}

注：本代码为CSDN博主“tongzou”所写，原链接：https://blog.csdn.net/tongzou/article/details/38894903

相关问题

写一段C语言代码，要求已知中序序列和后序序列求前序序列

以下是一段求解中序序列和后序序列求前序序列的C语言代码：

#include <stdio.h>
#include <stdlib.h>

int search(int arr[], int start, int end, int value) {
    int i;
    for (i = start; i <= end; i++) {
        if (arr[i] == value) {
            return i;
        }
    }
    return -1;
}

void printPreorder(int inorder[], int postorder[], int inStart, int inEnd, int *postIndex) {
    if (inStart > inEnd) {
        return;
    }

    int curr = postorder[*postIndex];
    (*postIndex)--;

    if (inStart == inEnd) {
        printf("%d ", curr);
        return;
    }

    int inIndex = search(inorder, inStart, inEnd, curr);
    printPreorder(inorder, postorder, inIndex + 1, inEnd, postIndex);
    printPreorder(inorder, postorder, inStart, inIndex - 1, postIndex);

    printf("%d ", curr);
}

void printPreorderWrapper(int inorder[], int postorder[], int n) {
    int postIndex = n - 1;
    printPreorder(inorder, postorder, 0, n - 1, &postIndex);
}

int main() {
    int inorder[] = {4, 2, 5, 1, 3};
    int postorder[] = {4, 5, 2, 3, 1};
    int n = sizeof(inorder) / sizeof(inorder[0]);

    printf("Preorder traversal of the constructed tree: ");
    printPreorderWrapper(inorder, postorder, n);

    return 0;
}

这段代码中，`printPreorder` 函数递归地构建前序序列。它首先从后序序列中取出当前的根节点，然后在中序序列中查找这个根节点的位置，将中序序列分成左子树和右子树两部分，再分别递归地构建左子树和右子树。每次递归都会先构建右子树，再构建左子树，最后输出当前节点的值，这就是前序遍历。`printPreorderWrapper` 函数是一个包装函数，用于初始化 `postIndex` 变量并调用 `printPreorder` 函数。

c语言二叉树已知前序中序求后序代码详解

二叉树的前序遍历是先访问根结点，然后访问左子树，最后访问右子树；中序遍历是先访问左子树，然后访问根结点，最后访问右子树。因此，如果已知二叉树的前序遍历和中序遍历，就可以构造出整个二叉树。

对于给定的前序遍历序列和中序遍历序列，我们可以通过递归的方式来构造出二叉树。具体地，我们可以按照以下步骤进行：

1. 前序遍历序列的第一个元素即为根结点，找到该结点在中序遍历序列中的位置，该位置左边的序列即为左子树的中序遍历序列，右边的序列即为右子树的中序遍历序列。

2. 根据左子树中序遍历序列的长度，可以得到前序遍历序列中左子树的前序遍历序列，右子树的前序遍历序列即为剩余部分。

3. 递归地对左子树和右子树分别进行上述步骤，得到左子树和右子树的结构。

4. 最后将根结点和左右子树连接起来，得到完整的二叉树。

根据上述思路，我们可以编写如下的递归代码来构造二叉树：

// 前序遍历序列 preorder，中序遍历序列 inorder，序列长度为 len
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    if (preorderSize == 0) { // 前序遍历序列为空，返回空指针
        return NULL;
    }

    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode)); // 创建根结点
    root->val = preorder[0];

    int i;
    for (i = 0; i < inorderSize; i++) { // 在中序遍历序列中找到根结点的位置 i
        if (inorder[i] == root->val) {
            break;
        }
    }

    int leftLen = i; // 左子树的中序遍历序列长度
    int rightLen = inorderSize - i - 1; // 右子树的中序遍历序列长度

    root->left = buildTree(preorder+1, leftLen, inorder, leftLen); // 递归构造左子树
    root->right = buildTree(preorder+1+leftLen, rightLen, inorder+leftLen+1, rightLen); // 递归构造右子树

    return root;
}

该代码的时间复杂度为 $O(n^2)$，其中 n 表示二叉树的结点数。因为在每一次递归中，都需要在中序遍历序列中查找根结点的位置，时间复杂度为 $O(n)$，因此总时间复杂度为 $O(n^2)$。

对于大规模的数据，我们可以使用哈希表来优化查找根结点位置的过程，将时间复杂度降为 $O(n)$。