根据后序和中序遍历输出先序遍历

根据后序和中序遍历输出先序遍历

后序遍历+中序遍历---->>>>先序遍历 输入

7 2 3 1 5 7 6 4 1 2 3 4 5 6 7

输出

Preorder: 4 1 3 2 6 5 7

思路：*找规律， 由后序为主体，每一个入树的都是后序的，从后序结果最后一个开始入树，一个一个往前。 找到一个后序的就去中序结果中找这一个后序数字所在位置，分出左右，再入树，继续找… 代码如下

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

typedef int ElementType;
typedef struct TNode* BinTree;
struct TNode
{
          
   
    ElementType Data;
    BinTree Left;
    BinTree Right;
};
BinTree CreatBintree(int n,int Late[],int Mid[])
{
          
   

    if(n<=0)
        return 0;
    else
    {
          
   
        BinTree Root=(BinTree)malloc(sizeof(struct TNode));
        Root->Data=Late[n-1];
        Root->Left=NULL;
        Root->Right=NULL;
        int i;
        for( i=0;i<n;i++)
        {
          
   
            if(Mid[i]==Late[n-1])
            break;
        }
        Root->Left=CreatBintree(i,Late,Mid);
        Root->Right=CreatBintree(n-i-1,Late+i,Mid+i+1);
        return Root;
    }

}
void PreorderTraversal(BinTree BT)
{
          
   
    if(BT==NULL)
        return;
    else
    {
          
   
        printf(" %d",BT->Data);
        PreorderTraversal(BT->Left);
        PreorderTraversal(BT->Right);
        return ;
    }
}
int main()
{
          
   
    int n;
    scanf("%d",&n);
    int Late[n],Mid[n];
    for(int i=0;i<n;i++)
    {
          
   
        scanf("%d",&Late[i]);
    }
    for(int i=0;i<n;i++)
    {
          
   
        scanf("%d",&Mid[i]);
    }
    BinTree BT;
    BT=CreatBintree(n, Late, Mid);
    printf("Preorder:");
    PreorderTraversal(BT);
}

今天又做了一道差不多的题，又想了想，不需要建树，想太多落入下乘了，题目只需要输出，去掉与树有关的 注意：我将int型换成char型了 代码：

#include <stdio.h>
#include <stdlib.h>
int n;
void CreatTree(int n,char after[],char mid[])
{
          
   
    if(n<0)
        return ;
    else
    {
          
   
        printf("%c",after[n]);
        int i;
        for(i=0;i<=n;i++)
        {
          
   
            if(mid[i]==after[n])
                break;
        }
        CreatTree(i-1,after,mid);
        CreatTree(n-i-1,after+i,mid+i+1);
        return ;
    }
}
int main()
{
          
   
    char after[1000];
    char mid[1000];
    scanf("%d",&n);
    scanf("%s",after);
    scanf("%s",mid);
    CreatTree(n-1,after,mid);
    return 0;
}