YTU 3025: 두 갈래 나무 만들기

2561 단어

원문 링크:https://www.dreamwings.cn/ytu3025/2628.html



3025: 두 갈래 나무 만들기


시간 제한:
1 Sec  
메모리 제한:
128 MB
제출:
3  
해결:

제목 설명


이미 알고 있는 두 갈래 나무의 중순 서열은 cbedahgijf이고, 후순 서열은cedbhjigfa이며, 두 갈래 나무의 수형 표시(괄호법)를 제시한다.

입력


출력


괄호와 알파벳이 있는 괄호법으로 표시된 두 갈래 트리를 출력합니다.

힌트


우선 중서 서열과 후서 서열에 따라 두 갈래 나무를 그린 다음 괄호법으로 표시한다.
중차 서열과 후차 서열을 이용하여 두 갈래 트리를 구성한 다음에 괄호 표현법으로 출력합니다!
AC 코드:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Node
{
    char data;
    Node *lc;
    Node *rc;
} Node;
Node *CreateBT2(char *post,char *in,int n)
{
    Node *b;
    int r,k;
    char *p;
    if(n<=0)return NULL;
    r=*(post+n-1);                      // , 
    b=(Node*)malloc(sizeof(Node));
    b->data=r;                          // 
    for(p=in; p<in+n; p++)
        if(*p==r)break;
    k=p-in;                             // 
    b->lc=CreateBT2(post,in,k);
    b->rc=CreateBT2(post+k,p+1,n-k-1);
    return b;
}
void Print(Node *b)
{
    if(b!=NULL)
    {
        printf("%c",b->data);
        if(b->lc!=NULL||b->rc!=NULL)
        {
            printf("(");
            Print(b->lc);
            if(b->rc!=NULL)printf(",");
            Print(b->rc);
            printf(")");
        }
    }
}
int main()
{
    int len;
    Node *head;
    char post[30]="cedbhjigfa",in[30]="cbedahgijf";     //  
    head=(Node*)malloc(sizeof(Node));
    len=strlen(post);
    head=CreateBT2(post,in,len);                        // 
    Print(head);                                        // 
    return 0;
}

좋은 웹페이지 즐겨찾기