트리에서 중위 순회(inorder traversal) 방식으로 가장 큰 값을 찾아야 할 때, 루트 노드를 설정하고 재귀 호출을 통해 중위 순회를 수행하는 등의 메서드를 포함한 이진 트리(binary tree) 클래스를 생성하면 됩니다.
클래스의 인스턴스를 생성한 후에는 해당 인스턴스를 통해 다양한 메서드에 접근하여 사용할 수 있습니다.
아래에서 실제 구현 예시를 확인해 보겠습니다.
예제 코드
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_largest(self):
largest = []
self.inorder_largest_helper_fun(largest)
return largest[0]
def inorder_largest_helper_fun(self, largest):
if self.left is not None:
self.left.inorder_largest_helper_fun(largest)
if largest == []:
largest.append(self.key)
elif largest[0] < self.key:
largest[0] = self.key
if self.right is not None:
self.right.inorder_largest_helper_fun(largest)
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
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('largest')
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 == 'largest':
if my_instance is None:
print('The tree is empty')
else:
print('The largest element is : {}'.format(my_instance.inorder_traversal_largest()))
elif operation == 'quit':
break
실행 결과
Menu (this assumes no duplicate keys)
insert <data> at root
insert <data> left of <data>
insert <data> right of <data>
largest
quit
What operation would you do ? insert 8 at root
What operation would you do ? insert 9 left of 8
What operation would you do ? insert 4 right of 8
What operation would you do ? largest
The largest element is : 9
What operation would you do ? > Use quit() or Ctrl-D (i.e. EOF) to exit
코드 설명
필요한 속성들을 갖춘 'BinaryTree_Struct' 클래스가 생성됩니다.
'__init__' 함수는 노드 생성 시 왼쪽(left)과 오른쪽(right) 자식 노드를 'None'으로 초기화하는 역할을 합니다.
'set_root' 메서드는 이진 트리의 루트(root) 노드를 설정하는 데 사용됩니다.
'inorder_traversal_largest' 메서드는 재귀 호출을 통해 중위 순회를 수행하며 트리 전체를 탐색합니다.
이 메서드 내부에서 사용되는 헬퍼(helper) 함수인 'inorder_largest_helper_fun'이 함께 정의되어 있으며, 순회 과정에서 가장 큰 값을 추적합니다.
'insert_to_right' 메서드는 특정 노드의 오른쪽에 새로운 요소를 추가하는 기능을 담당합니다.
'insert_to_left' 메서드는 특정 노드의 왼쪽에 새로운 요소를 추가하는 기능을 담당합니다.
'search_elem' 메서드는 트리에서 특정 키 값을 가진 노드를 검색하는 역할을 합니다.
'BinaryTree_Struct' 클래스의 객체(인스턴스)가 생성됩니다.
사용자로부터 수행할 작업(연산)에 대한 입력을 받습니다.
사용자의 선택에 따라 삽입(insert), 최댓값 조회(largest), 종료(quit) 등의 작업이 수행됩니다.
작업 결과는 콘솔 화면에 출력됩니다.
동작 원리 요약
중위 순회는 왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리 순서로 노드를 방문하는 방식입니다. 이 코드에서는 순회하면서 지금까지 방문한 노드 중 최댓값을 리스트에 저장하고, 각 노드의 키 값과 비교하여 더 큰 값이 나타나면 갱신합니다. 모든 노드의 방문이 끝나면 리스트의 첫 번째 요소, 즉 트리 전체의 최댓값이 반환됩니다.