트리는 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져있고, 트리 구조로 배열된 계층적 데이터의 집합이다.

구성

루트노드 : 가장 위에 있는 노드

내부노드 : 루트노드와 내부노드 사이에 있는 노드로 리프노드를 제외한 노드

리프노드 : 자식이 없는 노드

특징

• 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조
• 트리내에 또 다른 트리가 있는 재귀적 자료구조
• 단순 순환(Loop)을 갖지 않고, 연결된 무방향 그래프 구조
• 노드 간에 부모 자식 관계를 갖고 있는 계층형 자료구조이며 모든 자식 노드는 하나의 부모 노드만 가진다.

트리의 높이와 레벨

깊이 : 루트노드부터 특정노드까지 최단 거리로 갔을 때의 거리

높이 : 루트노드부터 리프노드까지 거리중 가장 긴 거리

레벨 : 주어지는 문제마다 다르지만 보통 깊이와 같은 의미

서브트리 : 트리 내의 하위 집합

자료구조-트리(Tree)

이진 트리

자식의 노드 수가 두개 이하인 트리를 의미