데이터 구조 과정 설계 (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; }

좋은 웹페이지 즐겨찾기