N-ary 트리의 핵심 개념과 프로그래밍 실습

N-ary 트리는 하나의 노드가 최대 N개의 자식을 가질 수 있는 계층적 데이터 구조로, 파일 시스템, 조직도, 탐색 트리 등 다양한 분야에서 활용된다. 이 글에서는 C 언어 기반의 구현 예제를 통해 삽입, 검색, 업데이트, 후위 순회 등의 기본 연산을 다루며, 실제 사례와 함께 그 응용 가능성을 살펴본다.

노드 구조 정의 및 초기화 각 노드는 값과 두 가지 링크 필드를 포함한다: 첫 번째 자식(자식 리스트 시작점)과 형제 노드 연결. 이를 통해 다중 자식 구조를 효율적으로 표현할 수 있다.

typedef struct Node {
    char data;
    struct Node *first_child;
    struct Node *next_sibling;
} Node;

Node* create_node(char value) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = value;
    new_node->first_child = NULL;
    new_node->next_sibling = NULL;
    return new_node;
}

삽입 연산: 형제 노드 추가 부모 노드의 자식 리스트에 새로운 노드를 추가하려면, 현재 마지막 자식까지 이동한 후 연결을 완료해야 한다. 이 과정은 단순한 포인터 조작으로 이루어진다.

void add_sibling(Node* parent, char value) {
    Node* new_node = create_node(value);
    if (parent->first_child == NULL) {
        parent->first_child = new_node;
    } else {
        Node* current = parent->first_child;
        while (current->next_sibling != NULL) {
            current = current->next_sibling;
        }
        current->next_sibling = new_node;
    }
    printf("노드 '%c'가 부모 '%c'의 형제로 추가됨.\n", value, parent->data);
}

검색 연산: 재귀 기반 탐색 트리 전체를 깊이 우선 탐색하여 특정 값을 가진 노드를 찾는다. 루트부터 시작해 각 자식 및 형제를 순차적으로 탐색하며, 일치하는 경우 해당 노드 포인터를 반환한다.

Node* find_node(Node* root, char target) {
    if (!root) return NULL;

    if (root->data == target) return root;

    Node* child = root->first_child;
    while (child) {
        Node* found = find_node(child, target);
        if (found) return found;
        child = child->next_sibling;
    }

    return NULL;
}

값 수정: 노드 정보 갱신 기존 노드를 검색한 후, 데이터 필드를 새 값으로 변경한다. 존재하지 않는 경우 오류 메시지를 출력한다.

void modify_value(Node* root, char old_val, char new_val) {
    Node* node = find_node(root, old_val);
    if (node) {
        node->data = new_val;
        printf("노드 '%c'의 값이 '%c'로 변경됨.\n", old_val, new_val);
    } else {
        printf("해당 노드를 찾을 수 없습니다.\n");
    }
}

후위 순회: 자식 처리 후 부모 방문 후위 순회는 모든 자식 노드를 먼저 방문한 후, 부모 노드를 처리하는 방식이다. 이는 리소스 해제, 식별자 평가, 계산 표현식 평가 등에 적합하다.

void postorder_traverse(Node* node) {
    if (!node) return;

    Node* child = node->first_child;
    while (child) {
        postorder_traverse(child);
        child = child->next_sibling;
    }

    printf("%c ", node->data);
}

응용 사례: 파일 시스템 구조 모델링 디렉토리 구조는 자연스럽게 N-ary 트리 형태로 표현된다. 루트 디렉토리가 루트 노드이고, 하위 폴더/파일이 자식 노드로 연결된다. 이러한 구조는 접근 속도, 계층 관리, 검색 효율성 측면에서 우수한 성능을 제공한다.

또한, 데이터베이스 인덱싱, 네트워크 경로 선택, 컴파일러의 구문 트리 표현 등에서도 널리 사용되며, 복잡한 계층 구조를 단순하고 명확하게 표현할 수 있다는 점에서 강력한 도구로 평가된다.