[c언어] 트리

26 Dec 2023

c언어

C언어에서 트리(tree)는 계층적인 데이터 구조를 표현하는 데 사용됩니다. 트리는 노드(node)들의 집합으로 구성되어 있으며, 각 노드는 자식 노드들과의 연결을 가지고 있습니다. 최상위 노드는 루트 노드로 표시되며, 각 노드는 부모 노드와 연결될 수 있습니다.

트리의 구현

트리는 보통 구조체(Structure)를 사용하여 구현됩니다. 각 노드는 다음과 같이 정의될 수 있습니다:

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

위에서, data는 노드가 저장하는 데이터를 나타내며, left와 right는 해당 노드의 자식 노드를 가리키는 포인터입니다.

트리의 순회

트리를 효율적으로 탐색하기 위해 여러 가지 방법이 사용됩니다. 대표적인 방법으로는 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)가 있습니다. 각 순회 방법은 노드를 어떤 순서로 방문하는지에 따라 다릅니다.

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

예시

다음은 간단한 이진 트리를 C언어로 구현한 예시입니다:

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

int main() {
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("Preorder traversal: ");
    preorder(root);

    return 0;
}

이를 실행하면 다음과 같은 결과가 출력됩니다:

Preorder traversal: 1 2 4 5 3

트리는 C언어에서 많은 응용 분야에서 활용되며, 데이터 구조와 알고리즘의 이해도를 높이는 데 도움이 됩니다.

트리의 구현

트리의 순회

예시

참고 자료