[C#] 트리(Tree)

AsiaticRicecake·2026년 6월 15일

📖 1. 트리

트리는 노드(Node)들이 부모-자식 관계로 연결된 비선형 계층 구조 자료구조

🔖 1-1. 노드(node)

먼저 트리를 이해하기 위해서는 노드의 개념을 알고 있어야 합니다.

노드는 데이터를 담고 있으면서 다른 노드와 연결될 수 있는 객체

class Node
{
    public int Data;   // 값을 저장하는 변수
    public Node Left;  // 다른 Node를 가리키는 변수
    public Node Right; // 다른 Node를 가리키는 변수
}

핵심은 Left, Right 변수입니다.

이 둘은 Node 타입의 변수인데, 여기에 담기는 값이 또 다른 Node 객체의 참조(주소)가 되는 것입니다.

Node root = new Node { Data = 10 };
Node left = new Node { Data = 20 };
Node right = new Node { Data = 30 };

root.Left = left;   // root의 Left 변수에 left 객체의 주소를 저장
root.Right = right;

   10 (root)
     /  \
   20    30
 (Left) (Right)

root.Left.Data로 20에 접근 가능한 것입니다.

🖥️ 1-2. 트리를 쉽게 이해하기 위한 코드

트리를 이해하기 위한 코드를 살펴봅시다

public class TreeNode
{
    public int Value;

    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value)
    {
        Value = value;
    }
}

이 코드를 예시를 들어봅시다

TreeNode root = new TreeNode(10);

root.Left = new TreeNode(20);
root.Right = new TreeNode(30);

이렇게 인스턴스를 생성했다고 가정합니다

Console.WriteLine(root.Value);
Console.WriteLine(root.Left.Value);
Console.WriteLine(root.Right.Value);

10
20
30

콘솔로 실행하면 이런 결과물이 나올 겁니다.

콘솔로 보면 이해가 되지 않아 그림으로 나타낸다면...

    10
   /  \
 20    30

이 상태로 연결된다는 것으로 이해하시면 됩니다.

그럼 여기서 노드를 추가해볼까요?

TreeNode root = new TreeNode(10);

root.Left = new TreeNode(20);
root.Right = new TreeNode(30);

root.Left.Left = new TreeNode(40);
root.Left.Right = new TreeNode(50);

Console.WriteLine(root.Left.Left.Value);
Console.WriteLine(root.Left.Right.Value);

40
50

일반 콘솔로 실행한다면 이런 값이 나오겠지만...

이 부분을 그림으로 나타낸다면

이렇게 노드가 연결되는 것입니다.

📖 2. 트리 순회(Traversal)

자 위에서 트리에 대한 기본 개념을 설명드렸습니다
위의 코드 예시를 보면 노드가 증가할 수록 계속 참조를 하고 있습니다.

Console.WriteLine(root.Value);
Console.WriteLine(root.Left.Value);
Console.WriteLine(root.Right.Value);

근데 여기서 만약 노드가 1000개라면? root.Left.Right.Left.Right....
하루종일 이것만 적을 겁니다

여기서 추가로 배워볼 개념이 트리 순회입니다!

🔖 2-1. 트리 순회 개념

트리에 있는 모든 노드를 한 번씩 방문하는 것

왼쪽 노드와 오른쪽 노드를 모두 방문하기 위해서 재귀 개념을 사용합니다

이 트리를 순회한다고 가정할게요

void Traverse(Node node)
{
    if (node == null) return; // 종료 조건 (자식이 없으면 멈춤)

    Console.WriteLine(node.Data); // 방문
    Traverse(node.Left);          // 왼쪽 -> 재귀로 끝까지 방문
    Traverse(node.Right);         // 오른쪽 -> 재귀로 끝까지 방문
}

왼쪽 노드부터 방문하고 오른쪽 노드를 출력하니까
10 → 20 → 40 → 50 → 30 가 결과로 나올 것입니다.

🔖 2-2. 순회의 3가지 방식

순회의 방식은 대표적으로 3가지가 있습니다.

          10
         /  \
       20    30
      /      / \
    40     50  60

이런 트리구조를 가지고 있다고 가정하고 설명하겠습니다.

2-2-1. ✔️ 전위 순회(Preorder)

전위 순회는 나 -> 왼쪽 -> 오른쪽 순서로 순회하는 방식입니다

static void PreOrder(TreeNode node)
{
    if (node == null)
        return;

    Console.WriteLine(node.Value);

    PreOrder(node.Left);
    PreOrder(node.Right);
}

2-2-2. ✔️ 중위 순회(InOrder)

중위 순회는 왼쪽 -> 나 -> 오른쪽 순서로 순회하는 방식입니다

static void InOrder(TreeNode node)
{
    if (node == null)
        return;

    InOrder(node.Left);

    Console.WriteLine(node.Value);

    InOrder(node.Right);
}

2-2-3. ✔️ 후위 순회(PostOrder)

후위 순회는 왼쪽 -> 오른쪽 -> 나 순서로 순회하는 방식입니다

