C++로 이진 트리에서 루트 노드부터 특정 노드까지의 경로 출력하기

이 튜토리얼에서는 이진 트리(binary tree)에서 루트 노드부터 주어진 노드까지의 경로를 출력하는 프로그램을 만드는 방법을 알아보겠습니다.

각 노드가 서로 다른 값을 가지는 이진 트리가 주어졌을 때, 루트 노드에서 출발하여 특정 노드에 도달하기까지 거치는 모든 노드의 값들을 순서대로 출력해야 합니다.

접근 방식

이 문제는 재귀(recursion)를 사용하면 깔끔하게 해결할 수 있습니다. 이진 트리를 순회하면서 찾고자 하는 값을 재귀적으로 탐색하고, 탐색 과정에서 지나온 노드들의 값을 벡터(vector)에 저장하여 경로를 기록합니다.

동작 순서는 다음과 같습니다.

1. 현재 노드의 값을 경로 배열에 추가합니다.
2. 현재 노드가 찾으려는 값이라면 true를 반환합니다.
3. 왼쪽 또는 오른쪽 서브트리에서 경로를 찾으면 true를 반환합니다.
4. 어느 쪽에서도 찾지 못했다면 배열에서 마지막 값을 제거(백트래킹)하고 false를 반환합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int data;
    Node *left, *right;
};
struct Node* create_node(int data){
    struct Node *new_node = new Node;
    new_node->data = data;
    new_node->left = new_node->right = NULL;
    return new_node;
}
// 루트 노드부터 해당 원소까지의 경로가 존재하는지 확인
bool is_path(Node *root, vector<int>& arr, int x){
    if (!root)
        return false;
    arr.push_back(root->data);
    if (root->data == x)
        return true;
    if (is_path(root->left, arr, x) || is_path(root->right, arr, x))
        return true;
    arr.pop_back();
    return false;
}
// 루트 노드부터 해당 원소까지의 경로 출력
void print_path(Node *root, int x){
    vector<int> arr;
    if (is_path(root, arr, x)){
        for (int i=0; i<arr.size()-1; i++)
            cout << arr[i] << " -> ";
            cout << arr[arr.size() - 1];
    }
    else
        cout << "Path doesn't exists" << endl;
}
int main(){
    struct Node *root = create_node(13);
    root->left = create_node(21);
    root->right = create_node(43);
    root->left->left = create_node(34);
    root->left->right = create_node(55);
    root->right->left = create_node(68);
    root->right->right = create_node(79);
    int x = 68;
    print_path(root, x);
    return 0;
}

실행 결과

13 -> 43 -> 68

코드 설명

위 예제에서 루트 노드의 값은 13이며, 찾으려는 노드의 값은 68입니다. 68은 루트의 오른쪽 자식(43)의 왼쪽 자식에 위치하므로, 최종적으로 13 -> 43 -> 68이라는 경로가 출력됩니다.

만약 트리에 찾으려는 값이 존재하지 않는다면, is_path 함수가 false를 반환하고 "Path doesn't exists"라는 메시지가 출력됩니다.

이 알고리즘의 시간 복잡도는 O(n)이며, 여기서 n은 트리의 노드 개수입니다. 최악의 경우 트리의 모든 노드를 한 번씩 방문해야 하기 때문입니다. 공간 복잡도 역시 재귀 호출 스택과 경로 저장용 벡터 때문에 O(n)입니다.