바이너리트리에 들어가기 전에 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
이후 바이너리 트리 문제들을 좀 풀고 벨로그를 정리하다 잤습니다.
