데이터 구조 과정 설계 (C 언어) - 두 서열 이 같은 두 갈래 검색 트 리 인지 판단
7354 단어 데이터 구조
요청:
입력: 두 시퀀스 가 같은 두 갈래 검색 트 리 시퀀스 인지 판단 합 니 다. Input 은 n (1 < = n < 20) 을 시작 합 니 다. n 개가 판단 해 야 하고 n = 0 일 때 입력 이 끝 났 음 을 표시 합 니 다.다음 줄 은 하나의 서열 로 서열 의 길이 가 10 보다 작고 (0 ~ 9) 을 포함 하 는 숫자 로 중복 되 지 않 으 며 이 서열 에 따라 이 진 트 리 를 구성 할 수 있 습 니 다.다음 n 줄 은 n 개의 서열 이 있 습 니 다. 모든 서열 형식 은 첫 번 째 서열 과 같 습 니 다. 이 두 서열 이 같은 두 갈래 검색 트 리 를 구성 할 수 있 는 지 판단 하 십시오.
출력: 시퀀스 가 같 으 면 YES 를 출력 합 니 다. 그렇지 않 으 면 NO 를 출력 합 니 다.
Sample Input 567432 543267 576342 0
Sample Output YES NO
설명 하 다.
두 갈래 검색 트 리 = = 두 갈래 찾기 트 리 = = 두 갈래 정렬 트 리
두 갈래 로 나 무 를 수색 하 는 것 은 뿌리 가 왼쪽 아이 종이 보다 크 고 오른쪽 아이 종이 보다 작 으 며 왼쪽 과 오른쪽 나 무 는 모두 이 규칙 에 부합된다.또한 이 진 트 리 의 중간 순 서 는 비 체감 질서 있 는 순서 입 니 다 (같은 점 을 고려 합 니 다).
그리고 하나의 서열 을 확인 하려 면 이 진 트 리 의 선, 중, 후 순 이 옮 겨 다 니 는 두 가 지 를 알 아야 한다. 평소에 이 방면 의 문 제 를 풀 고 이 진 트 리 를 옮 겨 다 니 는 두 가 지 를 제시 해 야 한다.
여기 서 제 가 사용 하 는 것 은 배열 이 옮 겨 다 니 는 순서 입 니 다. 배열 이 같은 지 비교 해서 두 배열 이 이 진 트 리 인지 확인 하 는 것 입 니 다.
소스 코드
#include
#include
#include
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTree;
char PreArray[11],PreArray2[11];
char InArray[11],InArray2[11];
BiTree* CreateBalanceTree(BiTree *T,int x){
if(T == NULL){
T = (BiTree *)malloc(sizeof(BiTree));
T->data = x;
T->lchild = NULL;
T->rchild = NULL;
}
else if(x < T->data){
CreateBalanceTree(T->lchild,x);
}
else if(x > T->data){
CreateBalanceTree(T->rchild,x);
}
return T;
}
int PreOrder(BiTree *T,int index){
PreArray[index++] = T->data;
if(T->lchild != NULL){
PreOrder(T->lchild,index);
}
if(T->rchild != NULL){
PreOrder(T->rchild,index);
}
return index;
}
int InOrder(BiTree *T,int index){
if(T->lchild != NULL){
InOrder(T->lchild,index);
}
InArray[index++] = T->data;
if(T->rchild != NULL){
InOrder(T->rchild,index);
}
return index;
}
int main()
{
int N,x,index,i,j;
char str1[11],str2[11];
BiTree *T;
printf(" :
");
scanf("%d",&N);
while(N != 0){
T = NULL;
index = 0;
printf(" :
");
scanf("%s",&str1);
for(i =0;i < strlen(str1);i++){
T = CreateBalanceTree(T,str1[i]);
}
index = PreOrder(T,index);
PreArray[index] = '\0';
strcpy(PreArray2,PreArray);
index = 0;
index = InOrder(T,index);
InArray[index] = '\0';
strcpy(InArray2,InArray);
for(i = 0;i < N;i++){
T = NULL;
scanf("%s",&str2);
for(j =0;j < strlen(str2);j++){
T = CreateBalanceTree(T,str2[j]);
}
index = 0;
index = PreOrder(T,index);
PreArray[index] = '\0';
if(strcmp(PreArray,PreArray2) != 0){
printf("NO
");
continue;
}
index = 0;
index = InOrder(T,index);
InArray[index] = '\0';
if(strcmp(InArray,InArray2) != 0){
printf("NO
");
continue;
}
printf("YES
");
free(T);
}
printf(" !
");break;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.