[c언어] 이진 탐색 트리

26 Dec 2023

c언어

이진 탐색 트리(Binary Search Tree, BST)는 데이터를 저장하고 탐색하는데 사용되는 효율적인 자료구조입니다. C언어로 간단한 이진 탐색 트리를 구현해보겠습니다.

이진 탐색 트리란?

이진 탐색 트리는 모든 노드가 다음의 성질을 만족하는 이진 트리입니다:

왼쪽 서브트리에는 루트 노드보다 작은 값의 노드들이 위치하며
오른쪽 서브트리에는 루트 노드보다 큰 값의 노드들이 위치합니다.

C언어로 이진 탐색 트리 구현하기

아래는 간단한 구조체를 사용하여 이진 탐색 트리를 구현한 코드입니다.

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

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

struct Node* createNode(int item) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

struct Node* insert(struct Node* node, int key) {
    if (node == NULL) return createNode(key);

    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);

    return node;
}

void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->key);
        inorderTraversal(root->right);
    }
}

int main() {
    struct Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    printf("이진 탐색 트리 (중위 순회): ");
    inorderTraversal(root);

    return 0;
}

위 코드는 간단한 이진 탐색 트리를 생성하고, 값을 삽입한 후 중위 순회(inorder traversal)하여 값을 출력하는 코드입니다.

이처럼 C언어를 사용하여 간단한 이진 탐색 트리를 구현할 수 있습니다. 만약 이진 탐색 트리에 대한 더 많은 정보가 필요하다면 Python, Java 등 다른 언어로 구현된 자료 구조 자료를 참고해보세요.