후위 순회(post-order)와 중위 순회(in-order)의 결과를 입력으로 받아 이진 트리를 구축해야 하는 경우가 종종 있습니다. 이럴 때 필요한 기능을 담은 클래스를 정의하면 편리합니다. 클래스에는 루트 요소를 설정하는 메서드, 중위 순회를 수행하는 메서드, 후위 순회를 수행하는 메서드를 포함시키고, 인스턴스를 생성하여 실제로 활용할 수 있습니다.
아래에서 전체 과정을 예제와 함께 살펴보겠습니다.
예제 코드
class BinaryTree_struct:
def __init__(self, key=None):
self.key = key
self.left = None
self.right = None
def set_root(self, key):
self.key = key
def inorder_traversal(self):
if self.left is not None:
self.left.inorder_traversal()
print(self.key, end=' ')
if self.right is not None:
self.right.inorder_traversal()
def post_order_traversal(self):
if self.left is not None:
self.left.post_order_traversal()
if self.right is not None:
self.right.post_order_traversal()
print(self.key, end=' ')
def construct_btree(post_ord, in_ord):
if post_ord == [] or in_ord == []:
return None
key = post_ord[-1]
node = BinaryTree_struct(key)
index = in_ord.index(key)
node.left = construct_btree(post_ord[:index], in_ord[:index])
node.right = construct_btree(post_ord[index:-1], in_ord[index + 1:])
return node
post_ord = input('후위 순회 입력 : ').split()
post_ord = [int(x) for x in post_ord]
in_ord = input('중위 순회 입력 : ').split()
in_ord = [int(x) for x in in_ord]
my_instance = construct_btree(post_ord, in_ord)
print('이진 트리가 구축되었습니다...')
print('검증을 진행합니다..')
print('후위 순회 결과... ', end='')
my_instance.post_order_traversal()
print()
print('중위 순회 결과... ', end='')
my_instance.inorder_traversal()
print()실행 결과
후위 순회 입력 : 1 2 3 4 5 중위 순회 입력 : 5 4 3 2 1 이진 트리가 구축되었습니다... 검증을 진행합니다.. 후위 순회 결과... 1 2 3 4 5 중위 순회 결과... 5 4 3 2 1
트리 구축의 핵심 원리
이진 트리를 복원하는 핵심 아이디어는 다음과 같습니다. 후위 순회 결과의 마지막 요소가 곧 트리의 루트라는 점을 이용합니다. 이 루트 값을 중위 순회 결과에서 찾으면, 그 위치를 기준으로 왼쪽 부분은 왼쪽 서브트리, 오른쪽 부분은 오른쪽 서브트리에 해당합니다. 이 과정을 각 서브트리에 대해 재귀적으로 반복하면 전체 트리가 복원됩니다.
코드 설명
필요한 속성을 가진 ‘BinaryTree_struct’ 클래스를 생성합니다.
‘__init__’ 함수는 노드의 키 값을 저장하고, 왼쪽과 오른쪽 자식 노드를 ‘None’으로 초기화합니다.
‘set_root’ 메서드는 이진 트리의 루트 값을 설정하는 역할을 합니다.
‘inorder_traversal’ 메서드는 중위 순회, 즉 왼쪽 → 노드 → 오른쪽 순서로 트리를 탐색합니다.
‘post_order_traversal’ 메서드는 후위 순회, 즉 왼쪽 → 오른쪽 → 노드 순서로 트리를 탐색합니다.
‘construct_btree’ 함수는 후위 순회와 중위 순회 목록을 재귀적으로 분석하여 이진 트리를 구축합니다.
사용자로부터 후위 순회와 중위 순회 시퀀스를 입력받아 정수 리스트로 변환합니다.
‘construct_btree’ 메서드를 호출하여 입력된 순회 결과로부터 이진 트리를 생성합니다.
구축된 트리에 대해 후위 순회와 중위 순회를 다시 수행하여, 원래 입력과 일치하는지 검증합니다.
모든 결과가 콘솔에 출력됩니다.