WEEK 05 C언어 바이너리트리 1,2,3,4번 문제(4월16일 수요일)

크래프톤 정글(C언어 WEEK 5 ~ 8)

WEEK 05 C언어 바이너리트리 1,2,3,4번 문제(4월16일 수요일)

devkty 2025. 4. 18. 03:48

728x90

바이너리트리에 들어가기 전에 C언어에서의 return에 대한 사실을 발견하게 되서 짧게 알아보고 가겠다.
바이너리트리에 결과값을 반환할 때 해당 개념을 꼭 알아야한다.

return에 대한 새로운 사실

C언어에서는 return 0이 false고, return 1이 true이다.
즉, 1이 반환되면 if 문을 진입하고, 0은 else문을 진입한다.

1. C언어 Binary Tree 1번

1. identical

설명:

두 이진 트리가 구조적으로 동일한지 확인하는 재귀 C 함수 작성

둘 다 비어 있거나, 구조와 값이 완전히 같아야 함
같으면 1 반환, 다르면 0 반환

함수 원형:


int identical(BTNode *tree1, BTNode *tree2);

예시:

tree1과 tree2 모두 1, 3, 2, 5, 4, 7, 8이면

→ 구조 동일 → 반환값: 1

※ 재귀 조건 요약:

둘 다 NULL이면 1
하나만 NULL이면 0
값 다르면 0
왼쪽/오른쪽 비교 결과 곱하여 반환

[풀이 방법]

두개의 이진 트리가 구조적으로 동일한지 재귀 함수를 통해 구현 하면 된다.
만약에 같으면 1반환, 다르면 0을 반환한다.
둘다 NULL 일시 1, 하나만 NULL이면 0, 값이 달라도 NULL이다.
그러므로 Base Condition은 두 트리가 NULL일때 같음으로 종료 시키고, 두 트리가 NULL이 아닐때 왼쪽과 오른쪽 트리를 재귀하여 item 값이 같은지 확인한다.

[코드와 해설]

int identical(BTNode *tree1, BTNode *tree2)

{
   /*
   두개의 이진 트리가 구조적으로 동일한지 재귀 함수를 통해 구현 하면 된다.
   만약에 같으면 1반환, 다르면 0을 반환한다.
   둘다 NULL 일시 1, 하나만 NULL이면 0, 값이 달라도 NULL이다.
   */

   if(tree1 == NULL && tree2 == NULL)    // 트리가 비어있으면 동일하므로 1(true)
   return 1;

   else if(tree1 != NULL && tree2 != NULL) {    // 두 트리 다 NULL아닐시 확인
    return(
        tree1->item == tree2->item &&           // 트리 1,2 아이템 값이 같아야한다.
        identical(tree1->left, tree2->left)&&   // 트리 1,2의 왼쪽과 오른쪽 노드를 재귀적으로 모두 확인한다. 
        identical(tree2->right,tree2->right)    // 트리 왼쪽과 오른쪽 노드를 탐색한다. 해당 아이템도 같아야한다.
    );
   }
   else
   return 0;   // 그 외 사항들 모두 false
}

2. C언어 Binary Tree 2번

2. maxHeight

설명:

이진 트리에서 루트부터 가장 먼 리프 노드까지의 링크 수 반환

※ 빈 트리의 높이는 -1로 간주

함수 원형:

int maxHeight(BTNode *root);

예시:

트리 1, 2, 3, 4, 5, 6, 7이면

→ 최대 높이: 2

[풀이 방법]

트리의 높이를 출력하면된다. 자식 노드부터 생각한다.
리프노드를 제외하고 밑의 칸의 개수만큼 높인다.
즉, 트리가 가로 3줄이면 높이는 2이다.

[코드와 해설]

int maxHeight(BTNode *node)

{
    /*
    트리의 높이를 출력하면된다. 자식 노드부터 생각한다.
    리프노드를 제외하고 밑의 칸의 개수만큼 높인다.
    즉, 트리가 가로 3줄이면 높이는 2이다.
    */

    // 맨 밑 노드부터 스캔하면서 재귀적으로 올라간다고 생각하면 편하다.
   if(node == NULL)    return -1;   // 문제의 조건에 따라 빈 트리는 -1이다.
    else
    {
        int l = maxHeight(node->left);   // 재귀적으로 왼쪽 오른쪽 탐색해서 풀어낸다.
        int r = maxHeight(node->right);

        if(l > r)   return l + 1;   // 자식 노드가 생김을 고려해서 +1을 해준다.(더큰 자식쪽)
        else    return r + 1;
    }
}

