MENU
  1. ホーム
  2. C 언어
  3. C 언어로 트리의 높이와 깊이 쉽게 계산하기

C 언어로 트리의 높이와 깊이 쉽게 계산하기

C 언어

트리 자료구조에서 높이와 깊이는 중요한 기본 개념으로, 데이터 조직화와 알고리즘 설계에 핵심적인 역할을 합니다. C 언어를 활용해 트리의 높이와 깊이를 계산하는 방법을 배우면 복잡한 문제를 효율적으로 해결할 수 있습니다. 본 기사에서는 트리의 기본 구조부터 높이와 깊이의 정의, 이를 C 언어로 구현하는 구체적인 예제와 응용까지 다룹니다. 이를 통해 트리 자료구조의 이해를 심화하고 실제 프로그래밍에 활용할 수 있는 기술을 익힐 수 있습니다.

목차

트리 자료구조란?


트리(Tree)는 계층적 데이터 구조를 표현하기 위한 자료구조로, 루트(Root) 노드에서 시작해 각 노드가 자식 노드로 이어지는 방식으로 구성됩니다.

트리의 구성 요소


트리는 다음과 같은 구성 요소로 이루어집니다:

  • 루트(Root): 트리의 최상단에 위치한 노드로, 부모가 없는 유일한 노드입니다.
  • 노드(Node): 데이터와 포인터를 포함하는 기본 구성 요소입니다.
  • 자식(Child): 특정 노드의 하위에 연결된 노드들입니다.
  • 부모(Parent): 특정 노드의 상위에 위치한 노드입니다.
  • 서브트리(Subtree): 특정 노드를 루트로 하는 하위 트리입니다.

트리의 특징

  • 노드 간에는 계층적 관계가 존재합니다.
  • 순환(Cycle)이 없습니다.
  • 트리의 높이는 루트에서 가장 멀리 있는 노드까지의 거리입니다.
  • 이진 트리(Binary Tree), 균형 트리(Balanced Tree) 등 다양한 종류가 있습니다.

트리는 데이터 조직화, 탐색, 정렬, 네트워크 라우팅, 표현식 계산 등 다양한 프로그래밍 문제에서 중요한 역할을 합니다.

높이와 깊이의 차이

높이(Height)란?


트리에서 높이는 특정 노드에서 가장 멀리 있는 리프(Leaf) 노드까지의 경로 길이를 의미합니다.

  • 루트 높이: 트리 전체의 높이는 루트 노드에서 가장 멀리 있는 리프 노드까지의 거리입니다.
  • 높이 계산 기준: 노드의 높이는 자식 노드의 높이 중 최대값에 1을 더한 값입니다.

깊이(Depth)란?


깊이는 특정 노드가 루트로부터 얼마나 떨어져 있는지를 나타내는 경로 길이입니다.

  • 루트 깊이: 항상 0입니다.
  • 깊이 계산 기준: 특정 노드까지의 부모-자식 경로를 따라간 거리를 계산합니다.

차이를 한눈에 보기

  • 높이: 특정 노드에서 리프까지의 최대 거리.
  • 깊이: 루트에서 특정 노드까지의 거리.

예시로 이해하기


아래 트리를 예로 들어보겠습니다:

         A
        / \
       B   C
      /   / \
     D   E   F
  • A의 높이: 2 (A → B → D 또는 A → C → E)
  • B의 깊이: 1 (A → B)
  • D의 높이: 0 (리프 노드이므로)
  • D의 깊이: 2 (A → B → D)

높이와 깊이의 개념을 명확히 이해하면 트리 구조의 분석과 알고리즘 구현이 훨씬 쉬워집니다.

높이와 깊이를 계산하는 방법

트리 높이 계산


트리의 높이는 루트 노드에서 가장 멀리 있는 리프 노드까지의 최대 경로 길이를 계산하는 것으로, 다음과 같은 단계로 수행됩니다:

  1. 재귀적으로 각 자식 노드의 높이를 계산합니다.
  2. 자식 노드 높이 중 최대값에 1을 더해 부모 노드의 높이를 결정합니다.

높이 계산 의사 코드

Function TreeHeight(node):
    If node is NULL:
        Return -1
    LeftHeight = TreeHeight(node.left)
    RightHeight = TreeHeight(node.right)
    Return Max(LeftHeight, RightHeight) + 1

트리 깊이 계산


