[자료구조]이진트리 개념, 종류, 순회방법, 활용

1. 이진트리

기본적인 트리 중에서 모든 노드의 자식노드의 개수가 2 이하인 트리를 의미한다.

일반적인 트리에서 사용되는 용어들은 모두 동일하다.

루트(root)노드를 중심으로 두 개의 이진트리로 쪼갤 수 있으며 아래와 같은 구조를 가져야 한다.

 

 

2. 이진트리의 몇 가지 종류

• 포화 이진 트리 (Full Binary Tree) : 단말 노드를 제외한 모든 노드의 차수가 2인 이진 트리
• 완전 이진 트리 (Complete Binary Tree) : 단말 노드들이 트리의 왼쪽부터 채워진 형태의 이진 트리
• 완벽 이진 트리 (Perfect Binary Tree) : 포화 이진 트리 + 모든 단말 노드의 깊이가 같은 트리

 

 

3. 이진 트리 순회 방법

이진트리에 있는 데이터를 탐색하기 위한 순회 방식으로 크게 3개로 나눌 수 있다.

• 전위 순회 (Pre-order Traversal) : 루트 노드를 방문한 후, 왼쪽 서브트리, 오른쪽 서브트리를 순회하는 방식
  위에 있는 이진 트리를 전위 순회한다면 방문 순서는 A-B-C-D-E-F-G가 된다.
• 중위 순회 (In-order Traversal) : 왼쪽 서브트리, 루트노드, 오른쪽 서브트리 순서로 탐색한다.
  마찬가지로 방문순서를 구해보면 C-B-D-A-F-E-G가 된다.
  중위 순회를 거친 탐색은 이진트리에서 정렬된 순서로 데이터를 얻을 수 있다.
• 후위 순회 (Post-order Traversal) : 왼쪽 서브트리, 오른쪽 서브트리, 루트노드 순서로 탐색한다.
  C-D-B-F-G-E-A순서로 위의 이진 트리를 탐색하게 된다.

각각의 방법을 코드로 구현해 보면 트리를 순회하는 함수의 순서에 따라 그 방법이 나뉘게 된다.

 

 

4. 이진 트리 활용

• 이진 탐색 트리 (Binary Search Tree, BST) : 각 노드의 왼쪽에는 해당 노드보다 작은 값이 있고, 오른쪽 서브트리에는 큰 값의 노드들이 위치한 트리
  데이터를 효과적으로 찾아낼 수 있기 때문에 검색속도를 향상시킬 수 있다.
• 힙 (Heap) : 최대힙, 최소힙으로 나뉘며, 최대 힙의 경우 루트노드가 가장 큰 값을 가지게 된다.
  이를 이용하여 우선순위 큐(Priority Queue)를 구현할 수 있다.
• B 트리 : 데이터베이스를 관리하는데 주로 쓰이는 자료구조로 자식노드의 수가 2보다 커질 수 있다.
  이를 이용하여 데이터를 읽거나 쓰는 데에 사용한다.

 

 

트리의 기본적인 개념  ▶  [자료구조]그래프, 트리 개념&예시