MENU
  1. ホーム
  2. C 언어
  3. C언어로 전위, 중위, 후위 순회 구현하기

C언어로 전위, 중위, 후위 순회 구현하기

C 언어

트리 데이터 구조는 다양한 프로그래밍 문제에서 핵심적인 역할을 합니다. 특히 전위, 중위, 후위 순회는 트리의 노드들을 특정 순서로 탐색하거나 처리하기 위해 사용됩니다. 본 기사에서는 이 세 가지 트리 순회 방식을 C언어로 구현하는 방법을 단계별로 설명하고, 이를 통해 트리 데이터 구조를 효과적으로 다루는 기술을 배워볼 것입니다.

목차

트리 순회란 무엇인가?


트리 순회(Tree Traversal)는 트리 데이터 구조의 모든 노드를 특정 순서에 따라 방문하는 과정입니다. 트리의 구조적 특징을 활용해 데이터를 검색, 수정 또는 처리하는 데 사용됩니다.

전위, 중위, 후위 순회의 차이

  1. 전위 순회 (Preorder Traversal)
  • 노드 방문 순서: 현재 노드 → 왼쪽 자식 → 오른쪽 자식
  • 루트를 먼저 처리하므로 트리 구조를 직렬화하거나 복제하는 데 유용합니다.
  1. 중위 순회 (Inorder Traversal)
  • 노드 방문 순서: 왼쪽 자식 → 현재 노드 → 오른쪽 자식
  • 이진 탐색 트리에서 데이터를 정렬된 순서로 처리하는 데 자주 사용됩니다.
  1. 후위 순회 (Postorder Traversal)
  • 노드 방문 순서: 왼쪽 자식 → 오른쪽 자식 → 현재 노드
  • 노드를 삭제하거나, 자식 노드를 먼저 처리해야 하는 경우 유용합니다.

트리 순회는 트리의 각 노드를 효과적으로 탐색하며 다양한 알고리즘의 기초가 됩니다.

트리 데이터 구조의 기본


트리는 계층적인 데이터 구조로, 노드와 간선으로 구성됩니다. 트리는 루트 노드에서 시작하며, 각 노드는 자식 노드를 가질 수 있습니다. 트리의 구조는 계층적 관계를 표현하는 데 적합하며, 탐색 및 정렬 알고리즘에서 널리 사용됩니다.

트리의 구성 요소

  1. 루트 노드 (Root Node)
  • 트리의 최상단 노드로, 모든 노드의 시작점입니다.
  1. 부모와 자식 노드 (Parent and Child Nodes)
  • 부모 노드는 자식 노드와 연결된 노드입니다.
  • 자식 노드는 부모 노드에서 파생된 하위 노드입니다.
  1. 잎 노드 (Leaf Node)
  • 자식 노드가 없는 노드로, 트리의 가장 말단에 위치합니다.
  1. 간선 (Edge)
  • 노드 간의 연결을 나타냅니다.

간단한 이진 트리 예제


다음은 간단한 이진 트리의 예입니다.

        A
       / \
      B   C
     / \
    D   E
  • 루트 노드: A
  • A의 자식 노드: B, C
  • 잎 노드: D, E, C

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리로, 트리 순회 알고리즘의 기본적인 예제로 활용됩니다.

트리의 기본 구조와 용어를 이해하면 트리 순회 알고리즘을 더 쉽게 배울 수 있습니다.

전위 순회 구현


전위 순회(Preorder Traversal)는 현재 노드 → 왼쪽 자식 → 오른쪽 자식의 순서로 트리의 노드를 탐색합니다. 이 순서는 트리를 직렬화하거나 루트를 먼저 처리해야 하는 작업에 유용합니다.

전위 순회의 C언어 구현


다음은 이진 트리에서 전위 순회를 구현한 코드입니다.

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

// 트리 노드 구조 정의
struct Node {
    char data;
    struct Node* left;
    struct Node* right;
};

