藍橋杯（C語言題目）題目 1648: [藍橋杯][算法訓練VIP]求先序排列

題目 1648: [藍橋杯][算法訓練VIP]求先序排列

時間限制: 1Sec 記憶體限制: 128MB

題目描述

給出一棵二叉樹的中序與後序排列。求出它的先序排列。（約定樹結點用不同的大寫字母表示，長度< =8）。

輸入

兩行，每行一個字元串，分别表示中序和後序排列

輸出

一個字元串，表示所求先序排列

樣例輸入

BADC 
BDCA 
           

樣例輸出

ABCD
           

C代碼

#include<stdio.h>
#include<string.h>
#define Max(x,y) x>y?x:y 
char s[100],s1[100];
void Pd(char *x,char *x1)
{
    int i,j,k,l,p;
    char c;
    char x3[100],x4[100];//X3:x的左  X4:x的右 
    char x6[100],x7[100];//X6:x1的左  X7:x1的右 
    int t=strlen(x1)-1;
    c=x1[t];//輸出後序序列的最後一位 (根節點)
    printf("%c",c);
    p=strlen(x);
    for(i=0;x[i];i++)
    {    
        if(c==x[i])
        {
            break;
        } 
        x3[i]=x[i];//把X的前i個放入左節點的中序 X1的前i個放入右節點的中序 
        x6[i]=x1[i];
    }
    x3[i]='\0';//别忘了 
    x6[i]='\0';
    k=0;
    for(l=i+1;l<p;l++)//把X i後邊(i是根節點)的數放入x4 
    {
        x4[k++]=x[l];
    } 
    x4[k]='\0';
    k=0;
    for(l=i;l<p-1;l++)//把X1 的i---（最後-1）放入x7中(因為最後是根節點) 
    {
        x7[k++]=x1[l];
    }
    x7[k]='\0';
    if(x3[0])
        Pd(x3,x6);
    if(x4[0])
        Pd(x4,x7);
}
int main()
{
    int i,j;
    scanf("%s",s);
    scanf("%s",s1);
    Pd(s,s1);
    return 0;
}
           

通過C語言網編譯運作