C++ 재귀를 활용한 트리 크기 계산 프로그램 작성 방법

이번 문제에서는 하나의 트리가 주어지며, 재귀(recursion)를 활용해 트리의 크기를 계산하는 프로그램을 작성하는 것이 목표입니다.

여기서 말하는 트리의 크기(size)란 트리에 포함된 노드의 총 개수를 의미합니다.

문제 해결 접근 방법

트리의 크기는 다음과 같은 재귀적 관계로 정의할 수 있습니다.

트리의 크기 = 왼쪽 서브트리의 크기 + 오른쪽 서브트리의 크기 + 1(현재 노드)

루트 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리에 대해 각각 재귀 함수를 호출한 뒤, 현재 노드 자신을 의미하는 1을 더해주면 됩니다. 이때 노드가 존재하지 않는 경우(NULL)에는 0을 반환하도록 하는 것이 재귀 호출의 종료 조건, 즉 기저 사례(base case)입니다.

예제로 이해하기

다음과 같은 이진 트리가 있다고 가정해 보겠습니다.

          6
        /   \
       3     7
      / \   /
     1   5 2

위 트리의 크기를 구하는 과정은 다음과 같습니다.

size(6) = size(3) + size(7) + 1

size(6) = (size(1) + size(5) + 1) + (size(2) + size(NULL) + 1) + 1

size(6) = (1 + 1 + 1) + (1 + 0 + 1) + 1

size(6) = 6

결국 트리 전체의 노드 개수인 6이 계산됩니다.

C++ 구현 코드

#include <iostream>
using namespace std;
class node {
    public:
    int data;
    node* left;
    node* right;
};
node* insertNode(int data) {
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    return(Node);
}
int findSize(node* node) {
    if (node == NULL)
       return 0;
    else
       return(findSize(node->left) + 1 + findSize(node->right));
}
int main() {
    node *root = insertNode(6);
    root->left = insertNode(3);
    root->right = insertNode(7);
    root->left->left = insertNode(1);
    root->left->right = insertNode(5);
    root->right->left = insertNode(2);
    cout<<"The size of the given tree is "<<findSize(root);
    return 0;
}

코드 설명

• insertNode(): 새로운 노드를 동적으로 생성하고, 전달받은 데이터를 저장한 뒤 왼쪽·오른쪽 자식 포인터를 NULL로 초기화합니다.
• findSize(): 핵심 재귀 함수입니다. 노드가 NULL이면 0을 반환하고, 그렇지 않으면 왼쪽 서브트리의 크기와 오른쪽 서브트리의 크기에 1을 더한 값을 반환합니다.
• main(): 예제 트리를 구성한 뒤 findSize()를 호출해 결과를 출력합니다.

실행 결과

The size of the given tree is 6

복잡도 분석

시간 복잡도: 모든 노드를 정확히 한 번씩 방문하므로 O(n)입니다. 여기서 n은 트리의 노드 개수입니다.

공간 복잡도: 재귀 호출 스택의 깊이가 트리의 높이에 비례하므로, 균형 잡힌 트리에서는 O(log n), 한쪽으로 치우친 편향 트리에서는 최악의 경우 O(n)입니다.