📍 이진 트리(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 // (왼쪽 자식) (오른쪽 자식) (루트)
