트리 ( Tree )

트리 ( Tree )

트리는 계층적 ( Hierarchical ) 구조를 표현하는 자료구조이다.

노드 ( Node ) 와 간선 ( Edge ) 으로 이루어지며 부모 - 자식 관계를 가진다.

대표적인 예시 : 폴더 구조 , 조직도 , 게임 내 스킬 트리

 

 

▼노드 ( Node )

정의 : 트리의 구성 요소 ( 데이터를 담는 단위 )

하나의 노드는 데이터와 자식 노드( 들 )에 대한 참조를 가진다.

 

 

1. 루트 노드 ( Root Node )

• 최상위에 있는 노드 ( 부모가 없다 )
• 트리 전체의 시작점

 

2. 내부 노드 ( Internal Node )

• 부모도 있고 자식도 있는 중간 단계 노드

 

3. 리프 노드 ( Leaf Node )

더 이상 자식이 없는 노드 ( 끝 점 )

 

         A(루트)
       /   \
      B     C
     / \
    D   E

A : 루트 노드

B , C : 내부 노드

D , E : 리프 노드

 

 

▼간선 ( Edge )

정의 : 노드와 노드를 연결하는 선

부모 - 자식 관계를 나타낸다.

항상 방향성이 있으며 ( 위에서 아래로 ) 순환이 없다.

 

 

노드와 간선의 관계

트리는 노드 ( N ) 개수 = 간선 ( E ) 개수 + 1 이라는 특징이 있다.

노드가 5개면 간선은 4개 라는 뜻이다.

모든 노드는 부모와 연결되는 하나의 간선만 가지는데, 루트만 예외이다. ( 부모가 없다 )

 

 

 

문법

▼트리의 노드 정의

class TreeNode
{
    public string Data;
    public List<TreeNode> Children = new List<TreeNode>();

    public TreeNode(string data)
    {
        Data = data;
    }

 

▼자식 추가

public void AddChild(TreeNode child)
    {
        Children.Add(child);
    }
}

 

▼사용 예시

TreeNode root = new TreeNode("루트");
TreeNode child1 = new TreeNode("자식1");
TreeNode child2 = new TreeNode("자식2");

root.AddChild(child1);
root.AddChild(child2);

 

 

 

예시 코드

▼DFS ( 깊이 우선 탐색 )

void Traverse(TreeNode node, int depth = 0)
{
    Console.WriteLine(new string('-', depth) + node.Data);
    foreach (var child in node.Children)
    {
        Traverse(child, depth + 1);
    }
}

// 실행
Traverse(root);

 

▼출력

루트
-자식1
-자식2

 

 

 

주의할 점

사이클 없음 - 트리는 그래프의 특수한 형태 , 순환구조가 있으면 안된다.

루트는 하나 - 루트 없는 트리는 트리가 아니다.

자식은 여러 개 가능하지만 부모는 최대 하나

깊은 트리에서는 재귀 호출 시 스택 오버플로우 주의

 

 

 

정리

트리는 부모 - 자식 관계를 가진 비선형 자료구조로 계층적 구조 표현에 적합하다.