[CS] 자료구조 - 이진 트리

이진 트리(binary tree)

 

- 트리 중에서 차수가 2인 트리

- 모든 노드의 차수는 최대 2를 넘지 않음

- 모든 노드는 최대 2개의 서브 트리를 가짐

- 각 서브 트리는 왼쪽 서브 트리와 오른쪽 서브 트리로 구분됨

- 왼쪽 노드와 오른쪽 노드에 '순서'의 의미를 부여함

- 이진 트리의 각 서브 트리는 다시 이진 트리가 됨

 

# 이진 트리의 높이

- N개의 노드를 가진 이진 트리의 높이를 계산으로 구할 수 있음

• 최대 높이 : N으로 노드의 개수와 같음
• 최소 높이 : 모든 내부 노드가 최대 2개의 자식 노드를 갖는 경우로서 [log2 N] +1 이 높이가 됨

---

이진 트리 순회 연산

- 일정한 순서에 따라 트리에 있는 각 노드를 한 번씩 방문하는 것

 

# 전위 순회 (preorder traversal, DLR)

- DLR은 각각 Data, Left, Right 를 뜻함

- 루트 노드 방문 → 왼쪽 서브 트리 방문 → 오른쪽 서브 트리 방문하는 방식

# 중위 순회 (inorder traversal, LDR)

- 왼쪽 서브 트리 방문 → 루트 노드 방문 → 오른쪽 서브 트리 방문하는 방식

# 후위순회 (postorder traversal, LRD)

- 왼쪽 서브 트리 방문 → 오른쪽 서브 트리 방문  →  루트 노드 방문하는 방식

---

# 포화 이진 트리(full binary tree)

- 각 레벨에서 빈자리가 없이 노드를 모두 가지고 있음

- 모든 내부 노드들은 2개의 자식 노드를 가짐

- 깊이가 k인 이진 트리 중에서 노드의 개수가 2^{k}  - 1 개인 이진 트리

- 깊이가 k인 이진 트리가 가질 수 있는 노드의 최대 개수는 2^{k}  - 1 개

- 단말 노드의 개수가 2^{k}  - 1 개

# 완전 이진 트리(complete binary tree)

- 트리의 최대 레벨이 k일 때, 레벨 k-1 까진 포화 이진 트리를 형성하고, 레벨 k에서는 왼쪽부터 오른쪽으로 채워진 트리

- 총 노드의 개수가 2^{k+1} - 1 을 초과하지 않으면서, 포화 이진 트리의 노드 번호에 해당하는 연속적인 번호를 갖는 트리

# 경사 이진 트리(skewed binary tree)

- 한 쪽 방향으로만 가지가 뻗어나간 이진 트리