[자료구조] 트리(Tree) 시리즈 2: 이진 트리(Binary Tree)란?

이진 트리란?

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조다.

주요 특성:

• 각 노드는 0, 1, 또는 2개의 자식 노드를 가질 수 있다.
• 자식 노드는 일반적으로 왼쪽 자식과 오른쪽 자식으로 구분된다.
• 루트 노드부터 시작하여 계층적 구조를 형성한다.

---

이진 트리의 종류

1. 완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 채워진다.

2. 포화 이진 트리(Full Binary Tree): 모든 내부 노드가 두 개의 자식을 가지며, 모든 리프 노드가 같은 레벨에 있다.

3. 균형 이진 트리(Balanced Binary Tree): 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하다.

4. 편향 이진 트리(Skewed Binary Tree): 한쪽 방향으로만 자식 노드를 가지는 트리다.

---

이진 트리의 표현 방법

배열을 이용한 표현

• 트리를 매우 빈번히 탐색하는경우 주로 사용된다.
• 인덱스 0은 사용하지 않는다.
• 노드 i의 왼쪽 자식: 2i
• 노드 i의 오른쪽 자식: 2i + 1
• 노드 i의 부모: i / 2 (정수 나눗셈)

연결 리스트를 이용한 표현

• 트리를 표현하기엔 연결리스트 기반이 더 유연하다

struct Node {
    int data;
    Node* left;
    Node* right;
    
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

---

이진 트리의 순회 방법

1. 전위 순회(Preorder Traversal): 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리

중위 순회(Inorder Traversal): 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리

3. 후위 순회(Postorder Traversal): 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트

4. 레벨 순회(Level-order Traversal): 루트부터 레벨 단위로 순회

---

이진 트리의 응용

1. 표현식 트리: 수학적 표현식을 트리 형태로 표현
2. 허프만 코딩: 데이터 압축 알고리즘
3. 힙(Heap): 우선순위 큐의 효율적인 구현
4. 구문 분석 트리: 프로그래밍 언어의 파서에서 사용

---

이진 트리의 주요 연산 및 시간 복잡도

• 검색: O(log n) ~ O(n)
• 순회: O(n)

---

참고

[자료구조] 이진 트리 (Binary tree) 알아보기

 

윤성우의 열혈 자료구조 : 네이버 도서

---