이진 트리 (Binary Tree) - 소개

* 책 열혈강의 + 인터넷

트리 Tree

비선형 자료구조

마치 조직도같은 모양!

용어

Node 노드 : 데이터를 저장하는 각각의 요소

Root Node 루트 노드 : 트리 구조의 최상위 노드

Terminal Node 단말 노드 : 아래로 다른 노드가 연결되어 있지 않은 노드

Internal Node 내부 노드 : 단말 노드를 제외한 노드

Edge 간선 : 노드를 잇는 선

관계

Parent 부모 : 자식 노드를 가진다

Child 자식 : 부모 노드를 가진다

Sibling 형제 : 같은 부모로부터 형제 노드를 가진다

(위 그림에서는 같은 색깔끼리 관계를 형성)

Level 레벨 : 트리의 가장 위에서부터 (0) 층별로 매겨진 숫자

Height/Depth 높이/깊이 : 트리의 최고 레벨. 위 그림에서는 2

Degree 차수 : 각 노드에서 뻗어나온 가지의 수

트리의 Degree? 노드들의 차수 중 가장 큰 수.

이진 트리 Binary Tree

조건

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

* 나누어진 두 서브 트리도 모두 이진 트리

재귀적인 조건임을 알 수 있다.

위 그림에서 가장 오른쪽은 이진 트리가 아니다. (두 개의 서브 트리로 나누어지지 않는다)

왼쪽 두 트리의 경우 루트 노드에서부터 노드 하나와 공집합 노드 하나로 나누어진다. 

노드가 존재할 수 있는 곳에 존재하지 않을 때 (보이지 않는)공집합 노드가 존재한다.

단말 노드의 경우에도 하위에 공집합이 존재하는 것으로 간주하여 단말 노드 자체도 이진 트리로 인정한다.

포화 이진 트리Full Binary Tree & 완전 이진 트리 Complete Binary Tree

포화 이진 트리

* 모든 레벹이 가득 차 있다.

완전 이진 트리

* 빈틈 없이 노드가 채워져 있다.

노드는 위에서 아래로, 왼쪽에서 오른쪽으로 채워진다.

포화 이진 트리는 완전 이진 트리이다.

완전 이진 트리는 포화 이진 트리 일수도, 아닐수도 있다.

순회 Traversal

▲ 전위 순회 Preorder Traversal 루트 노드를 먼저 방문

▲ 중위 순회 Inorder Traversal 루트 노드를 중간에 방문

▲ 후위 순회 Postorder Traversal 루트 노드를 마지막에 방문