트리의 깊이는 루트에서 특정 노드까지의 경로 길이를 계산하는 것으로, 다음 과정을 따릅니다:

  1. 루트 노드에서 시작해 자식 노드를 따라 내려가며 거리(깊이)를 증가시킵니다.
  2. 특정 노드에 도달하면 해당 깊이를 반환합니다.

깊이 계산 의사 코드

Function TreeDepth(node, target, currentDepth):
    If node is NULL:
        Return -1
    If node == target:
        Return currentDepth
    LeftDepth = TreeDepth(node.left, target, currentDepth + 1)
    If LeftDepth != -1:
        Return LeftDepth
    Return TreeDepth(node.right, target, currentDepth + 1)

구현 시 고려 사항

  • 기저 사례: 노드가 NULL인 경우, 깊이와 높이는 -1로 정의합니다.
  • 트리의 균형 여부: 균형이 잘 잡힌 트리는 높이가 낮아 성능이 더 좋습니다.
  • 반복 vs 재귀: 간단한 트리에서는 재귀가 적합하지만, 깊은 트리에서는 스택 오버플로를 피하기 위해 반복 접근법을 고려할 수 있습니다.

높이와 깊이를 계산하는 알고리즘을 이해하면 트리 구조를 다루는 다양한 문제를 효율적으로 해결할 수 있습니다.

재귀를 활용한 계산

트리 높이를 계산하는 재귀 함수


트리 높이 계산은 재귀를 활용해 간단히 구현할 수 있습니다. 각 노드의 왼쪽 및 오른쪽 자식의 높이를 계산한 뒤, 그 중 최대값에 1을 더하면 됩니다.

트리 높이 계산 코드

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

