C언어에서 트리 순회를 위한 스택과 큐 활용 방법

트리 순회는 자료구조의 핵심적인 개념 중 하나로, 트리 데이터 구조의 노드를 특정 순서에 따라 방문하는 과정을 의미합니다. C언어에서 이를 구현할 때 재귀를 사용하는 것이 일반적이지만, 스택과 큐를 활용하면 비재귀적인 방식으로도 효과적으로 순회를 수행할 수 있습니다. 본 기사에서는 스택과 큐를 이용한 트리 순회 기법과 이를 C언어에서 어떻게 구현할 수 있는지 구체적으로 다뤄보겠습니다.

트리 순회의 개요

트리 순회는 트리 구조의 모든 노드를 체계적으로 방문하는 방법입니다. 트리 순회는 크게 세 가지 주요 방식으로 나뉩니다: 전위 순회(Pre-order), 중위 순회(In-order), 후위 순회(Post-order).

전위 순회

루트를 먼저 방문하고, 왼쪽 서브트리를 순회한 후 오른쪽 서브트리를 순회합니다. 순서는 다음과 같습니다: 루트 → 왼쪽 → 오른쪽

중위 순회

왼쪽 서브트리를 먼저 순회하고, 루트를 방문한 후 오른쪽 서브트리를 순회합니다. 순서는 다음과 같습니다: 왼쪽 → 루트 → 오른쪽

후위 순회

왼쪽 서브트리를 먼저 순회하고, 오른쪽 서브트리를 순회한 후 루트를 방문합니다. 순서는 다음과 같습니다: 왼쪽 → 오른쪽 → 루트

레벨 순서 순회

트리의 각 레벨을 순서대로 방문하며, 일반적으로 큐를 활용해 구현합니다. 루트에서 시작하여 동일한 레벨의 노드를 왼쪽에서 오른쪽 순서로 방문합니다.

트리 순회는 데이터 처리의 순서를 정의하며, 각각의 방식은 특정 요구사항에 따라 선택적으로 활용됩니다.

스택을 사용한 비재귀적 트리 순회

재귀적인 방법 없이 트리를 순회하기 위해 스택을 사용할 수 있습니다. 이 방식은 함수 호출 스택 대신 명시적으로 스택을 이용하여 트리의 노드를 관리합니다.

전위 순회

전위 순회를 비재귀적으로 구현하려면, 스택을 사용해 방문할 노드의 순서를 관리합니다. 다음은 구현의 주요 단계입니다:

루트를 스택에 푸시합니다.
스택에서 노드를 팝하고, 이를 방문합니다.
방문한 노드의 오른쪽 자식과 왼쪽 자식을 순서대로 스택에 푸시합니다.
스택이 빌 때까지 반복합니다.

예제 코드:

#include <stdio.h>
#include <stdlib.h>

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

typedef struct Stack {
    Node *node;
    struct Stack *next;
} Stack;

void push(Stack **stack, Node *node) {
    Stack *newNode = (Stack *)malloc(sizeof(Stack));
    newNode->node = node;
    newNode->next = *stack;
    *stack = newNode;
}

Node *pop(Stack **stack) {
    if (*stack == NULL) return NULL;
    Stack *temp = *stack;
    Node *node = temp->node;
    *stack = temp->next;
    free(temp);
    return node;
}

void preorderTraversal(Node *root) {
    if (root == NULL) return;
    Stack *stack = NULL;
    push(&stack, root);

    while (stack != NULL) {
        Node *current = pop(&stack);
        printf("%d ", current->data);

        if (current->right) push(&stack, current->right);
        if (current->left) push(&stack, current->left);
    }
}

// 트리 생성 및 테스트 생략

중위 순회

중위 순회에서는 스택에 왼쪽 자식을 계속 푸시하다가 더 이상 왼쪽 자식이 없는 노드를 방문하고, 오른쪽 자식으로 이동합니다.

후위 순회

