Tree(트리)

Tree(트리)

Tree(트리)는 Hierarchical Relationship(계층적 관계)를 표현하는 자료구조입니다.

 

트리를 구성하는 구성 요소들은 다음과 같습니다.

- Node(노드) : 트리를 구성하는 각각의 요소

- Edge(간선) : 노드와 노드를 연결하는 선

- Root Node(루트 노드) : 트리의 최상위 노드

- Terminal Node( = leaf Node, 단말 노드) : 트리의 최하위 노드

- Internal Node(내부 노드, 비단말 노드) : 단말 노드를 제외한 모든 노드(루트 노드 포함)

- Sub-Tree(서브 트리) : 루트 노드를 제거한 후 남아있는 부분 트리

- Degree of Node(노드의 차수) : 특정 노드에 연결된 서브 트리의 수

- Level(레벨) : 루트 노드와 특정 노드까지의 거리(루트 노드의 레벨 = 1)

- Height(높이) : 트리의 최고 레벨

 

Binary Tree(이진 트리)

Binary Tree(이진트리)는 모든 노드의 차수가 최대 2인 트리입니다.

즉, 이진 트리의 모든 서브 트리는 이진 트리입니다.

이때, 공집합도 이진 트리에 속합니다. 

이진 트리의 단말 노드들은 자식 노드를 가지지 않기 때문입니다.

 

Full Binary Tree(포화 이진 트리)

Full Binary Tree(포화 이진 트리)는 단말 노드를 제외한 모든 노드의 차수가 2인 트리입니다.

포화 이진 트리에서 단말 노드의 수는 (단말 노드를 제외한 모든 노드의 수 + 1)와 같습니다.

 

Complete Binary Tree(완전 이진 트리)

Complete Binary Tree(완전 이진 트리)는 루트 노드부터 단말 노드 방향으로, 그리고 왼쪽에서 오른쪽 방향으로 빈 노드가 없이 순서대로 모두 존재하는 이진 트리입니다.

모든 포화 이진 트리는 완전 이진 트리가 될 수 있지만, 모든 완전 이진 트리는 포화 이진 트리가 될 수 없습니다.

포화 이진 트리가 완전 이진 트리의 부분 집합인 셈입니다.