Tree : 계층형 트리 구조를 시뮬레이션 하는 추상자료형(ADT)으로, 루트값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합이다.

• 하나의 뿌리에서 위로 뻗어나가는 형상이라서 트리라는 이름이 붙었으나, 트리구조 표현에는 나무의 형상과 반대 방향으로 표시한다.
• 족보, 조직도 등을 트리구조라고 할 수 있음
• 재귀로 정의된(Recursively Defined) 자기참조(Self-Referential) 자료구조이다. 흔히 서브트리(subtrees)로 구성된다고 표현한다
• 이러한 재귀적 특성으로 트리에서는 재귀 순회가 좀 더 자연스럽다

트리의 구성과 명칭

그래프 vs 트리

“트리는 순환 구조를 갖지 않는 그래프 입니다.”

그래프와 트리의 차이의 핵심은 순환구조(cyclic)가 아니라는 것이다

이진트리 Binary Trees

노드가 m개 이하의 자식을 갖고있는 트리 : m-ary tree (다항트리, 다진트리)

여기서 m=2이면, 즉 모든 노드의 차수가 2 이하이면 특별히 이진트리(Binary Tree)라고 하는 것

이진트리는 왼쪽, 오른쪽 최대 두개의 자식을 갖는 매우 단순한 형태

다진트리에 비해 훨씬 간결할 뿐 아닌 여러 알고리즘을 구현하는 일도 좀 더 간단하게 처리할 수 있어 보통 트리라 함은 이진트리를 일컫는다.

이진트리의 유형 Types of Binary Trees

1. 정 이진트리( Full Binary Tree ) : 모든 노드가 0개 혹은 2개의 자식 노드를 가짐

   

2. 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다.

   

3. 포화 이진 트리 ( Perfect Binary Tree ) : 모든 노드가 2개의 자식 노드를 갖고 있으며, 모든 리프 노드가 동일한 깊이 혹은 레벨을 갖는다. 문자 그대로, 가장 완벽한 유형의 트리다