Tree(트리)는 노드(Node)들이 부모–자식 관계를 이루며 계층 구조를 표현하는 자료구조입니다. 가장 위에 있는 노드를 루트(Root)라고 하고, 자식이 없는 노드를 리프(Leaf)라고 합니다. 각 노드는 0개 이상의 자식을 가질 수 있으며, 전체 구조는 “사이클이 없는 연결 그래프”라고 볼 수 있습니다.
※ 그래프는 노드들이 임의의 방식으로 연결된 일반적인 구조이고, 트리는 그중에서도 “사이클이 없고 루트부터 내려가는 계층형 구조”에 해당하는 특수한 그래프입니다. 그래프에 대한 좀 더 자세한 내용은 Unity 개발자를 위한 Graph(그래프)의 이해를 참고하세요.
일반적인 트리에서는 한 노드가 여러 자식을 가질 수 있지만, 이 노드가 최대 두 개의 자식만 가지도록 제한하면 이진 트리(Binary Tree)가 됩니다. 이진 트리는 이진 탐색 트리(BST), 힙(Heap), PriorityQueue 등을 이해하는 데 필수적인 기반 구조입니다.
이번 글에서는 트리의 개념과 특징을 정리하고, 이진 트리 형태의 Tree를 간단히 구현한 뒤, Unity에서 순회 결과를 확인하는 예제를 통해 동작 방식을 살펴보겠습니다.
1. Tree의 구조
트리는 루트에서 시작하여 간선(엣지)으로 서로 연결된 노드들의 집합입니다. 부모에서 자식으로만 내려가는 방향성이 있으며, 같은 노드를 다시 방문하는 사이클이 존재하지 않는다는 것이 핵심입니다
1.1 트리 기본 용어
● Node (노드)
- 트리를 구성하는 모든 구성 요소
- A, B, C, D, E, F, G 모두 노드
● Root (루트)
- 트리의 가장 최상단 노드
- 그림에서는 A
● Parent (부모) / Child (자식)
- 상하 관계로 연결된 노드
- B는 A의 자식, A는 B의 부모
● Sibling (형제)
- 같은 부모를 가진 노드
- B와 C는 형제
- D와 E도 형제, F는 D, E와 형제가 아님 (부모가 다름)
● Leaf (리프, 말단 노드)
- 자식이 없는 노드
- D, G, F가 Leaf 노드
● Depth (깊이)
- 루트(A)를 깊이 0이라고 할 때 아래로 갈수록 증가
- A = 깊이 0
- B, C = 깊이 1
- D, E, F = 깊이 2
- G = 깊이 3
● Height (높이)
- 특정 노드에서 가장 깊은 리프까지의 거리
- 예: 노드 E의 Height = 1 (자식 G까지)
일반 트리에서는 한 노드가 여러 자식을 가질 수 있지만, 실제로 자료구조와 알고리즘에서 자주 사용하는 형태는 자식이 최대 두 개인 이진 트리(Binary Tree)입니다. 이진 트리는 아래와 같이 여러 형태가 있습니다.
1.2 이진 트리의 대표적인 형태
1) 정 이진 트리 (Full Binary Tree)
모든 노드의 자식 수가 0개(리프) 또는 2개(내부 노드)인 이진 트리입니다.
예1)
|
예2)
|
- 모든 비리프 노드는 반드시 두 자식을 가짐
- 예1) 에서 리프(C, D, E)는 0개의 자식을 가짐
- 마지막 레벨이 모두 차 있어야 한다는 조건은 없음
2) 완전 이진 트리 (Complete Binary Tree)
마지막 레벨을 제외한 모든 레벨이 꽉 차 있으며, 마지막 레벨의 노드는 왼쪽부터 순서대로 채워지는 트리입니다.
A
/ \
B C
/ \ /
D E F <- 마지막 레벨 노드들은 왼쪽부터 순서대로 채워져 있어야 함- 마지막 레벨이 모두 차 있지 않아도 됨
- 비어 있는 자리는 오른쪽에서부터 발생
- 힙(Heap) 구조에서 사용하는 트리 형태
3) 포화 이진 트리 (Perfect Binary Tree)
모든 레벨이 완전히 채워져 있고, 모든 리프가 동일한 깊이에 존재하는 가장 이상적인 형태의 이진 트리입니다.
A
/ \
B C
/ \ / \
D E F G
- 모든 레벨이 빈 틈 없이 채워짐
- 리프 깊이가 모두 동일함
- 노드 수가 정확히 2^(h+1) - 1 형태
이 세 가지 형태는 힙(Heap), 이진 탐색 트리(Binary Search Tree) 등의 자료구조를 이해하는 데 중요한 개념입니다.
힙(Heap)은 완전 이진 트리를 기반으로 하며, 이 구조 덕분에 트리를 배열 하나로 표현하는 것이 가능합니다. 이 특성은 PriorityQueue의 구현에서도 그대로 활용됩니다. 반면 이진 탐색 트리(BST)는 값의 크기 규칙에 집중하여, “왼쪽은 더 작고, 오른쪽은 더 크다” 같은 정렬 조건을 만족시키는 구조입니다.
정리하면, 트리에서는 크게 두 가지 관점을 구분해서 봐야 합니다.
- 노드의 배치 모양(포화, 완전, 정 등 구조적인 모양)
- 노드에 저장된 값의 규칙(BST, Heap, 균형 트리 등 값의 제약 조건)
이번 글에서 구현하는 Tree는 “구조와 순회 방식”을 이해하기 위한 이진 트리 예제입니다. 삽입 시 값 비교(작으면 왼쪽, 크거나 같으면 오른쪽)를 기준으로 노드를 배치하기 때문에, 구조적으로는 사실상 이진 탐색 트리(BST) 입니다. 다만 여기서는 검색 성능을 다루기 위한 구현이 아니라, 트리의 노드 구조와 각 순회 방식이 어떻게 동작하는지를 이해하기 위한 학습용 예제로 보시면 됩니다.
2. Tree가 활용되는 대표적인 사례
트리는 게임 개발과 일반 소프트웨어 개발 전반에서 광범위하게 사용됩니다. 특히 “계층 구조”를 표현해야 하는 경우, 거의 항상 트리 구조가 등장한다고 봐도 무방합니다.
- Unity Transform 계층 구조
Unity의 하이어라키 창에서 GameObject들이 부모–자식 관계로 연결되어 있는 구조 자체가 트리입니다. 루트 오브젝트에서 자식 Transform으로 내려가며 전체 씬 구조를 순회할 수 있습니다. - UI 계층(캔버스, 패널, 버튼 등)
Canvas 아래에 Panel, Panel 아래에 Button, Text 등이 붙는 구조도 트리입니다. 레이아웃 계산, 이벤트 전파(위→아래 또는 아래→위) 모두 트리 순회 개념을 활용합니다. - 파일/폴더 탐색기
폴더 안에 또 다른 폴더와 파일이 들어가는 구조 역시 전형적인 트리입니다. 경로 탐색, 폴더 크기 계산 등에 DFS/BFS 순회가 사용됩니다. - 스킬 트리, 퀘스트 트리
특정 스킬을 습득해야 다음 스킬을 배울 수 있는 구조, 특정 퀘스트를 완료해야 다음 퀘스트가 열리는 구조 등을 트리로 표현하면 관리와 확장이 쉬워집니다. - Behaviour Tree / Decision Tree
게임 AI에서 자주 사용하는 Behaviour Tree, 머신러닝의 Decision Tree 등은 모두 트리 기반 의사 결정 구조입니다. 루트에서 시작해 조건을 따라 내려가면서 어떤 행동을 취할지 결정하게 됩니다. - 이진 탐색 트리(BST) / 힙(Heap)
정렬된 데이터 탐색, 우선순위 큐, 스케줄링 등에서 BST, Heap 같은 트리 기반 자료구조가 사용됩니다.
실제 프로젝트에서는 “트리라는 자료구조를 직접 구현”하는 일보다는, 엔진이 제공하는 계층 구조(Transform, UI, Scene Graph)를 이해하고 잘 활용하는 쪽에 더 가깝습니다. 하지만 트리의 개념을 정확히 알고 있으면, 이러한 시스템의 동작 원리를 훨씬 쉽게 이해할 수 있습니다.
3. Tree가 제공하는 기능(구현 기준)
Tree 자료구조는 사용하는 목적에 따라 기능이 많이 달라질 수 있습니다. 이번 글에서는 이진 트리 구조와 순회를 이해하는 데 필요한 최소한의 기능만 정의해 보겠습니다.
- Root: 트리의 루트 노드에 접근
- Insert: 값을 삽입하여 트리를 확장
- PreOrder / InOrder / PostOrder 순회: 깊이 우선 탐색(DFS) 기반 순회
- LevelOrder 순회: 큐를 사용하는 너비 우선 탐색(BFS) 기반 순회
실제 실무에서는 삭제(Remove), 검색(Search), 균형 조정(Rebalancing) 등 더 많은 기능이 필요할 수 있습니다. 또한 BST, AVL, Red-Black Tree, Heap 등 각 목적에 맞는 다양한 변형들이 존재합니다. 여기서는 트리라는 구조 자체와 기본 순회 방식에 집중하기 위해, Insert와 네 가지 순회만 구현합니다.
4. Tree의 내부 동작 방식
이제 이진 트리 구조가 내부적으로 어떻게 동작하는지, 노드 구조와 삽입, 순회 방식을 중심으로 살펴보겠습니다.
4.1 노드 구조
가장 단순한 이진 트리 노드는 다음과 같은 정보를 가집니다.
- Value: 노드에 저장되는 실제 값
- Left: 왼쪽 자식 노드에 대한 참조
- Right: 오른쪽 자식 노드에 대한 참조
C# 코드로 표현하면 다음과 같은 형태입니다.
public class TreeNode<T>
{
public T Value { get; }
public TreeNode<T> Left;
public TreeNode<T> Right;
public TreeNode(T value)
{
Value = value;
}
}
트리 전체를 관리하는 Tree 클래스는 루트 노드에 대한 참조를 하나 가지고 있고, Insert, Traverse 같은 동작을 담당합니다.
4.2 삽입 규칙(간단한 BST 스타일)
삽입(Insert)을 구현하는 방법은 여러 가지가 있지만, 예제로는 값의 크기를 기준으로 왼쪽/오른쪽을 나누는 간단한 BST 스타일을 사용하겠습니다.
- 삽입하려는 값이 현재 노드 값보다 작으면 왼쪽 서브트리로 내려갑니다.
- 크거나 같으면 오른쪽 서브트리로 내려갑니다.
- 내려간 위치에 비어 있는 자리가 나오면 그 자리에 새 노드를 생성합니다.
예를 들어, 다음 순서로 값을 삽입한다고 가정해 보겠습니다.
8 → 3 → 10 → 1 → 6 → 14 → 4
1) 8 삽입
트리가 비어 있으므로 8이 루트(Root)가 됩니다.
8
2) 3 삽입
3은 8보다 작으므로 왼쪽 서브트리로 내려가고, 왼쪽 자식이 비어 있으므로 그 자리에 3을 추가합니다.
8
/
3
3) 10 삽입
10은 8보다 크므로 오른쪽 서브트리로 내려가고, 오른쪽 자식이 비어 있으므로 그 자리에 10을 추가합니다.
8
/ \
3 10
4) 1 삽입
1은 8보다 작으므로 왼쪽(3)으로 내려가고, 다시 3보다도 작으므로 3의 왼쪽 자식 자리에 추가됩니다.
8
/ \
3 10
/
1
5) 6 삽입
6은 8보다 작으므로 왼쪽(3)으로 내려갑니다. 6은 3보다 크므로 3의 오른쪽 자식 자리에 추가됩니다.
8
/ \
3 10
/ \
1 6
6) 14 삽입
14는 8보다 크므로 오른쪽(10)으로 내려갑니다. 14는 10보다 크므로 10의 오른쪽 자식 자리에 추가됩니다.
8
/ \
3 10
/ \ \
1 6 14
7) 4 삽입 (최종)
4는 8보다 작으므로 왼쪽(3)으로 내려갑니다. 4는 3보다 크므로 오른쪽(6)으로 내려가고, 4는 6보다 작으므로 6의 왼쪽 자식 자리에 추가됩니다.
8
/ \
3 10
/ \ \
1 6 14
/
4
위 과정을 통해 최종적으로 위와 같은 이진 탐색 트리 형태가 만들어집니다. 이후 전위/중위/후위/레벨 순회를 적용하면, 각 순회 방식에 따라 다른 방문 순서를 확인할 수 있습니다.
4.3 순회 방식 (Pre/In/Post/Level)
트리의 모든 노드를 방문하는 방법을 트리 순회(Tree Traversal)라고 합니다. 대표적인 네 가지 방식은 다음과 같습니다.
- 전위 순회 (PreOrder): Root → Left → Right
- 중위 순회 (InOrder): Left → Root → Right
- 후위 순회 (PostOrder): Left → Right → Root
- 레벨 순회 (LevelOrder): 루트에서 시작해 같은 깊이의 노드를 왼쪽부터 오른쪽으로, 레벨 단위로 방문
위 예제 트리에 대해 네 가지 순회를 수행하면 결과는 다음과 같습니다.
4.3.1 전위 순회(PreOrder): 8, 3, 1, 6, 4, 10, 14
- Root → Left → Right
- 상위 노드 먼저 처리해야 하는 작업에 적합
- 트리 구조를 그대로 복사하거나 직렬화(Serialization) 할 때
- 디렉터리 구조 출력, 씬 계층 구조를 상단부터 쭉 나열하는 기능
8(1)
/ \
3(2) 10(6)
/ \ \
1(3) 6(4) 14(7)
/
4(5)
4.3.2 중위 순회(InOrder): 1, 3, 4, 6, 8, 10, 14 (오름차순 정렬 결과)
- Left → Root → Right
- 이진 탐색 트리(BST)의 값을 오름차순으로 정렬하여 얻고 싶을 때
- 아래 그림에서 중위 순회로 데이터를 꺼내면 오름차순으로 정렬된 리스트를 얻을 수 있음 (1, 3, 4, 6, 8, 10, 14)
8(5)
/ \
3(2) 10(6)
/ \ \
1(1) 6(4) 14(7)
/
4(3)
4.3.3 후위 순회(PostOrder): 1, 4, 6, 3, 14, 10, 8
- Left → Right → Root
- 하위 노드를 모두 처리한 뒤에 부모를 처리해야 할 때
- 트리를 삭제할 때(자식을 먼저 free해야 함)
- 수식 트리(Expression Tree)에서 계산 결과를 얻을 때 (후위 표기법(RPN, Reverse Polish Notation) 생성)
8(7)
/ \
3(4) 10(6)
/ \ \
1(1) 6(3) 14(5)
/
4(2)
트리 삭제 예
void DeleteSubTree(Node node)
{
if (node == null) return;
DeleteSubTree(node.Left); // Left
DeleteSubTree(node.Right); // Right
Delete(node); // Root
}- 이 코드는 트리 삭제를 가장 안전하게 수행하는 전형적인 방식입니다.
- 핵심은 부모 노드를 삭제하기 전에, 그 부모가 관리하던 모든 자식 노드를 먼저 삭제한다는 점입니다.
수식 트리
*
/ \
+ 2
/ \
3 5- 후위 순회 결과 : 3 5 + 2 *
- 숫자가 나오면 스택에 넣고, 연산자가 나오면 스택에서 숫자를 꺼내 계산한 뒤 다시 스택에 넣는 방식으로 계산합니다.
4.3.4 레벨 순회(LevelOrder): 8, 3, 10, 1, 6, 14, 4
- 루트부터 같은 깊이의 노드를 왼쪽→오른쪽 순으로 방문 (BFS)
- '높은 레벨에서 낮은 레벨로' 순서가 중요할 때 사용
- 너비 우선 탐색이 필요한 경우
- 최단 거리(간선 수 기준) 계산
- 계층 구조를 위에서부터 출력할 때 (조직도/씬 계층/메뉴 구조 등)
8(1)
/ \
3(2) 10(3)
/ \ \
1(4) 6(5) 14(6)
/
4(7)
4.4 배열 기반 표현 vs 노드 기반 표현
트리는 크게 두 가지 방식으로 표현할 수 있습니다.
- 배열 기반 표현: 완전 이진 트리에서 자주 사용, Heap 구조에 적합
- 노드(포인터) 기반 표현: 일반적인 트리, BST, 다양한 모양의 트리에 적합
배열 기반 이진 트리
완전 이진 트리를 0부터 시작하는 배열에 저장하면, 다음과 같은 규칙을 사용할 수 있습니다.
- 루트: index = 0
- 왼쪽 자식: index = 2 * i + 1
- 오른쪽 자식: index = 2 * i + 2
- 부모: index = (i - 1) / 2
이 방식은 포인터(참조)를 사용하지 않고도 부모/자식 노드를 계산으로 찾을 수 있어, 힙(Heap)처럼 삽입/삭제가 잦고 완전 이진 트리를 유지해야 하는 구조에서 매우 효율적입니다. 대신 트리가 한쪽으로 치우치거나 희소(sparse)해지면 배열의 사용 효율이 떨어집니다.
노드 기반 이진 트리
노드 기반 방식은 이번 글에서 구현하는 Tree처럼 Left/Right 참조를 사용하는 구조입니다. 트리 모양이 자유롭고, 자식 개수가 일정하지 않은 트리(일반 트리)에도 쉽게 확장할 수 있습니다. 대신 노드마다 별도의 객체가 할당되기 때문에, 관리해야 할 참조 수가 늘어나고, GC가 자주 발생할 수 있다는 점에 주의해야 합니다.
실무 관점 요약
- Heap / (Heap 기반 PriorityQueue)처럼 완전 이진 트리를 유지해야 하고, 성능이 중요한 경우 → 배열 기반이 적합
- Unity 계층 구조, 스킬 트리, Behaviour Tree처럼 구조가 유연해야 하는 경우 → 노드 기반이 자연스럽고 구현이 간단
5. C# 기반 Tree 직접 구현 코드
아래는 간단한 이진 트리 Tree 구현 코드입니다. 노드 구조는 TreeNode<T>로 분리하고, Tree는 루트 노드를 관리하면서 Insert 및 네 가지 순회 메서드를 제공합니다. 값 비교를 위해 T : IComparable<T> 제약을 사용합니다.
using System;
using BCL = System.Collections.Generic; // BCL - Base Class Library
namespace Daebak.Common.Collections
{
/// <summary>
/// 이진 트리의 한 노드를 표현하는 클래스.
/// 값과 왼쪽/오른쪽 자식 노드에 대한 참조를 가진다.
/// </summary>
public class TreeNode<T>
{
/// <summary>노드에 저장된 값</summary>
public T Value { get; }
/// <summary>왼쪽 자식 노드</summary>
public TreeNode<T> Left;
/// <summary>오른쪽 자식 노드</summary>
public TreeNode<T> Right;
public TreeNode(T value)
{
Value = value;
}
}
/// <summary>
/// 간단한 이진 트리 구현.
/// 삽입 시 "작으면 왼쪽, 크거나 같으면 오른쪽" 규칙을 사용한다.
/// (사실상 가장 기본적인 형태의 이진 탐색 트리 구조이다)
/// </summary>
public class Tree<T> where T : IComparable<T>
{
/// <summary>트리의 루트 노드</summary>
private TreeNode<T> _root;
/// <summary>외부에서 루트 노드에 읽기 전용으로 접근하기 위한 프로퍼티</summary>
public TreeNode<T> Root => _root;
/// <summary>
/// 값을 트리에 삽입한다.
/// 루트가 없으면 새 루트를 만들고, 있으면 재귀적으로 적절한 위치를 찾아 들어간다.
/// </summary>
public void Insert(T value)
{
// 트리가 비어 있으면 새 루트를 생성
if (_root == null)
{
_root = new TreeNode<T>(value);
return;
}
// 루트에서부터 내려가며 삽입 위치를 찾는다
InsertInternal(_root, value);
}
/// <summary>
/// 현재 노드를 기준으로 왼쪽/오른쪽 서브트리 중 어디에 삽입할지 결정하는 내부 메서드.
/// value가 더 작으면 왼쪽, 크거나 같으면 오른쪽으로 내려간다.
/// </summary>
private void InsertInternal(TreeNode<T> node, T value)
{
int cmp = value.CompareTo(node.Value);
if (cmp < 0)
{
// 더 작은 경우: 왼쪽 서브트리로 이동
if (node.Left == null)
{
// 빈 자리를 찾으면 새 노드를 생성
node.Left = new TreeNode<T>(value);
}
else
{
// 비어 있지 않으면 더 아래로 재귀적으로 내려간다
InsertInternal(node.Left, value);
}
}
else
{
// 크거나 같은 경우: 오른쪽 서브트리로 이동
if (node.Right == null)
{
node.Right = new TreeNode<T>(value);
}
else
{
InsertInternal(node.Right, value);
}
}
}
/// <summary>
/// 전위 순회(PreOrder) : Root -> Left -> Right 순서로 방문한다.
/// visit 콜백을 통해 방문 시 값을 외부로 전달한다.
/// </summary>
public void PreOrder(TreeNode<T> node, Action<T> visit)
{
if (node == null) return;
visit(node.Value);
PreOrder(node.Left, visit);
PreOrder(node.Right, visit);
}
/// <summary>
/// 중위 순회(InOrder) : Left -> Root -> Right 순서로 방문한다.
/// 이진 탐색 트리의 경우, 중위 순회 결과가 정렬된 순서가 된다.
/// </summary>
public void InOrder(TreeNode<T> node, Action<T> visit)
{
if (node == null) return;
InOrder(node.Left, visit);
visit(node.Value);
InOrder(node.Right, visit);
}
/// <summary>
/// 후위 순회(PostOrder) : Left -> Right -> Root 순서로 방문한다.
/// 하위 노드를 모두 처리한 뒤 부모를 처리하는 방식이다.
/// </summary>
public void PostOrder(TreeNode<T> node, Action<T> visit)
{
if (node == null) return;
PostOrder(node.Left, visit);
PostOrder(node.Right, visit);
visit(node.Value);
}
/// <summary>
/// 레벨 순회(LevelOrder) : 큐를 이용한 너비 우선 탐색(BFS).
/// 루트에서 시작해 같은 깊이의 노드들을 차례대로 방문한다.
/// </summary>
public void LevelOrder(TreeNode<T> node, Action<T> visit)
{
if (node == null) return;
// 루트부터 시작해 큐에 넣고 하나씩 꺼내며 자식을 다시 큐에 넣는다
BCL.Queue<TreeNode<T>> q = new();
q.Enqueue(node);
while (q.Count > 0)
{
var cur = q.Dequeue();
visit(cur.Value);
if (cur.Left != null)
{
q.Enqueue(cur.Left);
}
if (cur.Right != null)
{
q.Enqueue(cur.Right);
}
}
}
}
}
이 구현은 교육용 예제이며, 균형 조정이나 삭제 연산 등 복잡한 기능은 포함하지 않습니다. 트리 구조와 네 가지 기본 순회가 어떻게 동작하는지 확인하는 데 초점을 맞추고 있습니다.
6. 유니티(Unity) 환경에서 테스트해 보기
이제 위에서 구현한 Tree를 Unity에서 간단히 테스트해 보겠습니다. 몇 개의 정수를 삽입한 뒤, 전위/중위/후위/레벨 순회 결과를 로그로 출력해 보겠습니다.
using UnityEngine;
using Daebak.Common.Collections;
public class Test_Tree : MonoBehaviour
{
void Start()
{
Tree<int> tree = new();
// 삽입 순서: 8, 3, 10, 1, 6, 14, 4
tree.Insert(8);
tree.Insert(3);
tree.Insert(10);
tree.Insert(1);
tree.Insert(6);
tree.Insert(14);
tree.Insert(4);
Debug.Log("=== Tree Traversal Test ===");
Debug.Log("PreOrder:");
tree.PreOrder(tree.Root, v => Debug.Log(v));
Debug.Log("InOrder:");
tree.InOrder(tree.Root, v => Debug.Log(v));
Debug.Log("PostOrder:");
tree.PostOrder(tree.Root, v => Debug.Log(v));
Debug.Log("LevelOrder:");
tree.LevelOrder(tree.Root, v => Debug.Log(v));
Debug.Log("=== End ===");
}
}
실행 결과
다음 입력 순서로 노드를 삽입했을 때 만들어지는 트리 구조는 아래와 같습니다.
- 8 → 3 → 10 → 1 → 6 → 14 → 4
8
/ \
3 10
/ \ \
1 6 14
/
4
위 트리에 대해 전위 / 중위 / 후위 / 레벨 순회를 수행하면 Unity 콘솔에는 다음과 같은 로그가 출력됩니다.
- 트리 순회 결과는 콘솔창에서는 노드 하나씩 하나씩 해서 길게 출력되지만 편의상 가로로 표시했습니다.
=== Tree Traversal Test ===
PreOrder:
8 3 1 6 4 10 14
InOrder:
1 3 4 6 8 10 14
PostOrder:
1 4 6 3 14 10 8
LevelOrder:
8 3 10 1 6 14 4
=== End ===
이 결과를 통해 다음과 같은 점을 직관적으로 확인할 수 있습니다.
- 같은 트리라도 순회 방식에 따라 방문 순서가 완전히 달라진다.
- 단순한 BST 규칙을 사용하면, 중위 순회(InOrder) 결과가 항상 정렬된 순서가 된다.
- 레벨 순회(LevelOrder)는 힙과 같이 완전 이진 트리를 배열로 표현할 때의 순서와 동일한 구조를 가진다.
마무리
트리는 계층 구조를 표현하는 데 특화된 자료구조로, 게임 엔진의 오브젝트 계층, UI 구조, 스킬 트리, Behaviour Tree, 파일 시스템 등 수많은 곳에서 사용됩니다. 특히 자식이 최대 두 개인 이진 트리는 이진 탐색 트리(BST), 힙(Heap), PriorityQueue의 기반이 되므로, 구조와 순회 방식을 확실히 이해해 두면 이후 자료구조와 알고리즘을 학습할 때 큰 도움이 됩니다.
이번 글에서는 트리의 기본 개념과 용어, 일반 트리에서 이진 트리로의 연결, 포화/완전/정 이진 트리의 개념, 배열 기반 표현과 노드 기반 표현의 차이, 그리고 간단한 C# Tree 구현과 Unity 테스트 예제까지 한 번에 정리해 보았습니다.
※ 다음 글에서는 BST(Binary Search Tree) 구조를 살펴보며, 일반적인 트리 구조에 정렬 규칙이 추가되었을 때 탐색과 삽입이 어떻게 효율적으로 이루어지는지를 중심으로 정리합니다.
'자료 구조' 카테고리의 다른 글
| Unity 개발자를 위한 C# AVL(자기 균형 이진 탐색 트리) 구현 (0) | 2025.12.24 |
|---|---|
| Unity 개발자를 위한 C# BST(Binary Search Tree, 이진 탐색 트리) 구현 (0) | 2025.12.11 |
| Unity 개발자를 위한 Graph(그래프)의 이해 (0) | 2025.12.10 |
| Unity 개발자를 위한 C# PriorityQueue(우선순위 큐) 구현 (0) | 2025.12.10 |
| Unity 개발자를 위한 C# Dictionary(딕셔너리) 구현 (0) | 2025.12.08 |
