[C언어] 자료구조: 이진 트리 - 노드 생성, 삭제, 탐색

프로그래밍 언어 중에서도 고전적인 매력을 지닌 C언어는 시스템 프로그래밍이나 임베디드 시스템 개발에서 자주 사용됩니다. 특히 자료구조를 이해하고 구현하는 데 있어 C언어는 필수적인 도구이며, 그중 트리(Tree)는 매우 중요한 자료구조 중 하나입니다. 이 글에서는 C언어로 트리를 구현하는 방법부터 시작해서, 다양한 트리 종류와 옵션들을 자세히 설명하고자 합니다.

트리는 계층적 구조를 가진 자료구조로, 루트 노드에서 시작하여 여러 개의 자식 노드를 가질 수 있는 구조입니다. 파일 시스템이나 조직도, 계층적 데이터를 다룰 때 주로 사용되며, 이진 탐색 트리, 힙, AVL 트리, B-트리 등 다양한 변형이 존재합니다. C언어로 트리를 구현하려면 포인터 개념을 잘 이해하고 있어야 하며, 노드 구조체 정의부터 삽입, 삭제, 탐색 등의 기능을 직접 구현해야 합니다.

---

노드 구조체 정의

역할

트리를 구성하는 기본 단위인 노드의 구조를 정의합니다.

사용법

C언어에서는 구조체를 이용하여 노드를 정의합니다.

예제

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

결과

이 구조체를 사용하면, 각각의 노드는 데이터를 저장하고 좌우 자식 노드를 가리키는 포인터를 갖게 됩니다. 이를 통해 이진 트리 구조를 만들 수 있습니다.

---

노드 생성 함수

역할

새로운 노드를 생성하여 메모리를 동적으로 할당하고 데이터를 초기화합니다.

사용법

malloc 함수를 이용해 메모리를 할당하고, 초기값을 설정합니다.

예제

Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

결과

입력한 값으로 초기화된 새로운 노드를 동적으로 생성할 수 있습니다.

---

삽입 함수

역할

트리에 새로운 노드를 삽입합니다. 이진 탐색 트리(BST)의 경우, 왼쪽에는 더 작은 값, 오른쪽에는 더 큰 값을 삽입합니다.

사용법

재귀 함수를 사용하여 적절한 위치에 삽입합니다.

예제

Node* insert(Node* root, int value) {
    if (root == NULL) return createNode(value);
    if (value < root->data)
        root->left = insert(root->left, value);
    else
        root->right = insert(root->right, value);
    return root;
}

결과

주어진 값을 올바른 위치에 삽입하여 트리 구조를 유지할 수 있습니다.

---

탐색 함수

역할

트리에서 특정 값을 탐색합니다.

사용법

재귀적으로 노드를 순회하며 값을 찾습니다.

예제

Node* search(Node* root, int value) {
    if (root == NULL || root->data == value)
        return root;
    if (value < root->data)
        return search(root->left, value);
    else
        return search(root->right, value);
}

결과

찾고자 하는 값을 가진 노드의 포인터를 반환하거나, 없으면 NULL을 반환합니다.

---

삭제 함수

역할

트리에서 특정 값을 가진 노드를 삭제합니다.

사용법

삭제할 노드를 찾고, 경우에 따라 자식 노드들을 재배치합니다.

예제

Node* deleteNode(Node* root, int value) {
    if (root == NULL) return NULL;
    if (value < root->data) {
        root->left = deleteNode(root->left, value);
    } else if (value > root->data) {
        root->right = deleteNode(root->right, value);
    } else {
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }
        Node* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

Node* findMin(Node* node) {
    while (node->left != NULL) node = node->left;
    return node;
}

결과

특정 값을 가진 노드를 삭제하고, 트리 구조를 유지합니다.