Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.9 kB
0
Indexable
Never
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _Node{
    int number;
    struct _Node *left,*right,*prev;
}Node;

int in[3005];
int order[3005];
char X[3005];
char Y[3005];

int n,xs,ys,test;

void inorder1(Node* root);
void inorder2(int N);
void find(int m,int w,Node* cur);


int main(void){
    int N,M,x,y,m,l,r;
    Node* root;
    
    scanf("%d",&N);
    root=(Node*)malloc(sizeof(Node)*(N+1));
    root[1].number=1;
    root[1].prev=NULL;
    for(int i=2;i<=N;i++){
        root[i].number=i;
    }
    for(int i=1;i<=N;i++){
        printf("%d: ",i);
        scanf("%d %d",&l,&r);
        if(l==0){
            root[i].left=NULL;
        }
        else{
            root[l].prev=&root[i];
            root[i].left=&root[l];
        }
        if(r==0){
            root[i].right=NULL;
        }
        else{
            root[r].prev=&root[i];
            root[i].right=&root[r];
        }
        if(i==N) printf("==N\n");
    }
    printf("yyyyyyyyy\n");

    inorder1(root);
    for(int i=1;i<=N;i++) printf("in[%d]:%d",i,in[i]);
    printf("\n");
    inorder2(N);
    for(int i=1;i<=N;i++) printf("order[%d]:%d",i,order[i]);
    printf("\n");

    scanf("%d",&M);
    for(int i=0;i<M;i++){
        xs=0;
        ys=0;
        scanf("%d %d",&x,&y);
        find(x,1,root);
        find(y,0,root);
        for(int j=1;j<=xs && j<=ys;j++){
            if(X[j]==Y[j]){
                X[j]='\0';
                Y[j]='\0';
            }
            else break;
        }
        for(int j=1;j<=xs;j++){
            if(X[j]!='\0'){
                printf("P");
                X[j]='\0';
            }
        }
        for(int j=1;j<=ys;j++){
            if(X[j]!='\0'){
                printf("%c",Y[j]);
                Y[j]='\0';
            }
        }
        printf("\n");
    }

    return 0;
}

void inorder1(Node* root){
    Node* cur=root;
    //if(n==0) printf("in the order1\n");

    if(root!=NULL){
    inorder1(root->left);
    n++;
    printf("%d:%d\n",n,root->number);
    in[n]=root->number;
    inorder1(root->right);
    }

    return;
}
void inorder2(int N){

    for(int i=1;i<=N;i++){
        order[in[i]]=i;
    }
}

void find(int m,int w,Node* cur){
    if(cur==NULL) return;

    if(w==1){
        if(order[m]>order[cur->number]){
            X[xs]='R';
            find(m,1,cur->right);
        }
        else if(order[m]<order[cur->number]){
            X[xs]='L';
            find(m,1,cur->left);
        }
    }
    else{
        if(order[m]>order[cur->number]){
            Y[ys]='R';
            find(m,0,cur->right);
        }
        else if(order[m]<order[cur->number]){
            Y[ys]='L';
            find(m,0,cur->left);
        }
    }
}