[D-9] 이진 트리

📍 이진 트리(binary tree)

✅ 정의

각 노드의 자식 노드(차수)의 개수가 2이하로 구성돼 있는 트리를 말한다.
트리 영역에서 가장 많이 사용되는 형태이다.

 

✅ 종류

편향 이진 트리 : 노드들이 한쪽으로 편향돼 생성된 이진 트리를 말한다.
포화 이진 트리 : 트리의 높이가 모두 일정하며 리프 노드가 꽉찬 이진 트리를 말한다.
완전 이진 트리 : 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리를 말한다.

 

완전 이진 트리 : 일반적으로 코딩 테스트에서 데이터를 트리에 담을 때 사용한다.
편향 이진 트리 : 탐색 속도가 저하되고 공간이 많이 낭비되는 단점이 있다.

 

✅ 순차 표현

이진 트리의 가장 직관적이면서 편리한 트리 자료구조 형태는 바로 '배열'이다.
코딩 테스트에서 그래프의 표현 방식보다 다음 방식으로 데이터를 담는 것이 일반적이다.

 

이진 트리는 다음과 같이 1차원 배열의 형태로 표현할 수 있다.
1차원 배열의 형태로 표현할 때 트리의 노드와 배열의 인덱스 간의 상관 관계는 다음과 같다.

이동 목표 노드	인덱스 연산	제약 조건(N = 노드 개수)
루트 노드	index = 1
부모 노드	index = index / 2	현재 노드가 루트 노드가 아님
왼쪽 자식 노드	index = index * 2	index * 2 <= N
오른쪽 자식 노드	index = index * 2 + 1	index * 2 + 1 <= N

인덱스 연산 방식은 향후 세그먼트 트리(segement tree)나 LCA(lowest common ancestor) 알고리즘에서도 기본이 되는 연산이다.

 

---

✅ 트리 순회하기 (백준 1991번)

이미지 출처 : 백준, 1991 (https://www.acmicpc.net/problem/1991)

전위 순회(preorder traversal) : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
중위 순회(inorder traversal) : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
후위 순회(postorder traversal) : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)