Untitled
unknown
plain_text
3 years ago
2.9 kB
1
Indexable
#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); } } }
Editor is loading...