C++로 완전 이진 트리의 루트에서 모든 노드까지의 경로 출력하기

C++로 완전 이진 트리의 모든 경로 출력하기

이 튜토리얼에서는 완전 이진 트리(complete binary tree)에서 루트 노드로부터 트리 내 모든 노드까지의 경로를 출력하는 프로그램을 C++로 구현하는 방법을 알아봅니다.

문제 정의

숫자 N이 주어지며, 이는 이진 트리에 1부터 N까지의 노드가 존재함을 의미합니다. 이때 1번 노드가 트리의 루트(root)입니다. 따라서 우리의 목표는 루트 노드에서 출발하여 트리에 있는 각 노드에 도달하는, 가능한 모든 경로를 출력하는 것입니다.

접근 방식

완전 이진 트리의 핵심 성질을 활용하면 이 문제를 효율적으로 해결할 수 있습니다. 배열 기반 표현에서 인덱스가 i인 노드의 자식 노드는 다음과 같이 계산됩니다.

왼쪽 자식: 2 × i
오른쪽 자식: 2 × i + 1

이 성질에 백트래킹(backtracking) 기법을 적용하면, 현재까지 탐색한 경로를 벡터(vector)에 저장해 두었다가 각 노드에 도달할 때마다 그 경로를 출력할 수 있습니다.

구현 예제

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

// 루트 노드에서 가능한 모든 경로를 계산하는 함수
void calc_allpath(vector<int> paths, int nth_node, int kth_node){
    if (kth_node > nth_node)
        return;
    paths.push_back(kth_node);
    for (int i = 0; i < paths.size(); i++)
        cout << paths[i] << " ";
    cout << endl;
    calc_allpath(paths, nth_node, kth_node * 2);      // 왼쪽 자식 탐색
    calc_allpath(paths, nth_node, kth_node * 2 + 1);  // 오른쪽 자식 탐색
}

// 루트 노드에서 가능한 모든 경로를 출력하는 함수
void print_allpath(int nth_node){
    vector<int> paths;
    calc_allpath(paths, nth_node, 1);
}

int main(){
    int nth_node = 9;
    print_allpath(nth_node);
    return 0;
}

실행 결과

동작 원리

위 코드는 루트(1)에서 출발해 매 단계마다 현재까지의 경로를 출력한 뒤, 왼쪽 자식(2×k)과 오른쪽 자식(2×k+1)을 차례로 재귀 호출합니다. 노드 번호가 N을 초과하면 해당 분기의 탐색을 종료합니다. 예를 들어 N=9일 때 1 → 2 → 4 → 8, 1 → 2 → 4 → 9, 1 → 2 → 5, 1 → 3 → 6, 1 → 3 → 7처럼 루트에서 리프 노드와 중간 노드까지의 모든 경로가 순서대로 출력되는 것을 확인할 수 있습니다.

복잡도 분석

노드의 개수를 N이라 할 때, 루트에서 임의의 노드까지 경로의 최대 길이는 O(log N)입니다. 모든 노드에 대해 경로를 출력해야 하므로 전체 시간 복잡도는 O(N log N)이며, 경로를 저장하는 벡터와 재귀 호출 스택으로 인한 추가 공간 복잡도는 O(log N)입니다.