트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조이다. 이 트리라는 자료구조는 표현에 집중한다. 무엇인가를 저장하고 꺼내야 한다는 사고에서 벗어나 트리라는 자료구조를 바라보자.

트리를 구성하고 있는 구성요소들(용어)

• Node(노드) : 트리를 구성하고 있는 기본 원소
  • 루트 노드 (root node / root) : 트리에서 부모가 없는 최상위 노드, 트리의 시작점
  • 부모 노드 (parent node) : 루트 노드 방향으로 직접 연결된 노드
  • 자식 노드 (child node) : 루트 노드 반대방향으로 직접 연결된 노드
  • 형제 노드 (siblings node) : 같은 부모 노드를 갖는 노드들
  • 리프 노드 (leaf node / leaf) : 루트 노드를 제외한 차수가 1인 정점을 뜻함. 쉽게 말해 자식이 없는 노드, 단말 노드라 부르기도 함.
• Path (경로) : 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서
• Length(길이) : 출발 노드에서 도착 노드까지 거치는 간선 갯수
• Depth(깊이) : 루트의 경로의 길이
• Level(레벨) : 루트 노드부터 노드까지 연결된 간선 수의 합
• Height(높이) : 가장 긴 루트 경로의 길이
• Degree(차수) : 각 노드의 자식의 개수
• Degree of tree(트리의 차수) : 트리의 최대 차수 = $max(deg1, deg2,..., deg_n)$
• Size(크기) : 노드의 개수
• Width(너비) : 가장 많은 노드를 갖고 있는 레벨의 크기
• Internal vertex(내부 정점) : 차수가 2 인상인 정점을 뜻함.
• Forest(포레스트) : 서로 독립인 트리들의 모임
• Directed Tree(방향 트리) : 방향을 무시하고 생각했을 때 트리인 유향 그래프는 방향 트리이다. 자료구조의 트리는 방향 트리의 일종이다.
• Edge(간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다.

Binary Tree (이진 트리)

부모 노드 밑의 자식 노드 개수를 최대 2개로 제한하는, 트리의 가장 간단한 형태이며 왼쪽 자식과 오른쪽 자식으로 구분 지을 수 있다.

<aside> 💡 대부분 숫자 같은 선형적인 데이터값을 가진 경우이다.

</aside>