[CS] 이진 트리

트리의 정의

자료들 사이의 계층적 관계를 나타내는데 사용하는 자료구조로 부모-자식 관계로 표현된다.

트리는 1개 이상의 노드를 갖는 집합으로 루트 노드가 존재해야 하며 부분트리 또한 트리 구조를 따라야 한다.
 

트리의 용어

• 루트 노드 : 트리의 최상위 노드로써 유일함
• 깊이 : 루트 노드에서 해당 노드까지 도달하는데 사용하는 간선의 개수
• 레벨 : 노드의 깊이 + 1
• 높이 : 루트 노드에서 해당 노드까지 도달하는데 지나간 정점의 개수
• 트리의 높이 : 노드 중 가장 높이가 높은 노드의 높이
• 노드의 차수 : 노드의 자식 수
• 트리의 차수 : 해당 트리 내 모든 노드의 차수 중 최댓값
• 부모 노드 : 부모-자식 관계에서 상위 계층에 있는 노드
• 자식 노드 : 부모-자식 관계에서 하위 계층에 있는 노드
• 형제 노드 : 부모가 동일한 노드
• 내부 노드 : 자식이 있는 노드
• 외부 노드 (단말 노드, 리프 노드) : 자식이 없는 노드

 

이진 트리의 정의

트리의 차수가 2 이하인 트리이다.

자식이 최대 2개이기 때문에 자식을 왼쪽 자식과 오른쪽 자식으로 구분한다.
높이가 N인 이진 트리의 최대 노드 개수는 \( 2^{N} - 1 \) 개이다.
 

이진 트리의 종류

• 정 이진 트리 : 모든 노드의 차수가 0 또는 2인 이진 트리
• 포화 이진 트리 : 정 이진 트리에서 모든 리프 노드의 깊이가 같은 이진 트리  

        높이가 H인 포화 이진 트리의 노드 개수는 \( 2^{H} - 1 \) 개이다.
        반대로 노드가 N개인 포화 이진 트리의 높이는 \( log_{2} (N + 1) \) 이다.
        깊이가 D인 포화 이진 트리의 리프 노드 개수는 \( 2^{D} \) 개이다.

• 완전 이진 트리 : 마지막 레벨은 노드가 왼쪽에 몰려있고 나머지는 포화 이진 트리 구조인 이진 트리
• 사향 이진 트리 : 연결리스트처럼 한 줄로 연결 되어 있는 형태의 이진 트리

 

이진 트리의 순회

출처 : https://galid1.tistory.com/176

• 전위 순회 : 현재 노드 방문 → 왼쪽 자식 탐색 → 오른쪽 자식 탐색 (A - B - D - E - H - C - F - G - I)
• 중위 순회 : 왼쪽 자식 탐색 → 현재 노드 방문 → 오른쪽 자식 탐색 (D - B - E - H - A - F - C - I - G)
• 후위 순회 : 왼쪽 자식 탐색 → 오른쪽 자식 탐색 → 현재 노드 방문 (D - H - E - B - F - I - G - C - A)