3. C언어 Binary Tree 3번

3. countOneChildNodes

설명:

자식이 하나만 있는 노드의 개수를 세는 함수 작성

함수 원형:

int countOneChildNodes(BTNode *root);

예시:

트리 (10, 20, 55, 30, 50, 60, 80) → 자식 1개인 노드 수: 2

※ 재귀 조건 요약:

NULL이면 0
자식이 하나면 + 1
양쪽 자식 있으면 좌 + 우

[풀이 방법]

자식이 1개인 노드의 합을 구하면 된다.
NULL이면 0임을 예외처리
재귀를 돌려서 자식이 있는지 확인
노드들 중에서 자식이 1개 인 노드를 모두 더해서 출력(3번째 줄)
자식이 1이 아니라면, 다음 노드 탐색

[코드와 해설]

int countOneChildNodes(BTNode *node)

{
    /*
    자식이 1개인 노드의 합을 구하면 된다.
    NULL이면 0임을 예외처리
    재귀를 돌려서 자식이 있는지 확인
    노드들 중에서 자식이 1개 인 노드를 모두 더해서 출력 3번째 줄
    자식이 1이 아니라면, 다음 노드 탐색
    */
    if (node == NULL)  return 0;    // 예외 케이스

    int count = 0;

    // 자식이 하나만 있는 경우 체크(두가지 케이스)
    if ((node->left == NULL && node->right != NULL) ||
        (node->left != NULL && node->right == NULL)) {
        count = 1;
    }

    // 재귀적으로 자식들도 검사
    return count + countOneChildNodes(node->left) + countOneChildNodes(node->right);
}

4. C언어 Binary Tree 4번

4. sumOfOddNodes

설명:

이진 트리에 저장된 홀수 값들의 합을 반환하는 재귀 함수

함수 원형:

int sumOfOddNodes(BTNode *root);

예시:

트리 (11, 40, 35, 50, 80, 60, 85)

→ 홀수 합: 11 + 35 + 85 = 131

[풀이 방법]

간단히 노드 값이 홀수인 값들의 합을 반환하는 재귀함수를 구현한다.
node->item 값을 2와 나눠서 나머지가 1이면 홀수이다.
그값들을 따로 빼서 더하면 될 것 같다.

[코드와 해설]

int sumOfOddNodes(BTNode *node)

{
    /*
    간단히 노드 값이 홀수인 값들의 합을 반환하는 재귀함수를 구현한다.
    node->item 값을 2와 나눠서 나머지가 1이면 홀수이다.
    그값들을 따로 빼서 더하면 될 것 같다.
    */

    if (node == NULL)  return 0;    // 예외 케이스

    // 본인값이 2 나눈 나머지 1이면 홀수.
    else if(node->item % 2 == 1) {
        return(sumOfOddNodes(node->left) + sumOfOddNodes(node->right) + node->item);  // 본인값 더 해서 재귀
    }

    // 그외의 경우에는 계속 탐색(본인 값 더하지말고)
    else
        return countOneChildNodes(node->left) + countOneChildNodes(node->right);
}

5주차 새로운 마무리

전 포스팅에서 말했던 것처럼 내일은 5주차의 마지막날이다.
기존에는 시험으로 한 주를 마무리 했지만, C언어 주차부터는 일주일동안 C언어 코드를 작성하며 본인이 코드리뷰를 원하는 파일 1개만 올려서 코드리뷰를 받습니다.
또한 점심시간까지 각 조별로 일주일간의 트러블 슈팅, 새로운 방식, 느낀점 등을 자유롭게 발표하는 시간을 가집니다. 그래서 팀원과 함께 발표자료를 만들었습니다.

팀별 발표자료 구성(11:30 ~ 01:30)

저는 스택 앤 큐 7번 대괄호, 중괄호, 소괄호의 짝이 맞으면 균형이 맞음을 출력하는 문제입니다.
아스키코드를 이용하여 푸는 방법에 대해서 핵심적인 부분만 간추려서 코드와 함께 발표자료를 준비했습니다. 팀원분들의 피드백을 적극 반영하여 처음봐도 알기 쉬운 방식으로 발표를 준비했습니다.
발표시간은 총 6분이 주어졌기 때문에 팀원간 호흡을 맞춰 5분45초쯤으로 맞췄습니다.

1:30 ~ 5:00
이후 바이너리 트리 문제들을 좀 풀고 벨로그를 정리하다 잤습니다.

728x90