// 트리 노드 정의
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// 높이 계산 함수
int calculateHeight(Node* root) {
    if (root == NULL) {
        return -1; // NULL 노드는 높이 -1
    }
    int leftHeight = calculateHeight(root->left);
    int rightHeight = calculateHeight(root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// 새 노드 생성 함수
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

트리 깊이를 계산하는 재귀 함수


특정 노드의 깊이는 루트에서 해당 노드까지의 경로 길이를 계산합니다. 각 자식 노드를 탐색하며 깊이를 증가시켜가며 계산합니다.

트리 깊이 계산 코드

int calculateDepth(Node* root, Node* target, int depth) {
    if (root == NULL) {
        return -1; // 타겟 노드를 찾을 수 없을 때
    }
    if (root == target) {
        return depth; // 타겟 노드에 도달했을 때
    }
    int leftDepth = calculateDepth(root->left, target, depth + 1);
    if (leftDepth != -1) {
        return leftDepth;
    }
    return calculateDepth(root->right, target, depth + 1);
}

테스트 코드

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("트리의 높이: %d\n", calculateHeight(root));

    // 깊이 계산
    printf("노드 5의 깊이: %d\n", calculateDepth(root, root->left->right, 0));

    return 0;
}

코드 설명

  1. 높이 계산: 자식 노드의 높이를 재귀적으로 계산한 후, 최대값에 1을 더합니다.
  2. 깊이 계산: 루트에서 타겟 노드까지 경로를 따라가며 깊이를 증가시킵니다.
  3. 테스트 코드: 간단한 트리를 생성하고 높이와 깊이를 출력합니다.

재귀를 활용하면 트리의 높이와 깊이를 간단하고 직관적으로 구현할 수 있습니다.

예제와 코드 분석

예제 트리


아래의 트리 구조를 기반으로 높이와 깊이를 계산합니다:

         1
        / \
       2   3
      / \
     4   5

높이 계산 분석


코드 실행 흐름

  1. 루트 노드(1)에서 시작하여 왼쪽 자식(2)과 오른쪽 자식(3)의 높이를 재귀적으로 계산합니다.
  2. 왼쪽 서브트리(2):
  • 4와 5의 높이는 각각 0 (리프 노드).
  • 2의 높이는 Max(0, 0) + 1 = 1.
  1. 오른쪽 서브트리(3):
  • 리프 노드이므로 높이는 0.
  1. 루트 노드(1):
  • Max(1, 0) + 1 = 2.

출력 결과

트리의 높이: 2

깊이 계산 분석


코드 실행 흐름

  1. 루트에서 시작하여 타겟 노드(예: 5)를 탐색합니다.
  2. 루트(1)의 왼쪽 자식(2)으로 이동.
  3. 자식 노드(2)에서 오른쪽 자식(5)으로 이동.
  4. 타겟 노드(5)에 도달한 시점에서 깊이는 2.

출력 결과

노드 5의 깊이: 2

코드의 결과


테스트 코드를 실행하면 트리의 높이와 깊이가 정확히 계산되는 것을 확인할 수 있습니다:

전체 코드 실행 결과

트리의 높이: 2  
노드 5의 깊이: 2

추가 설명: 코드의 효율성

  • 높이 계산: 각 노드를 한 번씩 방문하므로 시간 복잡도는 (O(n))입니다.
  • 깊이 계산: 최악의 경우 트리 전체를 탐색하므로 시간 복잡도는 (O(n))입니다.
  • 메모리 사용: 재귀 호출로 인해 깊이 만큼의 스택 공간이 사용됩니다.

확장 가능성

  • 다양한 트리 구조(예: 균형 이진 트리, 비균형 트리)에서 동일한 코드를 사용할 수 있습니다.
  • 이 코드를 확장해 트리의 최대값, 최소값, 노드 수 등을 추가로 계산할 수 있습니다.

이 예제와 분석을 통해 트리의 높이와 깊이 계산 로직을 명확히 이해하고 실제 프로그래밍에 활용할 수 있습니다.

응용: 다양한 트리 구조에 적용하기

균형 이진 트리에서의 높이와 깊이


균형 이진 트리는 모든 리프 노드가 동일하거나 한 단계 차이의 높이를 가집니다. 이 경우, 높이와 깊이를 계산하는 알고리즘은 효율적으로 작동합니다.

예제

         1
        / \
       2   3
      / \   \
     4   5   6
  • 루트 높이: 2 (1 → 2 → 4 또는 1 → 3 → 6).
  • 노드 5의 깊이: 2 (1 → 2 → 5).

비균형 트리에서의 높이와 깊이


비균형 트리는 일부 가지가 더 긴 트리로, 높이가 클수록 효율성이 저하될 수 있습니다. 재귀 호출이 더 깊어지므로 스택 오버플로를 방지하기 위해 반복적 접근법을 고려할 수 있습니다.

예제

         1
        /
       2
      /
     3
    /
   4
  • 루트 높이: 3 (1 → 2 → 3 → 4).
  • 노드 4의 깊이: 3 (1 → 2 → 3 → 4).

다항 트리에서의 응용


다항 트리는 각 노드가 두 개 이상의 자식을 가질 수 있습니다. 높이와 깊이 계산 알고리즘은 이 구조에도 적용 가능하며, 각 자식의 높이를 반복적으로 계산합니다.

예제

         1
       / | \
      2  3  4
     / \
    5   6
  • 루트 높이: 2 (1 → 2 → 5 또는 1 → 2 → 6).
  • 노드 4의 깊이: 1 (1 → 4).

실제 응용 사례

  1. 파일 시스템
  • 디렉토리 구조에서 최상위 디렉토리의 깊이를 구하거나, 특정 파일의 깊이를 계산하는 데 사용할 수 있습니다.
  1. 네트워크 라우팅
  • 트리 형태의 네트워크에서 최장 경로(높이)나 특정 노드까지의 경로(깊이)를 계산합니다.
  1. 인공지능 게임 탐색
  • 미니맥스 알고리즘에서 트리 깊이를 기반으로 최적의 움직임을 결정합니다.

코드 확장

  • 반복적 방법 적용: 재귀 호출 대신 큐를 사용해 높이와 깊이를 계산하면 메모리 효율성이 개선됩니다.
  • 다중 트리 지원: 자식 리스트를 활용한 일반 트리 구조에서도 동일한 알고리즘을 적용할 수 있습니다.

트리의 높이와 깊이를 다양한 구조와 상황에 맞게 계산하면 더 넓은 범위의 문제를 해결할 수 있습니다. 이를 통해 효율적이고 유연한 알고리즘 설계가 가능합니다.

요약

트리 자료구조에서 높이와 깊이는 데이터를 효율적으로 분석하고 구조를 이해하는 데 중요한 요소입니다. 높이는 특정 노드에서 리프 노드까지의 최대 거리, 깊이는 루트에서 특정 노드까지의 경로 길이를 의미합니다.

C 언어를 활용해 재귀적으로 높이와 깊이를 계산하는 방법을 학습했으며, 균형 트리, 비균형 트리, 다항 트리 등 다양한 트리 구조에 이 알고리즘을 적용하는 사례를 살펴보았습니다.

이를 통해 파일 시스템, 네트워크 라우팅, AI 탐색과 같은 실제 문제에 트리의 높이와 깊이를 효율적으로 계산하고 적용하는 방법을 익힐 수 있습니다.

C 언어
C언어 깊이 높이 트리 구조
목차