static void PostOrder(TreeNode node)
{
    if (node == null)
        return;

    PostOrder(node.Left);
    PostOrder(node.Right);

    Console.WriteLine(node.Value);
}

📖 3. 이진 트리(Binary Tree)

이진 트리는 모든 노드가 자식을 최대 2개까지만 가질 수 있는 트리입니다.

class Node
{
    public int Data;
    public Node Left;
    public Node Right;
}

위에서 트리를 설명하기 위해 보여준 예시들이 이진 트리라고 생각하시면 됩니다

🔖 3-1. 이진 트리 종류

✔️ 3-1-1. 정 이진 트리(Full Binary Tree)

모든 노드가 자식이 0개 또는 2개만 가지는 트리입니다. 즉 1개인 노드가 없습니다.

✔️ 3-1-2. 포화 이진 트리(Perfect Binary Tree)

모든 레벨이 완전히 채워진 트리이고 리프 노드들이 모두 같은 깊이에 있습니다.
위의 특징으로 모든 노드가 자식 2개를 가집니다.

⭐ 노드 수 공식(참고)

\text{노드 수} = 2^h - 1

h : 트리의 레벨(Level)
레벨 1 → 1개
레벨 2 → 2개
레벨 3 → 4개
레벨 4 → 8개

각 레벨의 노드 수는 2배씩 증가하여 등비수열 합 공식으로 노드 수가 나옵니다.

1 + 2 + 4 + ... + 2^{h-1} = 2^h - 1

✔️ 3-1-3. 완전 이진 트리(Complete Binary Tree)

마지막 레벨을 제외한 모든 레벨이 채워져 있고, 마지막 레벨은 왼쪽부터 채워지는 트리입니다.

왼쪽부터 채워야 하기 때문에 오른쪽부터 채워진 밑에 트리는 성립할 수 없습니다.

✔️ 3-1-4. 편향 이진 트리(Skewed Binary Tree)

모든 노드가 한쪽 자식만 가져서 한쪽으로 쏠리는 모양이 됩니다.

1                    1
 \                  /
  2                2
   \              /
    3            3
     \          /
      4        4
(오른쪽 편향)    (왼쪽 편향)

사실상 Linked List와 동일한 모양이 됩니다.

📖 4. BST (Binary Search Tree, 이진 탐색 트리)

BST는 이진 트리에 순서 규칙을 추가한 것입니다.

각 노드를 기준으로 숫자 크기에 따라 정렬을 하는 건데 일단 수를 나열해봤을 때 Root가 가장 가운데 값을 가집니다. 왼쪽 자식 Root보다 작게 오른쪽 자식은 Root보다 더 크게 정렬합니다

        50
       /   \
     30      70
    /  \    /  \
   20  40  60  80

보시면 왼쪽은 50보다 전부 작고 오른쪽은 50보다 전부 크죠? 이런 특징을 가진 트리가 BST입니다.

🤔 4-1 왜 이런 식으로 정렬할까요?

가장 큰 이유는 빠르게 탐색(Search)하기 위해서입니다.

예를 들어 80 찾는다고 했을 때 전부 순회해서 찾는 것보다 Root 값을 기준으로 그 값이 크면 오른쪽만 탐색하면 되기 때문에 효율적입니다!

public Node Search(Node node, int target)
{
    if (node == null) return null;          // 못 찾음
    if (node.Data == target) return node;   // 찾음

    if (target < node.Data)
        return Search(node.Left, target);   // 왼쪽으로
    else
        return Search(node.Right, target);  // 오른쪽으로
}

매번 비교해서 절반씩 줄여나가는 게 이진 탐색과 똑같은 원리입니다!

🤔 4-2. 삽입(Insert)은?

앞에서는 탐색을 살펴봤다면 삽입하는 건 어떨까요?

public Node Insert(Node node, int value)
{
    if (node == null) return new Node { Data = value }; // 빈 자리에 삽입

    if (value < node.Data)
        node.Left = Insert(node.Left, value);
    else
        node.Right = Insert(node.Right, value);

    return node;
}

마찬가지로 삽입 위치를 찾는 비교 횟수가 확 줄어들기 때문에 빠릅니다.

🚨 4-3. 최악의 경우(편향 이진 트리)

편향 이진 트리의 경우 한쪽으로만 연결 되어있는 구조라고 앞에서 언급했습니다.

결국 이건 Linked list와 같은 구조로 되어버립니다.
여기서 탐색의 시간복잡도가 O(n)이 됩니다.

이 부분을 해결하기 위해서 AVL, Red-Black Tree 같은 균형 BST가 있습니다.

📊 4-4. 시간 복잡도 정리

자료구조	검색(Search)	삽입(Insert)	삭제(Delete)	특징
배열	O(n)	O(n)	O(n)	중간 삽입/삭제 시 밀기 발생
Linked List	O(n)	O(1)*	O(1)*	위치를 이미 알고 있을 때
BST (평균)	O(log n)	O(log n)	O(log n)	트리가 균형 잡힌 경우
BST (최악)	O(n)	O(n)	O(n)	편향 트리 발생

AsiaticRicecake

이전 포스트

[Unity] MCP 세팅(with Coplay, Claude)

다음 포스트