[자료구조] 이진트리(Binary Tree) 홀수 합(sumOfOddNodes) 구현(C언어)

문제 설명

이번 포스트에서는 이진 트리(Binary Tree)에 저장된 정수들 중 홀수 값만을 골라 합산하는 문제를 해결해보겠습니다.
문제에서는 정수 값을 저장하는 이진 트리의 루트 노드를 입력받아, 트리 내에 존재하는 모든 홀수 노드의 값을 더한 합계를 반환하는 재귀 함수를 구현합니다.

---

문제 요구사항

• 예외 처리:
  • 만약 입력된 이진 트리의 루트 노드(root)가 NULL이면, 함수는 예외 처리 후 0을 반환합니다.
• 노드 합산 방식:
  • 재귀 함수 호출을 통해 이진 트리의 모든 노드를 탐색합니다.
  • 현재 노드의 값이 홀수이면 그 값을 결과 변수 sum에 더합니다.
  • 현재 노드의 왼쪽 서브트리와 오른쪽 서브트리를 재귀적으로 탐색하여, 반환된 합계를 현재 노드의 값과 함께 누적합니다.

---

문제 코드 설명

1. 구조체 정의

1.1 BTNode 구조체

typedef struct _btnode {
    int item;               // 노드가 담고 있는 정수 값
    struct _btnode *left;   // 왼쪽 자식 노드의 주소
    struct _btnode *right;  // 오른쪽 자식 노드의 주소
} BTNode;

• item: 노드에 저장된 정수 값
• left: 왼쪽 서브트리(자식 노드)를 가리키는 포인터
• right: 오른쪽 서브트리(자식 노드)를 가리키는 포인터

1.2 StackNode 구조체

typedef struct _stackNode {
    BTNode *btnode;         // 저장된 이진 트리 노드의 포인터
    struct _stackNode *next; // 다음 스택 노드의 주소
} StackNode; 

• btnode
  • 타입: BTNode *
  • 설명: 이 필드는 스택에 저장되는 이진 트리 노드의 주소를 저장합니다.
    • 즉, 현재 스택 노드가 임시로 보관하고 있는 이진 트리의 노드를 가리킵니다.
• next
  • 타입: struct _stackNode *
  • 설명: 스택 내에서 현재 노드의 바로 아래에 있는(즉, 다음으로 저장된) 스택 노드의 주소를 가리킵니다.
    • 이를 통해 스택은 후입선출(LIFO, Last In First Out) 방식으로 동작할 수 있습니다.

1.3 Stack 구조체

typedef struct _stack {
    StackNode *top;         // 스택의 최상위 노드의 주소
} Stack;

• top
  • 타입: StackNode *
  • 설명: 스택 구조체에서 이 필드는 스택의 최상위(top) 노드의 주소를 저장합니다.
    • push 연산 시 새 노드를 top에 추가하고,
    • pop 연산 시 top에 있는 노드를 제거하면서 스택의 다음 노드로 이동하는 역할을 합니다.

2. 함수 원형

int sumOfOddNodes(BTNode *node);

매개변수:

• BTNode *node: 이진 트리의 루트 노드를 가리키는 포인터입니다. 재귀적으로 각 노드를 탐색하여 홀수 값을 가진 노드들의 합을 계산합니다.​

반환값:

• int: 트리 내 모든 홀수 노드의 값들의 합을 반환합니다.

---

홀수 합 플로우 차트

1. 시작:
   • 함수가 호출되면 입력된 node를 기준으로 작업을 시작합니다.
2. 예외 처리:
   • 만약 node가 NULL이면, 함수는 0을 반환하고 종료됩니다.
3. 현재 노드 처리:
   • sum 변수를 0으로 초기화한 후, 현재 노드의 item 값이 홀수인지 판별합니다.
   • 홀수라면, sum에 현재 노드의 값을 더합니다.
4. 재귀 호출:
   • 왼쪽 서브트리에 대해 재귀 호출을 수행하여 반환된 값을 leftSum에 저장합니다.
   • 오른쪽 서브트리에 대해서도 재귀 호출을 수행하여 반환된 값을 rightSum에 저장합니다.
5. 합산 및 반환:
   • sum에 leftSum과 rightSum을 더한 후 최종 결과를 반환합니다.

---

핵심 아이디어

• 입력된 노드가 NULL이면 0을 반환하고,
• 현재 노드가 홀수이면 그 값을 합산한 후,
• 왼쪽과 오른쪽 서브트리를 재귀적으로 탐색하여 합계를 누적합니다.

---

구현

int sumOfOddNodes(BTNode *node)
{
    // 예외 처리
    if (node == NULL) return 0;

    // 결과 저장할 변수 초기화
    int sum = 0;

    // 들어온 노드 중 홀수인 것을 판별
    // 홀수인 경우, sum에 현재 노드의 값을 더함
    if (node->item % 2 == 1){
        sum += node->item;
    }

    // 왼쪽 서브트리 탐색
    // 왼쪽 자식 노드에서 홀수 노드의 합을 재귀적으로 구하고, 그 값을 sum에 더함
    sum += sumOfOddNodes(node->left);

    // 오른쪽 서브트리 탐색
    // 오른쪽 자식 노드에서 홀수 노드의 합을 재귀적으로 구하고, 그 값을 sum에 더함
    sum += sumOfOddNodes(node->right);

    return sum;
}