자료구조 프로그래밍 Lab05) 최소 좌향 트리 만들기(Leftist Min Tree, Heap)

자료구조 프로그래밍 Lab05) 최소 좌향 트리 만들기(Leftist Min Tree, Heap)

문제

최소 좌향 트리의 병합 과정은 다음과 같다.

해결 알고리즘

Main 함수.

0. TreePointer를 저장할 Queue와 levelOrder로 출력할 Queue2와 Queue에 들어있는 각 Tree들의 size를 저장할 배열 TreeSize를 준비한다.

1. 입력파일의 값을 하나씩 읽으면서 NodePointer로 만들어 Queue에 push 한다(이 때, TreeSize에 해당 rear로 1을 넣어준다).

2. While 문(queue의 값이 하나가 될 때까지) 반복.

3. NodePointer 두개를 pop 해서 minMeld를 통해 합친다.

4. 합치면서 TreeSize의 front 인덱스로 접근해서 사이즈를 가져와서 합쳐서 다시 TreeSize의 rear 인덱스에 값 넣기.

5. TreeSize의 front+1 ~ rear 까지 Size가 2 이상인 트리만 Queue에서 찾아서 출력.

 

void main(int ac, char * av[]) {
 
    nodePointer aTree, bTree, tempTree;
    aTree = bTree = tempTree = NULL;
    int data;
    int finIDX;
    int count = 1;
    int n;
    int aSize, bSize;
 
    // ARGUMENT ERROR
    if (ac != 3) {
        fprintf(stderr, "YOU MUST 2 ARGUMENT ex) program input.txt output.txt\n");
        exit(0);
    }
 
    // 파일 열기
    if ((fp1 = fopen(av[1], "r")) == NULL) {
        fprintf(stderr, "FILE OPEN ERROR!\n");
        exit(0);
    }
    if ((fp2 = fopen(av[2], "w")) == NULL) {
        fprintf(stderr, "FILE WIRTE ERROR!\n");
        exit(0);
    }
    
    // 사이즈 읽어오기
    fscanf(fp1, "%d ", &size);
    
    // 할당
    queue = (nodePointer*)malloc(sizeof(nodePointer)*(size * 100));
    queue2 = (nodePointer*)malloc(sizeof(nodePointer)*(size * 100));
    treeSize = (int *)malloc(sizeof(int)*(size * 100));
 
    // 하나씩 만들기
    for (int i = 0; i < size; i++) {
        fscanf(fp1, "%d ", &data);
        tempTree = makeNode(data); // 만들기
        addQ(tempTree); //Q에 넣기
        treeSize[rear] = 1; // 개수 1 넣기
    }
 
    // Q가 1개 남을 때 까지
    while ((rear-front) != 1) {
 
        // 두개 트리 꺼내서
        aTree = delQ(), aSize = treeSize[front];
        bTree = delQ(), bSize = treeSize[front];
 
        // 합치기
        minMeld(&aTree, &bTree);
 
        // 다시 넣기
        addQ(aTree);
        treeSize[rear] = aSize + bSize;
        
        // 출력
        fprintf(fp2, "**모든 트리 출력**\n");
        for (int i = front + 1; i <= rear; i++) {
            // 2개 이상 완성된 트리만 출력
            if (treeSize[i] > 1) {
                front2 = rear2 = -1; // queue2 초기화
                levelOrder(queue[i], treeSize[i]);
                fprintf(fp2, "\n\n");
            }
        }
 
    }
 
    // 트리비우기
    freeTree(queue[rear]);
 
    // 메모리 해제
    free(queue);
    free(queue2);
    free(treeSize);
 
    // 파일닫기
    fclose(fp1);
    fclose(fp2);
}

minMeld 함수

CASE 1. aTree가 NULL 일 경우

0. aTree가 NULL이면 bTree 대입 연산

1. bTree에 NULL값을 주고 종료.

CASE 2. aTree가 NULL이 아닐 경우

0. aTree가 값이 있다면 minUnion 함수 호출.

1. minUnion에서 aTree의 data가 bTree의 data 크다면 Tree SWAP(aTree의 루트에 가장 작은 값 와야함!)

2-a. aTree의 rch가 없다면 aTree->rch = bTree (무조건 좌향트리는 먼저 rch에 넣고 SWAP)

2-b. aTree의 rch가 있다면 aTree->rch, bTree를 minUnion 재귀함수로 호출

3. 재귀 함수들 종료 후

3-a. aTree의 lch가 없다면 aTree->lch와 aTree->rch를 SWAP

3-b. aTree의 lch가 있다면 lch와 rch의 Shortest (가상 노드까지의 거리)를 비교해서 더 큰 값을 lch에 넣기

4. aTree의 shortest는 rch가 없다면 1이고 있으면 rch의 shortest+1이 된다.

// 병합하기
void minMeld(nodePointer *a, nodePointer *b) {
    // a가 NULL이면 b 트리 넣기
    if (!*a) *a = *b;
 
    // b가 NULL이 아니면 a,b 합치기
    else if (*b) minUnion(a, b);
 
    // 남은 b에 NULL 주기
    *b = NULL;
}
 
// 실제 합치기
void minUnion(nodePointer *a, nodePointer *b) {
    
    nodePointer temp;
 
    // a의 값이 더 크면 b의 값과 교환
    if ((*a)->data > (*b)->data)
        SWAP(*a, *b, temp);
 
    // a의 rch가 없으면 b를 rch로 넣기
    if (!(*a)->rch)
        (*a)->rch = *b;
 
    // a의 rch가 있으면 rch와 b를 재귀적 호출 
    else
        minUnion(&(*a)->rch, b);
 
    // 재귀함수 끝난 다음 lch가 없다하면 rch를 lch로 넘겨주기!
    if (!(*a)->lch) {
        (*a)->lch = (*a)->rch;
        (*a)->rch = NULL;
    }
 
    // 둘다 있는데 rch가 더 많으면 스왑하기
    else if ((*a)->lch->shortest < (*a)->rch->shortest)
        SWAP((*a)->lch, (*a)->rch, temp);
 
    // shortest 값은 rch가 없으면 1을 주고 있으면 rch의 shortest+1 값을 준다
    (*a)->shortest = (!(*a)->rch) ? 1 : (*a)->rch->shortest + 1;
}
 

출력함수

// levelOrder
void levelOrder(nodePointer ptr, int check) {
    
    nodePointer temp = ptr;
    int count = 1, lineCount=2;
    int sizeCheck = 0;
    int lineCheck = 2;
 
    // 처음 시작
    addQ2(temp);
    fprintf(fp2, "Root node : ");
 
    // 빌 때 까지
    while (front2 != rear2) {
        // pop
        temp = delQ2();
 
        // NULL 일 경우 
        if (!temp) {
            fprintf(fp2, "- ");
            addQ2(NULL);
            addQ2(NULL);
        }
 
        // 정상 출력
        else {
            fprintf(fp2, "%d ", temp->data);
            // 자식 노드 넣기
            addQ2(temp->lch);
            addQ2(temp->rch);
            sizeCheck++;
            
            // 다 출력했을경우 탈출
            if (sizeCheck == check)
                return;
        }
        
        // 줄바꿈 처리
        if (count == (lineCheck - 1)) {
            fprintf(fp2, "\nlevel %d nodes : ",lineCount++);
            lineCheck = lineCheck * 2;
        }
 
        // 개수 증가
        count++;
    
    }
 
}