C++에서 N-Ary(다진) 트리의 깊이 구하는 방법

N-Ary(다진) 트리는 각 노드가 두 개 이상, 즉 N개까지의 자식 노드를 가질 수 있는 일반화된 트리 구조입니다. 트리의 깊이(depth)란 루트 노드에서 가장 깊은 곳에 있는 리프 노드까지 이어지는 경로의 길이를 의미하며, 자식 노드들을 순회하면서 재귀적으로 계산할 수 있습니다.

이번 글에서는 C++를 이용해 N-Ary 트리의 깊이를 구하는 방법을 코드와 함께 단계별로 알아보겠습니다.

1. 트리 노드 구조체 정의하기

가장 먼저, 문자(character) 타입의 키 값을 저장하고 자식 노드 포인터들을 담는 벡터(vector)를 멤버로 갖는 트리 노드용 구조체를 정의합니다.

struct Node {
    char key;
    vector<Node *> children;
};

2. 노드 생성 함수 작성하기

다음으로 새로운 노드를 동적으로 할당하고 키 값을 초기화한 뒤, 생성된 노드의 포인터를 반환하는 createNode() 함수를 작성합니다.

Node *createNode(char key){
    Node *node = new Node;
    node->key = key;
    return node;
}

3. 트리의 깊이를 계산하는 재귀 함수

depthOfTree() 함수는 루트 노드를 매개변수로 받습니다. 루트가 NULL이라면 더 이상 탐색할 노드가 없으므로 깊이로 0을 반환합니다. 이것이 재귀 호출의 기저 조건(base case)입니다.

int depthOfTree(Node *root){
    if (root == NULL)
        return 0;

그다음 maxDepth 변수를 0으로 초기화한 뒤, 현재 노드의 모든 자식들을 순회하면서 재귀 호출을 진행합니다. 각 자식 서브트리의 깊이에 1을 더한 값 중 가장 큰 값을 maxDepth에 저장하고, 모든 순회가 끝나면 그 값을 반환합니다.

int depthOfTree(Node *root){
    if (root == NULL)
        return 0;
    int maxDepth = 0;
    for (auto i : root->children){
        maxDepth = max(maxDepth, depthOfTree(i) + 1);
    }
    return maxDepth;
}

참고: 자식 노드들의 서브트리 깊이는 서로 다를 수 있으므로, 반드시 std::max를 사용해 기존 maxDepth 값과 비교하면서 갱신해야 합니다. 단순히 대입만 하면 마지막 자식의 결과로 덮어써져 잘못된 깊이가 계산될 수 있습니다.

전체 예제 코드

지금까지 설명한 내용을 바탕으로 N-Ary 트리의 깊이를 구하는 전체 구현은 다음과 같습니다.

#include <iostream>
#include <vector>
using namespace std;

struct Node {
    char key;
    vector<Node *> children;
};

Node *createNode(char key){
    Node *node = new Node;
    node->key = key;
    return node;
}

int depthOfTree(Node *root){
    if (root == NULL)
        return 0;
    int maxDepth = 0;
    for (auto i : root->children){
        maxDepth = max(maxDepth, depthOfTree(i) + 1);
    }
    return maxDepth;
}

int main(){
    Node *root = createNode('S');
    (root->children).push_back(createNode('O'));
    (root->children).push_back(createNode('A'));
    (root->children).push_back(createNode('D'));
    (root->children).push_back(createNode('N'));
    (root->children[0]->children).push_back(createNode('L'));
    (root->children[0]->children).push_back(createNode('I'));
    (root->children[2]->children).push_back(createNode('R'));
    (root->children[3]->children).push_back(createNode('C'));
    (root->children[3]->children).push_back(createNode('H'));
    (root->children[3]->children).push_back(createNode('I'));

    cout << "The depth of the n-ary tree is " << depthOfTree(root) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

The depth of the n-ary tree is 2

동작 원리와 시간 복잡도

예제 트리에서 루트 'S'의 자식인 'O', 'D', 'N' 아래에는 각각 한 단계 더 깊은 리프 노드들이 존재하므로, 루트로부터 가장 깊은 리프까지의 경로 길이는 2가 됩니다. 따라서 출력 결과는 2입니다.

이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)(n은 노드의 총 개수)입니다. 공간 복잡도는 재귀 호출 스택의 깊이에 비례하며, 최악의 경우 O(n)이 됩니다.