후위 순회는 보다 복잡하며, 두 개의 스택을 사용하거나 특별한 알고리즘을 활용해 구현합니다.

스택을 이용한 트리 순회는 재귀의 한계를 극복하고 명시적으로 순회를 제어할 수 있는 유용한 방법입니다.

큐를 사용한 레벨 순서 순회

레벨 순서 순회(Level Order Traversal)는 트리의 각 레벨을 차례대로 방문하는 방식입니다. 이 방식은 큐(Queue)를 사용하여 구현하며, BFS(Breadth-First Search) 알고리즘과 유사합니다.

레벨 순서 순회의 구현 방법

레벨 순서 순회는 다음 단계로 구현됩니다:

루트 노드를 큐에 삽입합니다.
큐에서 노드를 하나씩 꺼내 방문합니다.
방문한 노드의 왼쪽 자식과 오른쪽 자식을 큐에 삽입합니다.
큐가 빌 때까지 반복합니다.

예제 코드

#include <stdio.h>
#include <stdlib.h>

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

typedef struct QueueNode {
    Node *treeNode;
    struct QueueNode *next;
} QueueNode;

typedef struct Queue {
    QueueNode *front, *rear;
} Queue;

void enqueue(Queue *queue, Node *node) {
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    newNode->treeNode = node;
    newNode->next = NULL;
    if (queue->rear) {
        queue->rear->next = newNode;
    } else {
        queue->front = newNode;
    }
    queue->rear = newNode;
}

Node *dequeue(Queue *queue) {
    if (queue->front == NULL) return NULL;
    QueueNode *temp = queue->front;
    Node *node = temp->treeNode;
    queue->front = temp->next;
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    free(temp);
    return node;
}

void levelOrderTraversal(Node *root) {
    if (root == NULL) return;

    Queue queue = {NULL, NULL};
    enqueue(&queue, root);

    while (queue.front != NULL) {
        Node *current = dequeue(&queue);
        printf("%d ", current->data);

        if (current->left) enqueue(&queue, current->left);
        if (current->right) enqueue(&queue, current->right);
    }
}

// 트리 생성 및 테스트 생략

알고리즘 분석

시간 복잡도: 각 노드를 한 번씩 방문하므로 (O(n)), (n)은 노드 수입니다.
공간 복잡도: 큐에 저장되는 최대 노드 수는 최악의 경우 한 레벨의 모든 노드 수로, 완전 이진 트리일 경우 (O(2^h)), (h)는 트리 높이입니다.

적용 사례

트리의 각 레벨별 데이터를 처리하는 작업.
특정 노드에 도달하기 위해 최단 경로를 찾는 작업.

큐를 사용한 레벨 순서 순회는 트리의 전반적인 구조를 탐색하는 데 효과적인 기법입니다.

스택과 큐의 장단점

스택과 큐는 트리 순회에서 각각 다른 방식으로 활용되며, 사용 목적과 상황에 따라 장단점이 다릅니다. 이 섹션에서는 두 자료구조의 특징을 비교하고, 특정 상황에서 어떤 자료구조를 선택해야 할지에 대해 알아봅니다.

스택의 장단점

장점

비재귀적 구현 가능: 재귀 호출을 명시적인 스택으로 대체하여 재귀에 의존하지 않는 순회 구현이 가능합니다.
공간 효율성: 한쪽 방향의 순회에 적합하며, 호출 스택의 공간을 절약할 수 있습니다.
명확한 제어 흐름: 순회 과정을 직접 제어할 수 있어 디버깅과 문제 해결이 용이합니다.

단점

복잡성 증가: 후위 순회 등 일부 경우 구현이 복잡할 수 있습니다.
동적 크기 필요: 노드 수에 따라 스택의 크기가 동적으로 변해야 하므로 메모리 관리가 필요합니다.

큐의 장단점

장점

