9 도 OnlineJudge 제목 1009: 이 진 트 리 검색
제목 설명:
두 시퀀스 가 같은 두 갈래 검색 트 리 시퀀스 인지 판단 하기
입력:
하나의 수 n 을 시작 합 니 다. (1 < = n < 20) 은 n 개가 판단 해 야 한 다 는 것 을 나타 내 고 n = 0 일 때 입력 이 끝 납 니 다.
다음 줄 은 하나의 서열 로 서열 의 길이 가 10 보다 작고 (0 ~ 9) 을 포함 하 는 숫자 로 중복 되 지 않 으 며 이 서열 에 따라 이 진 트 리 를 구성 할 수 있 습 니 다.
다음 n 줄 은 n 개의 서열 이 있 습 니 다. 모든 서열 형식 은 첫 번 째 서열 과 같 습 니 다. 이 두 서열 이 같은 두 갈래 검색 트 리 를 구성 할 수 있 는 지 판단 하 십시오.
출력:
시퀀스 가 같 으 면 YES 를 출력 합 니 다. 그렇지 않 으 면 출력 NO 입 니 다.
샘플 입력:
2
567432
543267
576342
0
샘플 출력:
YES
NO
AC 코드:
#include<stdio.h>
#include<string.h>
struct Node{
Node* lchild;
Node* rchild;
int value;
}tree[189];
int loc;
Node* Creat()
{
tree[loc].lchild=tree[loc].rchild=NULL;
return &tree[loc++];
}
char str1[18],str2[18];
int size1,size2;
char *str;
int *size;
Node* CreatTree(int x,Node *p)
{
if(p==NULL)
{
p=Creat();
p->value=x;
return p;
}
if(x<p->value)
{
p->lchild=CreatTree(x,p->lchild);
}
if(x>p->value)
{
p->rchild=CreatTree(x,p->rchild);
}
return p;
}
void PreOrder(Node *p)
{
str[(*size)++]=p->value+'0';
if(p->lchild!=NULL)
{
PreOrder(p->lchild);
}
if(p->rchild!=NULL)
{
PreOrder(p->rchild);
}
}
void InOrder(Node *p)
{
if(p->lchild!=NULL)
{
PreOrder(p->lchild);
}
str[(*size)++]=p->value+'0';
if(p->rchild!=NULL)
{
PreOrder(p->rchild);
}
}
int main()
{
char temp[10];
int n;
while(scanf("%d",&n)!=EOF&&n!=0)
{
loc=0;
scanf("%s",temp);
Node* root=NULL;
for(int i=0;temp[i]!=0;i++)
{
root=CreatTree(temp[i]-'0',root);
}
str=str1;
size1=0;
size=&size1;
PreOrder(root);
InOrder(root);
str1[size1]=0;
while(n-- >0)
{
root=NULL;
scanf("%s",temp);
for(int i=0;temp[i]!=0;i++)
{
root=CreatTree(temp[i]-'0',root);
}
str=str2;
size2=0;
size=&size2;
PreOrder(root);
InOrder(root);
str2[size2]=0;
if(strcmp(str1,str2)==0)
{
printf("YES
");
}
else
{
printf("NO
");
}
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
9. 데이터 구조의 이 진 트 리그 다음 에 우 리 는 이 진 트 리 의 생 성, 소각, 옮 겨 다 니 기, 그리고 각종 이 진 트 리 의 성질 에 착안 하여 (높이, 노드 개수, 균형 여부 등 특성) 이 진 트 리 의 일부 응용 을 소개 해 야 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.