이진트리(안혜진 선임님)

[자료구조 목차]

 

이진트리 (Binary Tree)

 

1. 탐색작업의 효율화를 위한 자료구조, 이진트리 개념

• 각 노드가 2개 이하의 자식노드를 가지는 트리형 자료구조로 탐색 작업을 효율적으로 하기 위한 자료구조
• 노드의 차수(degree)가 2 이하로 구성된 트리
• 왼쪽 자식 노드는 부모보다 작고, 오른쪽 자식 노드는 부모보다 큰 트리구조 형태
• (연산유형) 탐색, 삽입, 삭제

 

2. 이진트리의 순회방식 및 유형

1) 이진트리 순회방식

• 전위 순회 : 루트노드를 먼저 탐색하고, 자식노드를 탐색하는 방식
• 중위 순회 : 왼쪽 자식 노드를 탐색하고, 루트노드를 탐색하고,오른쪽 자식 노드를 탐색하는 방식
• 후위 순회 : 왼쪽 자식 노드를 탐색하고, 오른쪽 자식 노드를 탐색하고, 루트 노드를 탐색하는 방식

순회 방식	그림	설명
전위 순회		- 루트노드를 먼저 탐색하고, 자식노드를 탐색하는 방식
중위 순회		- 왼쪽 자식 노드를 탐색하고, 루트노드를 탐색하고,오른쪽 자식 노드를 탐색하는 방식
후위 순회		- 왼쪽 자식 노드를 탐색하고, 오른쪽 자식 노드를 탐색하고, 루트 노드를 탐색하는 방식
레벨 순회		- 루트 노드를 먼저 탐색하고, 그 다음 레벨의 노드를 탐색하는 방식 - 큐를 선언하고 루트노드를 넣어준 다음, 큐에 넣어준 노드를 하나씩 탐색하면서 자식 노드를 큐에 넣고 큐가 비어있을 때까지 반복

 

2) 이진트리 유형

유형	개념도	설명
포화 이진		leaf 노드들이 모두 같은 높이에 존재 총 노드 개수 : 2^k - 1 (k ≥ 1)
완전 이진		leaf 노드들이 트리의 왼쪽부터 차곡차곡 채워진 형태 총 노드 개수 : 2^(k-1) ~ 2^k -1
경사 이진		한쪽 방향으로 노드들이 채워진 형태

• 깊이가 k인 이진트리의 최대 노드의 수 : 2^k - 1
• 이진 트리의 레벨 i에서 최대 노드의 수 : 2^(i - 1)
• n0 = n2 + 1 (n0 : 이진 트리의 터미널 노드, n2 : 차수가 2인 노드 수)