레벨 기반 탐색에 적합: 레벨 순서 순회 등 트리의 폭을 따라 탐색해야 하는 경우 매우 효과적입니다.
FIFO 특성: 순서를 유지하며 노드를 처리하기에 직관적이고 명확한 탐색 과정을 제공합니다.
넓은 범위의 노드 처리 가능: 트리의 전체 구조를 쉽게 파악할 수 있습니다.

단점

높은 메모리 사용: 큰 트리에서 큐에는 한 번에 많은 노드가 저장될 수 있어 메모리 사용량이 많아질 수 있습니다.
제한된 활용 범위: 깊이 우선 탐색과 같이 노드 순서가 중요한 경우에는 적합하지 않습니다.

스택과 큐의 활용 사례 비교

자료구조	적합한 순회 방식	주요 활용 사례
스택	전위, 중위, 후위 순회	비재귀적 깊이 우선 탐색
큐	레벨 순서 순회	넓이 우선 탐색, 레벨 기반 탐색

요약

스택은 깊이 우선 탐색과 비재귀적 구현에 유용하며, 큐는 레벨 순서와 넓이 우선 탐색에 적합합니다.
구현할 순회 방식과 트리 구조의 크기에 따라 적절한 자료구조를 선택하는 것이 중요합니다.

구현 시 발생할 수 있는 오류와 해결 방안

스택과 큐를 활용한 트리 순회 구현 중에는 다양한 오류가 발생할 수 있습니다. 이 섹션에서는 자주 발생하는 문제와 이를 해결하기 위한 방법을 제시합니다.

1. 널 포인터 접근 오류

트리 노드가 NULL인 경우 이를 적절히 처리하지 않으면 프로그램이 크래시할 수 있습니다.

발생 원인

NULL 노드에 접근하거나 이를 스택 또는 큐에 추가하려고 시도함.
루트 노드가 NULL인 트리를 순회하려는 경우.

해결 방안

모든 노드에 접근하기 전에 NULL인지 확인하는 조건문을 추가합니다.
루트가 NULL인지 먼저 검사하고, 순회 과정을 시작합니다.

if (root == NULL) {
    printf("Tree is empty.\n");
    return;
}

2. 스택 또는 큐의 메모리 누수

스택과 큐를 동적으로 할당했을 경우, 해제되지 않은 메모리 누수가 발생할 수 있습니다.

발생 원인

스택이나 큐를 다 사용한 후 메모리를 해제하지 않음.
반복 과정에서 임시로 할당된 노드가 메모리에 남아있음.

해결 방안

스택이나 큐의 메모리를 모두 사용한 후 명시적으로 해제합니다.
프로그램 종료 전에 사용된 모든 동적 메모리를 해제합니다.

while (stack != NULL) {
    pop(&stack);
}
// 큐 해제 로직도 필요

3. 무한 루프

트리 순회 과정에서 종료 조건이 설정되지 않으면 무한 루프에 빠질 수 있습니다.

발생 원인

스택이나 큐가 비어있을 때 루프를 종료하지 않음.
잘못된 순서로 노드를 처리하여 순회가 중복되거나 끝나지 않음.

해결 방안

루프 종료 조건을 명확히 정의합니다.
스택과 큐의 상태를 반복적으로 확인하여 종료 여부를 판단합니다.

while (stack != NULL) {
    Node *current = pop(&stack);
    if (current == NULL) continue;
    // 노드 처리 로직
}

4. 잘못된 노드 삽입 또는 제거

스택이나 큐에 노드를 잘못 삽입하거나 순서를 혼동하면 잘못된 순회 결과가 나올 수 있습니다.

발생 원인

스택 또는 큐에 노드를 삽입하는 순서를 바꿈.
팝한 노드를 제대로 처리하지 않음.

해결 방안

자료구조의 삽입 및 제거 순서를 철저히 검토합니다.
각 단계에서 올바른 순서로 노드를 처리했는지 디버깅합니다.

if (current->right) push(&stack, current->right);
if (current->left) push(&stack, current->left);

5. 데이터 출력 누락

