C++로 이진 트리에서 특정 노드의 조상 노드 출력하기

이 문제에서는 하나의 이진 트리와 목표 노드가 주어지며, 해당 노드의 조상(ancestor) 노드를 모두 찾아 출력해야 합니다.

이진 트리란?

이진 트리(Binary Tree)는 모든 노드가 최대 두 개의 자식 노드만 가질 수 있는 특수한 트리 구조입니다. 즉, 각 노드는 자식이 없는 리프 노드이거나, 왼쪽·오른쪽 중 하나 또는 두 개의 자식 노드를 가집니다.

조상 노드란?

이진 트리에서 어떤 노드의 조상(ancestor)이란 해당 노드보다 상위 레벨에 있으면서, 그 노드부터 루트 노드까지의 경로에 포함되는 노드들을 의미합니다.

예를 들어, 값이 3인 노드의 조상 노드는 경로상에 있는 상위 노드들입니다.

문제 해결 접근 방법

이 문제는 다음과 같은 방식으로 해결할 수 있습니다.

1. 루트 노드에서 출발하여 대상 노드를 향해 트리를 아래로 순회합니다.
2. 재귀적으로 왼쪽 또는 오른쪽 서브트리에서 목표 노드를 찾습니다.
3. 목표 노드를 발견한 경로에 있는 노드들을 역순으로 출력하면, 그것이 바로 조상 노드들이 됩니다.

핵심 아이디어는 재귀 함수가 목표 노드를 하위 트리에서 찾았는지 여부를 반환하고, 찾았다면 현재 노드를 출력하는 것입니다.

C++ 구현 예제

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

struct node {
    int data;
    struct node* left;
    struct node* right;
};

// 목표 노드를 찾으면 true를 반환하며, 되돌아오는 경로의 노드를 출력
bool AncestorsNodes(struct node *root, int target) {
    if (root == NULL)
        return false;
    if (root->data == target)
        return true;
    if (AncestorsNodes(root->left, target) || AncestorsNodes(root->right, target)) {
        cout << root->data << " ";
        return true;
    }
    return false;
}

struct node* insertNode(int data) {
    struct node* node = (struct node*) malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return(node);
}

int main() {
    struct node *root = insertNode(10);
    root->left = insertNode(6);
    root->right = insertNode(13);
    root->left->left = insertNode(3);
    root->left->right = insertNode(8);
    root->right->left = insertNode(12);

    cout << "Ancestor Nodes are ";
    AncestorsNodes(root, 8);
    getchar();
    return 0;
}

실행 결과

Ancestor Nodes are 6 10

코드 설명

• AncestorsNodes 함수는 현재 노드가 NULL이면 false를 반환하여 탐색 실패를 알립니다.
• 현재 노드의 값이 목표값과 같으면 true를 반환하여 탐색 성공을 알립니다.
• 왼쪽 또는 오른쪽 서브트리에서 목표 노드를 찾으면, 현재 노드의 값을 출력하고 true를 반환합니다.
• 이 과정 덕분에 목표 노드에서 루트까지 거슬러 올라가는 경로의 노드들이 순서대로 출력됩니다.

위 예제에서 값 8의 조상 노드는 6과 10이므로, 실행 결과로 "6 10"이 출력됩니다. 이 알고리즘의 시간 복잡도는 O(n)이며, n은 트리의 노드 수입니다.