트리(Tree)

• 자식 노드와 부모 노드로 이루어진 계층적인 구조
• 무방향 그래프의 일종이자 사이클이 없는 자료구조

특징

• 부모, 자식 계층 구조
• Vertex - 1 = Edge
• 임의의 두 노드 사이 경로는 유일무이하며 반드시 존재

💡[TIP]
문제, 면접에서 트리가 주어지면 루트 노드부터 탐색하는 것이 좋다

용어

• 루트 노드 : 맨 위 노드
• 내부 노드 : 루트 ~ 리프 사이 노드
• 리프 노드 : 자식 노드가 없는 노드

• 깊이 : 루트 노드 ~ 특정 노드 까지 최단 거리
• 높이 : 루트 노드 ~ 리프 노드 까지 가장 긴 거리
• 레벨 : 깊이와 비슷한데 문제마다 다름. 0부터 시작 or 1부터 시작
• 서브트리 : 트리 내의 하위 집합
• 숲 : 트리로 이루어진 집합