이진 트리 직렬화

이진 트리 직렬화(Serialization of Binary Tree)는 이진 트리의 구조와 노드 값을 문자열 또는 배열과 같은 일차원적인 형태로 변환하여 저장하거나 전송할 수 있도록 하는 과정이다.

개요

이진 트리는 노드가 최대 두 개의 자식을 가지는 트리 구조이며, 다양한 알고리즘과 자료 구조에서 널리 사용된다. 이러한 트리 구조를 파일로 저장하거나 네트워크를 통해 전송하기 위해서는 이진 트리를 직렬화(Serialization)하고, 이를 다시 트리 구조로 복원하는 역직렬화(Deserialization) 과정이 필요하다.

직렬화 방법

이진 트리를 직렬화하는 방법에는 여러 가지가 있으며, 대표적인 방식은 다음과 같다.

전위 순회 기반 직렬화

전위 순회를 이용하여 트리를 순회하며 각 노드의 값을 기록한다. 이때 자식이 없는 노드는 null 또는 특정 구분 기호로 표시한다.

예시:

• 입력 트리:

  1  
 / \  
2   3  
   / \  
  4   5  

• 직렬화 결과 (전위 순회): 1,2,null,null,3,4,null,null,5,null,null

레벨 순회 기반 직렬화

큐(Queue)를 사용하여 트리를 레벨 순서대로 탐색하며 직렬화하는 방법이다. 이진 힙 등의 구조에서 많이 사용된다.

예시:

• 입력 트리:

  1  
 / \  
2   3  
   / \  
  4   5  

• 직렬화 결과 (레벨 순회): 1,2,3,null,null,4,5

직렬화의 활용

• 네트워크를 통해 트리 자료를 전송할 때 사용
• 디스크에 저장하여 나중에 재사용하거나 로드할 때 사용
• 트리 구조 기반 알고리즘의 테스트 및 검증을 위한 데이터 표현

구현 고려 사항

• null 노드의 표현 방식: 다양한 직렬화 방식에서는 null 값을 명시적으로 기록해야 정확한 복원이 가능하다.
• 순회 순서의 선택: 전위, 중위, 후위, 레벨 순회 등 선택에 따라 직렬화 결과와 복원 방법이 달라진다.
• 구분자와 포맷: 직렬화된 문자열에서 노드 구분을 위한 구분자(예: 쉼표, 공백 등)를 일관되게 사용하는 것이 중요하다.

같이 보기

• 이진 트리
• 트리 (자료 구조)
• 순회 (트리)
• 큐 (자료 구조)
• 역직렬화

참고 문헌

• LeetCode. “Serialize and Deserialize Binary Tree.” [1]
• Thomas H. Cormen 외, 『Introduction to Algorithms』, MIT Press, 2009.