모든 노드를 순회하지 않으면 데이터가 누락될 수 있습니다.

발생 원인

특정 조건에서 노드를 스킵하거나 잘못된 트리 구조를 탐색.

해결 방안

테스트 데이터를 사용하여 모든 노드가 방문되는지 확인합니다.
디버그 로그를 활용하여 순회 과정을 추적합니다.

결론

구현 과정에서 발생할 수 있는 오류는 철저한 검증과 디버깅을 통해 예방할 수 있습니다. 모든 가능성을 염두에 두고 안정적인 코드를 작성하는 것이 중요합니다.

연습 문제: 스택과 큐를 활용한 트리 구현

트리 순회 개념을 더욱 잘 이해하기 위해 스택과 큐를 활용한 연습 문제를 제시합니다. 이 문제를 통해 비재귀적 트리 순회와 레벨 순서 순회 구현 능력을 실습할 수 있습니다.

문제 1: 스택을 사용한 비재귀적 전위 순회

주어진 이진 트리에서 비재귀적 전위 순회를 구현하세요.

조건:

노드는 다음과 같은 구조체를 사용합니다.

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

스택을 이용해 전위 순회를 구현하고 노드 데이터를 출력하세요.

예제 입력 트리:

예상 출력:

1 2 4 5 3 6

문제 2: 큐를 사용한 레벨 순서 순회

주어진 이진 트리에서 레벨 순서 순회를 구현하세요.

조건:

큐를 이용해 각 레벨의 노드를 순서대로 출력합니다.
사용자가 트리를 입력할 필요 없이, 코드에 트리를 직접 정의합니다.

예제 입력 트리:

예상 출력:

1 2 3 4 5 6

문제 3: 후위 순회와 레벨 순서 순회의 결합

트리를 후위 순회한 결과와 레벨 순서 순회한 결과를 각각 출력하는 프로그램을 작성하세요.

추가 조건:

후위 순회는 스택을 이용하여 비재귀적으로 구현합니다.
레벨 순서 순회는 큐를 활용합니다.
두 순회 방식의 차이를 비교하는 코멘트를 코드에 추가하세요.

힌트 및 가이드

스택은 Last In, First Out (LIFO), 큐는 First In, First Out (FIFO)의 특성을 가집니다. 이를 활용하여 순회 방식을 설계하세요.
디버그를 위해 순회 중 각 단계에서 스택이나 큐의 상태를 출력해보세요.
트리 노드의 데이터를 생성하는 별도의 함수(예: createNode(int data))를 작성하면 코드를 재사용하기 쉽습니다.

도전 과제

트리가 주어지지 않았을 때, 사용자가 입력한 데이터를 기반으로 트리를 동적으로 생성하고 순회하는 프로그램을 작성해 보세요.
완전 이진 트리가 아닌 일반 이진 트리에 대해서도 코드를 테스트하세요.

결론

위 연습 문제를 통해 스택과 큐를 활용한 트리 순회 방식을 실습할 수 있습니다. 각 문제를 해결하면서 자료구조와 알고리즘의 동작 방식을 명확히 이해할 수 있습니다.

요약

본 기사에서는 C언어에서 트리 순회를 효율적으로 구현하기 위해 스택과 큐를 활용하는 방법을 다루었습니다. 스택을 이용한 비재귀적 전위, 중위, 후위 순회 방법과 큐를 활용한 레벨 순서 순회의 구현 과정을 상세히 설명하고, 각각의 장단점을 비교했습니다. 또한, 구현 시 발생할 수 있는 오류와 해결 방안, 실습 문제를 통해 실질적인 이해를 돕고자 했습니다.

스택과 큐를 활용하면 재귀 호출을 사용하지 않고도 트리 순회를 효과적으로 구현할 수 있으며, 특정 요구사항에 따라 적합한 자료구조를 선택하는 것이 중요합니다. 이를 통해 트리 순회의 원리를 이해하고, C언어에서의 활용 능력을 높일 수 있습니다.