// 새 노드 생성 함수
struct Node* createNode(char data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 전위 순회 함수
void preorderTraversal(struct Node* node) {
    if (node == NULL)
        return;

    // 현재 노드 출력
    printf("%c ", node->data);
    // 왼쪽 서브트리 순회
    preorderTraversal(node->left);
    // 오른쪽 서브트리 순회
    preorderTraversal(node->right);
}

// 메인 함수
int main() {
    // 트리 생성
    struct Node* root = createNode('A');
    root->left = createNode('B');
    root->right = createNode('C');
    root->left->left = createNode('D');
    root->left->right = createNode('E');

    printf("전위 순회 결과: ");
    preorderTraversal(root);  // 결과: A B D E C

    return 0;
}

코드 설명

  1. createNode 함수는 새로운 노드를 생성합니다.
  2. preorderTraversal 함수는 재귀적으로 현재 노드와 자식 노드를 탐색합니다.
  3. 메인 함수에서 트리를 생성하고 전위 순회를 호출하여 결과를 출력합니다.

출력 결과

전위 순회 결과: A B D E C

전위 순회는 트리의 각 노드를 빠짐없이 탐색하며, 트리 데이터의 계층적 구조를 직렬화하는 데 유용합니다.

중위 순회 구현


중위 순회(Inorder Traversal)는 왼쪽 자식 → 현재 노드 → 오른쪽 자식의 순서로 트리의 노드를 탐색합니다. 이 순서는 이진 탐색 트리(Binary Search Tree)에서 노드를 정렬된 순서로 방문하는 데 사용됩니다.

중위 순회의 C언어 구현


다음은 이진 트리에서 중위 순회를 구현한 코드입니다.

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

// 트리 노드 구조 정의
struct Node {
    char data;
    struct Node* left;
    struct Node* right;
};

// 새 노드 생성 함수
struct Node* createNode(char data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 중위 순회 함수
void inorderTraversal(struct Node* node) {
    if (node == NULL)
        return;

    // 왼쪽 서브트리 순회
    inorderTraversal(node->left);
    // 현재 노드 출력
    printf("%c ", node->data);
    // 오른쪽 서브트리 순회
    inorderTraversal(node->right);
}

// 메인 함수
int main() {
    // 트리 생성
    struct Node* root = createNode('A');
    root->left = createNode('B');
    root->right = createNode('C');
    root->left->left = createNode('D');
    root->left->right = createNode('E');

    printf("중위 순회 결과: ");
    inorderTraversal(root);  // 결과: D B E A C

    return 0;
}

코드 설명

  1. createNode 함수는 새로운 노드를 생성합니다.
  2. inorderTraversal 함수는 재귀적으로 왼쪽 자식, 현재 노드, 오른쪽 자식을 순서대로 탐색합니다.
  3. 메인 함수에서 트리를 생성하고 중위 순회를 호출하여 결과를 출력합니다.

출력 결과

중위 순회 결과: D B E A C

중위 순회의 활용

  • 이진 탐색 트리 정렬: 중위 순회는 트리를 정렬된 형태로 탐색하므로 데이터 검색 및 정렬에 적합합니다.
  • 계층적 데이터 확인: 트리의 왼쪽부터 오른쪽까지 데이터를 확인할 수 있습니다.

중위 순회를 통해 이진 트리의 데이터를 정렬된 순서로 탐색하고 처리할 수 있습니다.

후위 순회 구현


후위 순회(Postorder Traversal)는 왼쪽 자식 → 오른쪽 자식 → 현재 노드의 순서로 트리의 노드를 탐색합니다. 이 순서는 자식 노드를 먼저 처리해야 하는 작업, 예를 들어 트리 삭제나 하위 트리의 계산에 유용합니다.

후위 순회의 C언어 구현


다음은 이진 트리에서 후위 순회를 구현한 코드입니다.

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

// 트리 노드 구조 정의
struct Node {
    char data;
    struct Node* left;
    struct Node* right;
};

// 새 노드 생성 함수
struct Node* createNode(char data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 후위 순회 함수
void postorderTraversal(struct Node* node) {
    if (node == NULL)
        return;

    // 왼쪽 서브트리 순회
    postorderTraversal(node->left);
    // 오른쪽 서브트리 순회
    postorderTraversal(node->right);
    // 현재 노드 출력
    printf("%c ", node->data);
}

// 메인 함수
int main() {
    // 트리 생성
    struct Node* root = createNode('A');
    root->left = createNode('B');
    root->right = createNode('C');
    root->left->left = createNode('D');
    root->left->right = createNode('E');

    printf("후위 순회 결과: ");
    postorderTraversal(root);  // 결과: D E B C A

    return 0;
}

코드 설명

  1. createNode 함수는 새로운 노드를 생성합니다.
  2. postorderTraversal 함수는 재귀적으로 왼쪽 자식, 오른쪽 자식을 탐색한 후 현재 노드를 처리합니다.
  3. 메인 함수에서 트리를 생성하고 후위 순회를 호출하여 결과를 출력합니다.

출력 결과

후위 순회 결과: D E B C A

후위 순회의 활용

  • 트리 삭제: 부모 노드를 삭제하기 전에 모든 자식 노드를 먼저 삭제해야 하는 작업에 적합합니다.
  • 하위 트리 계산: 자식 노드의 연산 결과를 부모 노드에서 활용해야 하는 경우 사용됩니다.

후위 순회는 트리의 하위 구조를 먼저 처리하고 부모 노드를 나중에 처리하는 작업에 적합한 알고리즘입니다.

다양한 응용 사례


트리 순회는 알고리즘과 데이터 구조의 중요한 부분으로, 다양한 문제 해결과 응용에 활용됩니다. 다음은 전위, 중위, 후위 순회의 주요 응용 사례를 소개합니다.

전위 순회의 응용

  1. 트리 직렬화와 복원
  • 전위 순회를 사용해 트리 구조를 직렬화(Serialization)하여 파일에 저장하거나 네트워크를 통해 전송할 수 있습니다.
  • 저장된 데이터를 역직렬화(Deserialization)하여 트리를 복원합니다.
  1. 루트 우선 작업 처리
  • 루트를 먼저 처리해야 하는 문제(예: 운영체제의 디렉토리 복사)에 사용됩니다.

중위 순회의 응용

  1. 이진 탐색 트리 정렬
  • 중위 순회를 사용하면 이진 탐색 트리의 데이터를 오름차순으로 정렬된 순서로 방문할 수 있습니다.
  • 데이터베이스 쿼리나 정렬 작업에서 활용됩니다.
  1. 수학 표현식 평가
  • 중위 표기법(Infix Notation)으로 수학식을 처리하거나 변환하는 데 사용됩니다.

후위 순회의 응용

  1. 트리 구조 삭제
  • 후위 순회를 사용하여 자식 노드를 먼저 삭제한 후 부모 노드를 삭제하는 방식으로 트리 전체를 제거할 수 있습니다.
  1. 수학 표현식 계산
  • 후위 표기법(Postfix Notation)으로 변환된 수식을 계산하는 데 사용됩니다.

실무 사례

  • 웹 개발: DOM(Document Object Model) 트리에서 특정 요소를 검색하거나 수정할 때 트리 순회 알고리즘이 사용됩니다.
  • 컴파일러 설계: 구문 분석 트리(Parse Tree)에서 구문을 분석하거나 최적화 작업을 수행합니다.
  • 게임 개발: 경로 탐색이나 AI 설계에서 트리 구조와 순회 알고리즘이 활용됩니다.

트리 순회는 단순한 탐색을 넘어 다양한 문제 해결 및 최적화 작업에서 중요한 역할을 합니다. 트리 구조와 순회 알고리즘을 깊이 이해하면 실무에서 복잡한 문제를 효과적으로 해결할 수 있습니다.

요약


C언어에서 트리 순회는 전위, 중위, 후위 순회의 세 가지 방식으로 데이터를 탐색하며, 각 방식은 특정 응용 사례에 적합합니다. 본 기사에서는 트리 구조의 기본 개념부터 각 순회의 구현 방법과 실무 활용 사례까지 설명했습니다. 이를 통해 트리 데이터 구조를 효과적으로 다루고, 다양한 프로그래밍 문제를 해결하는 데 필요한 기초를 다질 수 있습니다.

C 언어
C언어 알고리즘 트리 순회
목차