[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)
- 한 쪽 방향으로만 가지가 뻗어나간 이진 트리