이진 트리의 중위 순회(inorder traversal)에서 'n'번째 노드를 찾아야 하는 경우가 있습니다. 이를 위해서는 루트 노드 설정, 왼쪽 또는 오른쪽 자식 노드 추가, 중위 순회 수행 등의 기능을 갖춘 이진 트리 클래스를 먼저 생성해야 합니다. 클래스의 인스턴스를 만들면 이러한 메서드들을 자유롭게 호출하여 사용할 수 있습니다.
중위 순회는 왼쪽 서브트리를 먼저 방문하고, 그다음 현재(루트) 노드를 방문한 뒤, 마지막으로 오른쪽 서브트리를 방문하는 순서로 진행됩니다. 이 순서대로 노드를 하나씩 세어가며 n번째에 해당하는 노드를 반환하면 됩니다.
아래는 전체 구현 예시입니다 −
예제
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_nth(self, n):
return self.inorder_nth_helper_fun(n, [])
def inorder_nth_helper_fun(self, n, in_ord):
if self.left is not None:
temp = self.left.inorder_nth_helper_fun(n, in_ord)
if temp is not None:
return temp
in_ord.append(self)
if n == len(in_ord):
return self
if self.right is not None:
temp = self.right.inorder_nth_helper_fun(n, in_ord)
if temp is not None:
return temp
def insert_t0_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
btree_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('inorder ')
print('quit')
while True:
do = input('What would you like to do? ').split()
operation = do[0].strip().lower()
if operation == 'insert':
data = int(do[1])
new_node = BinaryTree_struct(data)
suboperation = do[2].strip().lower()
if suboperation == 'at':
btree_instance = new_node
else:
position = do[4].strip().lower()
key = int(position)
ref_node = None
if btree_instance is not None:
ref_node = btree_instance.search_elem(key)
if ref_node is None:
print('No such key.')
continue
if suboperation == 'left':
ref_node.insert_t0_left(new_node)
elif suboperation == 'right':
ref_node.insert_to_right(new_node)
elif operation == 'inorder':
if btree_instance is not None:
index = int(do[1].strip().lower())
node = btree_instance.inorder_nth(index)
if node is not None:
print('nth term of inorder traversal: {}'.format(node.key))
else:
print('The index exceeds maximum possible index.')
else:
print('The tree is empty...')
elif operation == 'quit':
break출력
Menu (this assumes no duplicate keys) insert <data> at root insert <data> left of <data> insert <data> right of <data> inorder quit What would you like to do? insert 5 at root What would you like to do? insert 6 left of 5 What would you like to do? insert 8 right of 5 What would you like to do? inorder 5 The index exceeds maximum possible index. What would you like to do? 6 6
코드 설명
필요한 속성을 갖춘 'BinaryTree_struct' 클래스가 생성됩니다.
'__init__' 함수는 왼쪽과 오른쪽 노드를 'None'으로 초기화하는 역할을 합니다.
'set_root' 메서드는 이진 트리의 루트를 설정하는 데 사용됩니다.
'inorder_nth' 메서드는 재귀 호출을 통해 중위 순회를 수행하며 n번째 노드를 찾습니다.
이를 위해 내부적으로 헬퍼 함수('inorder_nth_helper_fun')가 함께 정의되어 있습니다.
'insert_to_right' 메서드는 루트 노드의 오른쪽에 새로운 요소를 추가합니다.
'insert_to_left' 메서드는 루트 노드의 왼쪽에 새로운 요소를 추가합니다.
'search_elem' 메서드는 트리에서 특정 요소를 검색하는 기능을 담당합니다.
'BinaryTree_struct' 클래스의 인스턴스(객체)가 생성됩니다.
사용자로부터 수행할 작업에 대한 입력을 받습니다.
사용자의 선택에 따라 해당 작업이 실행됩니다.
결과로 얻은 출력이 콘솔에 표시됩니다.