UVa 548 트리

제목: 중순과 후순 서열을 제시하고 뿌리에서 잎사귀 결점까지의 경로와 값이 가장 작은 잎사귀 결점을 구한다.값과 같으면 잎사귀 결점 값이 비교적 작은 것을 선택하십시오.
사고방식: 중순과 후순 서열로 돌아가며 두 갈래 나무를 구성한다.순서 저장은 분명히 안 된다. 체인 저장을 사용한다.모든 결점은 알파벳이 아니라 숫자를 입력하기 때문에, 여기는 정형 수조로 저장되며, 더 이상 문자열이 아니기 때문에 더욱 편리할 수 있다.build(n, a1, a2) 함수는 중차 서열 a1과 후차 서열 a2를 이용하여 n개의 결점이 있는 두 갈래 트리를 구성하여 뿌리 결점 지침을 되돌려줍니다.귀속은 두 갈래 나무를 구성한 후 깊이 우선 검색을 하면 된다. 여기서 실현된 시비귀속 형식은 창고를 사용한다.
주의: 여러 경로가 최소와 값을 가지고 있을 때 잎사귀 결점이 가장 작은 출력을 선택하십시오.
여러 가지 작은 오류가 있는데 마지막에 연결했는데 입력 부분에 아직도 오류가 있다는 것을 발견했다. 만약while 중등가를 cnt1++로 바꾸면 오류가 발생할 수 있기 때문에 브레이크를 판단하는 조건을 ==1로 바꿀 수 없다. 왜냐하면 하나의 결점만 있을 때도 1이기 때문이다.
또한 프로그램 카드가 입력을 기다리는 동안 RE 오류가 발생합니다.즉, main에서 while (1) 을 벗어나는 조건인 if (cnt1=0) 를 주석하면 RE 오류가 발생합니다.
또한 테스트한 결과 파일 끝까지 읽을 때 계속 읽을 수 있고 EOF로 돌아갈 수 있습니다.즉if(cnt1=0) 주석을 지우고if(!cnt1&!cnt2)로 바꾸면 여전히 AC입니다. 첫 번째while 순환이 EOF로 읽을 때 두 번째while 순환이 읽히는 것은 문제없지만 여전히 EOF입니다.(이것은 완전히 RE를 시작했지만 아직 오류를 찾아내지 못했을 때 많은 생각을 했습니다~~) 이것은 EOF가 실제로 존재하는 문자가 아니라 표기 위치이기 때문인 것 같습니다.
또한 초기의 최소치leastv는 충분히 크게 설정하고 MAXN으로 설정하기 시작하면 WA~~친측...
RE 처음 시작할 때 remove가 없더라고요.tree, 메모리 유출로 인한 줄 알았어.방금 또 직접 측정해서remove_tree는 주석을 달았는데 이 문제는 뜻밖에도 없다.
preorder 선순,inorder 중순,postorder 후순.
Code:

#include
#include
#define MAXN 10010

typedef struct node
{
 int data;
 bool lvisit;
 bool rvisit;
 struct node *left,*right;       
}Node;

int dfs(Node *u);
Node* build(int n,int *a1, int *a2);
int find(int t,int *a,int len);
Node* newNode();
void remove_tree(Node *u);

int main()
{
 int a1[MAXN],a2[MAXN];
 while(1)
 {
  int cnt1=0,cnt2=0;
  while((scanf("%d",&a1[cnt1]))==1)
  {
   cnt1++; 
   char c=getchar();
   if(c=='
') break;            
  }   
  //if(cnt1==0) break; 
  while((scanf("%d",&a2[cnt2]))==1)
  {
   cnt2++;
   char c=getchar();
   if(c=='
'||c==EOF) break;                         
  }
  if(!cnt1&&!cnt2) break;
  Node *root=build(cnt1,a1,a2);       
  printf("%d
",dfs(root));
  remove_tree(root);
 }//while
 return 0;
}

int dfs(Node *u)
{
 Node *stack[MAXN]; int top=0;
 stack[++top]=u;
 int count=u->data; int leaf=0; int leastv=1000000000;
 while(top)
 {
  Node *t=stack[top];
  if(t->left==NULL && t->right==NULL)
  {// ，  
   if(countdata;}
   else if(count==leastv && t->datadata;
   count=count-t->data;
   top--;               
  }
  else if(!t->lvisit && t->left!=NULL)
  {// ，  
   stack[++top]=t->left; 
   t->lvisit=1;      
   count=count+stack[top]->data;                
  }         
  else if(!t->rvisit && t->right!=NULL)
  {// ，  
   stack[++top]=t->right;   
   t->rvisit=1;
   count=count+stack[top]->data;
  }
  else
  {//  
   count=count-stack[top]->data;
   top--;
  }
 }//while
 return leaf;
}

Node* build(int n,int *a1, int *a2)
{
 if(n<=0) return NULL;
 Node *root=newNode();
 root->data=a2[n-1];// n-1  
 int p=find(a2[n-1],a1,n);
 root->left=build(p,a1,a2);
 root->right=build(n-p-1,a1+p+1,a2+p);  
 return root;   
}

int find(int t,int *a,int len)
{
 int i=0;
 while(idata=0;
  u->lvisit=0;
  u->rvisit=0;
  u->left=u->right=NULL;          
 }     
 return u;
}

void remove_tree(Node *u)
{
 if(u!=NULL)
 {
  remove_tree(u->left);
  remove_tree(u->right);
  free(u);          
 }    
}