트리의 미러(mirror) 복사본을 생성하고, 너비 우선 탐색(BFS, Breadth First Search) 방식으로 그 결과를 화면에 출력해야 하는 상황을 가정해 보겠습니다. 이를 구현하려면 루트 노드 설정, 왼쪽·오른쪽 자식 삽입, 특정 요소 검색, 후위 순회 등의 기능을 갖춘 이진 트리 클래스를 먼저 정의해야 합니다. 클래스의 인스턴스를 생성하면 해당 인스턴스를 통해 정의된 메서드들을 자유롭게 호출할 수 있습니다.
아래는 이를 실제로 구현한 예제입니다.
예제
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 insert_to_left(self, new_node):
self.left = new_node
def insert_to_right(self, new_node):
self.right = new_node
def search_elem(self, key):
if self.key == key:
return self
if self.left is not None:
temp = self.left.search_elem(key)
if temp is not None:
return temp
if self.right is not None:
temp = self.right.search_elem(key)
return temp
return None
def copy_mirror(self):
mirror = BinaryTree_struct(self.key)
if self.right is not None:
mirror.left = self.right.copy_mirror()
if self.left is not None:
mirror.right = self.left.copy_mirror()
return mirror
def bfs(self):
queue = [self]
while queue != []:
popped = queue.pop(0)
if popped.left is not None:
queue.append(popped.left)
if popped.right is not None:
queue.append(popped.right)
print(popped.key, end=' ')
my_instance = None
print('Menu (this assumes no duplicate keys)')
print('insert <data> at root')
print('insert <data> left of <data>')
print('insert <data> right of <data>')
print('mirror')
print('quit')
while True:
my_input = input('What operation would you do ? ').split()
operation = my_input[0].strip().lower()
if operation == 'insert':
data = int(my_input[1])
new_node = BinaryTree_struct(data)
suboperation = my_input[2].strip().lower()
if suboperation == 'at':
my_instance = new_node
else:
position = my_input[4].strip().lower()
key = int(position)
ref_node = None
if my_instance is not None:
ref_node = my_instance.search_elem(key)
if ref_node is None:
print('No such key exists..')
continue
if suboperation == 'left':
ref_node.insert_to_left(new_node)
elif suboperation == 'right':
ref_node.insert_to_right(new_node)
elif operation == 'mirror':
if my_instance is not None:
print('Creating a mirror copy...')
mirror = my_instance.copy_mirror()
print('The breadth first search traversal of original tree is : ')
my_instance.bfs()
print()
print('The breadth first traversal of mirror is : ')
mirror.bfs()
print()
elif operation == 'quit':
break실행 결과
Menu (this assumes no duplicate keys) insert <data> at root insert <data> left of <data> insert <data> right of <data> mirror quit What operation would you do ? insert 6 at root What operation would you do ? insert 9 left of 6 What operation would you do ? insert 4 right of 6 What operation would you do ? mirror Creating a mirror copy... The breadth first search traversal of original tree is : 6 9 4 The breadth first traversal of mirror is : 6 4 9 What operation would you do ?quit Use quit() or Ctrl-D (i.e. EOF) to exit
코드 설명
'BinaryTree_struct'라는 이름의 클래스가 필요한 속성들과 함께 정의됩니다.
__init__ 함수는 새 노드가 생성될 때 왼쪽과 오른쪽 자식 노드를 None으로 초기화하는 역할을 합니다.
set_root 메서드는 특정 값을 루트 노드로 지정할 때 사용됩니다.
insert_to_left 메서드는 트리의 왼쪽 자식 노드에 새 요소를 추가합니다.
insert_to_right 메서드는 트리의 오른쪽 자식 노드에 새 요소를 추가합니다.
bfs 메서드는 큐(queue)를 활용해 트리 전체를 너비 우선 방식으로 순회하며 각 노드의 값을 출력합니다.
search_elem 메서드는 주어진 키와 일치하는 노드를 재귀적으로 검색합니다.
copy_mirror 메서드는 원본 이진 트리의 좌우를 반전시킨 미러 복사본을 재귀적으로 생성합니다.
클래스 인스턴스가 생성되며, 초기에는 None으로 할당됩니다.
사용자로부터 수행할 연산을 입력받습니다.
사용자의 선택에 따라 해당 연산이 실행됩니다.
연산 결과가 콘솔에 출력됩니다.
핵심 동작 원리
copy_mirror 메서드는 재귀적으로 동작합니다. 현재 노드의 키 값으로 새 노드를 만든 뒤, 원본 트리의 오른쪽 서브트리를 미러의 왼쪽에, 원본의 왼쪽 서브트리를 미러의 오른쪽에 배치함으로써 좌우가 반전된 트리를 얻습니다. 실행 결과에서도 원본 트리의 BFS 순회가 '6 9 4'인 반면, 미러 복사본은 '6 4 9'로 출력되어 좌우가 뒤바뀐 것을 확인할 수 있습니다.
bfs 메서드는 리스트를 큐처럼 활용합니다. 맨 앞의 노드를 꺼내(pop) 처리하고, 해당 노드의 자식들을 큐 뒤에 순서대로 추가하는 방식으로 같은 깊이의 노드들을 차례대로 방문합니다. 이러한 구조 덕분에 트리의 위쪽 레벨부터 아래쪽 레벨까지 순차적으로 출력할 수 있습니다.