C의 트리와 그래프

트리와 그래프는 계층적 데이터와 네트워크 데이터를 표현하는 데 사용하는 비선형 자료 구조입니다.

이 단원에서는 다음 내용을 배웁니다:

• 트리와 그래프가 구성되는 방식
• C에서 이진 트리를 구현하는 방법
• 인접 리스트와 인접 행렬을 사용하여 그래프를 표현하는 방법

트리란 무엇인가요?

트리는 Node로 구성된 계층적 자료 구조입니다.

주요 용어:

• 루트 - 최상위 Node입니다.
• 부모와 자식 - 직접 연결된 Node입니다.
• 리프 - 자식이 없는 Node입니다.

예제: 이진 트리 Node

C에서는 왼쪽과 오른쪽 자식 포인터를 가진 struct를 사용하여 이진 트리 Node를 정의합니다.

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

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

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

int main() {
    struct Node *root = createNode(10);
    return 0;
}

이진 트리 순회

순회 방법:

• 중위 순회 (LNR) - 왼쪽, Node, 오른쪽 순서입니다.
• 전위 순회 (NLR) - Node, 왼쪽, 오른쪽 순서입니다.
• 후위 순회 (LRN) - 왼쪽, 오른쪽, Node 순서입니다.

예제: 중위 순회

이 프로그램은 이진 트리를 중위 순회합니다.

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

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

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

int main() {
    struct Node *root = malloc(sizeof(struct Node));
    root->data = 10;
    root->left = NULL;
    root->right = NULL;
    inorder(root);
    return 0;
}

그래프란 무엇인가요?

그래프는 간선으로 연결된 Node(정점)의 모음입니다.

그래프는 다음과 같이 나눌 수 있습니다:

• 방향 그래프 - 간선에 방향이 있습니다.
• 무방향 그래프 - 간선에 방향이 없습니다.

그래프 표현

그래프는 다음과 같은 방법으로 표현할 수 있습니다:

• 인접 행렬 - 연결 관계를 나타내는 2차원 배열입니다.
• 인접 리스트 - 각 Node가 이웃 Node를 가리키는 목록입니다.

그래프 순회

일반적인 순회 방법:

• 너비 우선 탐색 (BFS) - 더 깊이 이동하기 전에 모든 이웃을 방문합니다.
• 깊이 우선 탐색 (DFS) - 되돌아가기 전에 가능한 한 깊이 탐색합니다.

요약

이 레슨에서는 다음을 배웠습니다:

• 트리와 그래프의 구조
• 트리 순회를 수행하는 방법
• 그래프를 표현하고 순회하는 방법

C 자료 구조 섹션을 마칩니다!