트리(Tree)의 개요

트리 관련 용어

• 노드(node) : 트리의 구성요소에 해당하는 요소
• 간선(edge) : 노드와 노드를 연결하는 연결선
• 루트 노드(root node) : 트리 구조에서 최상위에 존재하는 노드
• 단말 노드(terminal node) : 아래로 또는 다른 노드가 연결되어 있지 않은 노드
• 내부 노드(internal node) : 단말 노드를 제외한 모든 노드

- 서브 트리

서브 트리 역시 서브트리로 이뤼져 있으며, 그 서브 트리 역시 또 다른 서브트리로 이뤼져 있다. 그렇듯 트리는 그 구조가 재귀적이다!

- 이진 트리

루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.

나뉘어진 두 서브트리도 모두 트리이어야 한다.

- 이진 트리와 공집합 노드

공집합도 이진 트리에서는 노드로 간주한다.

하나의 노드에 두 개의 노드가 달리는 형태의 트리는 모두 이 진트리이다.

- 레벨과 높이, 그리고 포화, 완전 이진트리

높이 = 최대 레벨과 값이 같다.

완전 이진 트리는 위에서 아래로 왼쪽에서 오른쪽으로 채워진 트리를 의미한다.

따라서 포화 이진 트리는 동시에 완전 이진 트리이지만 그 역은 성립하지 않는다.