C언어] 트리

[트리]

1. 트리 란?
트리(Tree)는 계층적인 구조를 나타내는 자료구조로, 노드(node)들이 간선(edge)으로 연결되어 있는 구조를 갖는다. 각 노드는 하나의 부모(parent) 노드와 여러 개의 자식(child) 노드를 가질 수 있다. 트리는 데이터를 효율적으로 조직화하고 검색하는 데 사용된다.

 

배열, 연결리스트, 스택, 큐 등은 모두 1차원 선형적인 구조를 가지는데 비해 트리는 2차원적인 구조를 가진다.

 

트리 용어

노드(Node): 트리의 기본 구성 요소로, 데이터를 저장하는 요소입니다. 각 노드는 부모와 자식 노드 간의 연결을 갖습니다.

루트 노드(Root Node): 트리의 시작점에 위치한 최상위 노드를 가리킵니다. 트리는 하나의 루트 노드만을 가집니다.

부모 노드(Parent Node): 어떤 노드의 바로 위에 위치한 노드를 가리킵니다. 부모 노드는 해당 노드에 대한 직접적인 상위 계층을 형성합니다.

자식 노드(Child Node): 어떤 노드의 바로 아래에 위치한 노드를 가리킵니다. 자식 노드는 해당 노드에 대한 하위 계층을 형성합니다.

리프 노드(Leaf Node): 자식이 없는 노드로, 트리의 가장 끝단에 위치한 노드를 가리킵니다.

서브트리(Subtree): 트리 내의 어떤 노드와 그 자손 노드들로 이루어진 부분 트리를 가리킵니다.

차수(Degree): 어떤 노드가 가지고 있는 자식의 개수를 가리킵니다. 노드의 차수는 해당 노드의 서브트리 개수와도 관련이 있습니다.

높이(Height): 트리의 루트 노드에서 가장 깊숙한 리프 노드까지의 거리를 가리킵니다. 높이는 가장 긴 경로에 있는 에지의 개수와 동일합니다.

깊이(Depth): 어떤 노드가 루트 노드에서부터 얼마나 깊이 위치해 있는지를 가리킵니다.

부모-자식 관계(Parent-Child Relationship): 트리에서 각 노드는 부모와 하나 이상의 자식을 가질 수 있는데, 이것이 트리의 계층적인 구조를 형성합니다.

 

#include <stdio.h>
#include <stdlib.h>
 
//& 트리 노드 구조체 정의
typedef struct TreeNode
{
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;
 
//& 새로운 노드 생성 함수
TreeNode* createNode(int data)
{
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode != NULL)
    {
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
    }
    return newNode;
}
 
//& 이진 트리에 노드 추가 함수
TreeNode* insertNode(TreeNode* root, int data)
{
    if (root == NULL)
    {
        return createNode(data);
    }
 
    if (data < root->data)
    {
        //& 왼쪽 서브트리에 노드 추가
        root->left = insertNode(root->left, data);
    }
    else if (data > root->data)
    {
        //& 오른쪽 서브트리에 노드 추가
        root->right = insertNode(root->right, data);
    }
 
    return root;
}
 
//& 이진 트리 전위 순회 함수
void preorderTraversal(TreeNode* root)
{
    if (root != NULL)
    {
        //& 현재 노드 데이터 출력
        printf("%d ", root->data);
 
        //& 왼쪽 서브트리 전위 순회
        preorderTraversal(root->left);
 
        //& 오른쪽 서브트리 전위 순회
        preorderTraversal(root->right);
    }
}
 
//& 이진 트리 중위 순회 함수
void inorderTraversal(TreeNode* root)
{
    if (root != NULL)
    {
        //& 왼쪽 서브트리 중위 순회
        inorderTraversal(root->left);
 
        //& 현재 노드 데이터 출력
        printf("%d ", root->data);
 
        //& 오른쪽 서브트리 중위 순회
        inorderTraversal(root->right);
    }
}
 
//& 이진 트리 후위 순회 함수
void postorderTraversal(TreeNode* root)
{
    if (root != NULL)
    {
        //& 왼쪽 서브트리 후위 순회
        postorderTraversal(root->left);
 
        //& 오른쪽 서브트리 후위 순회
        postorderTraversal(root->right);
 
        //& 현재 노드 데이터 출력
        printf("%d ", root->data);
    }
}
 
//& 이진 트리에서 노드 검색 함수
TreeNode* searchNode(TreeNode* root, int key)
{
    if (root == NULL || root->data == key)
    {
        //& 노드를 찾거나 노드가 NULL인 경우 반환
        return root;
    }
 
    if (key < root->data)
    {
        //& 왼쪽 서브트리에서 검색
        return searchNode(root->left, key);
    }
    else
    {
        //& 오른쪽 서브트리에서 검색
        return searchNode(root->right, key);
    }
}
 
int main()
{
    TreeNode* root = NULL;
 
    //& 노드 추가
    root = insertNode(root, 50);
    insertNode(root, 30);
    insertNode(root, 20);
    insertNode(root, 40);
    insertNode(root, 70);
    insertNode(root, 60);
    insertNode(root, 80);
 
    //& 순회 출력
    printf("전위 순회: ");
    preorderTraversal(root);
    printf("\n");
 
    printf("중위 순회: ");
    inorderTraversal(root);
    printf("\n");
 
    printf("후위 순회: ");
    postorderTraversal(root);
    printf("\n");
 
    //& 노드 검색
    int key = 40;
    TreeNode* searchedNode = searchNode(root, key);
    if (searchedNode != NULL)
    {
        printf("노드 %d를 찾았습니다.\n", key);
    }
    else
    {
        printf("노드 %d를 찾을 수 없습니다.\n", key);
    }
 
    return 0;
}// main

위 코드예제는 이진 트리를 구현하고, 전위 순회, 중위 순회, 후위 순회를 수행하는 함수들을 만들었다. 또한, 이진 트리에서 특정 노드를 검색하는 함수도 구현 했다.