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

문제 소개

이 문제에서는 하나의 이진 트리가 주어지며, 트리 내 특정 노드의 조상(ancestor) 노드들을 모두 출력해야 합니다.

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드만 가질 수 있는 특수한 형태의 트리입니다. 즉, 모든 노드는 자식이 없는 리프 노드이거나, 한 개 또는 두 개의 자식 노드를 갖습니다.

조상 노드란?

이진 트리에서 어떤 노드의 조상이란, 해당 노드보다 상위 레벨에 위치하면서 루트 노드로부터 그 노드까지의 경로에 있는 노드를 의미합니다.

예를 들어, 값이 17인 노드의 조상은 루트에서 해당 노드까지의 경로에 있는 15, 25, 27과 같은 노드들입니다.

해결 접근 방식

이 문제를 해결하기 위해서는 루트 노드에서 목표 노드까지 이진 트리를 따라 단계적으로 아래로 탐색하면서, 경로에 있는 모든 노드를 출력하면 됩니다.

일반적으로는 루트에서 목표 노드까지의 경로에 있는 각 노드마다 동일한 함수를 재귀적으로 호출하는 방식을 사용하지만, 여기서는 재귀를 사용하지 않는 방법을 다룹니다.

재귀 대신 반복문 기반의 순회(iterative traversal)와 스택(stack)을 활용합니다. 구체적인 알고리즘은 다음과 같습니다.

이진 트리를 후위 순회(postorder traversal) 방식으로 순회합니다.
목표 노드를 찾을 때까지 지나온 노드들을 스택에 저장합니다. 이때 스택에는 목표 노드의 조상들이 쌓이게 됩니다.
목표 노드를 발견하면 탐색을 종료하고, 스택의 내용을 차례대로 출력합니다. 출력된 값들이 바로 해당 노드의 조상입니다.

C++ 구현 예제

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

struct Node {
    int data;
    struct Node *left, *right;
};

struct Stack {
    int size;
    int top;
    struct Node* *array;
};

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

struct Stack* createStack(int size) {
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
    stack->size = size;
    stack->top = -1;
    stack->array = (struct Node**) malloc(stack->size * sizeof(struct Node*));
    return stack;
}

int isFull(struct Stack* stack) {
    return ((stack->top + 1) == stack->size);
}

int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

void push(struct Stack* stack, struct Node* node) {
    if (isFull(stack))
        return;
    stack->array[++stack->top] = node;
}

struct Node* pop(struct Stack* stack) {
    if (isEmpty(stack))
        return NULL;
    return stack->array[stack->top--];
}

struct Node* peek(struct Stack* stack) {
    if (isEmpty(stack))
        return NULL;
    return stack->array[stack->top];
}

void AncestorNodes(struct Node *root, int key) {
    if (root == NULL)
        return;
    struct Stack* stack = createStack(MAX_SIZE);
    while (1) {
        while (root && root->data != key) {
            push(stack, root);
            root = root->left;
        }
        if (root && root->data == key)
            break;
        if (peek(stack)->right == NULL) {
            root = pop(stack);
            while (!isEmpty(stack) && peek(stack)->right == root)
                root = pop(stack);
        }
        root = isEmpty(stack) ? NULL : peek(stack)->right;
    }
    while (!isEmpty(stack))
        printf("%d ", pop(stack)->data);
}

int main() {
    struct Node* root = insertNode(15);
    root->left = insertNode(10);
    root->right = insertNode(25);
    root->left->left = insertNode(5);
    root->left->right = insertNode(12);
    root->right->left = insertNode(20);
    root->right->right = insertNode(27);
    root->left->left->left = insertNode(1);
    root->left->right->right = insertNode(14);
    root->right->right->left = insertNode(17);

    printf("The ancestors of the given node are : ");
    AncestorNodes(root, 17);
    getchar();
    return 0;
}

실행 결과

The ancestors of the given node are : 27 25 15

정리

위 코드는 값이 17인 노드를 목표로 설정하고, 후위 순회와 스택을 이용해 재귀 호출 없이 조상 노드들을 찾아냅니다. 실행 결과에서 볼 수 있듯이, 목표 노드 17의 조상인 27, 25, 15가 순서대로 출력됩니다. 이 방법은 재귀 호출로 인한 스택 오버플로우 위험을 피할 수 있어 깊이가 큰 트리에서도 안전하게 사용할 수 있다는 장점이 있습니다.