연결 리스트(Linked List)를 이용해 이진 트리(Binary Tree) 자료구조를 구현할 때는 루트 노드를 설정하는 메서드, 중위 순회(in-order traversal)를 수행하는 메서드, 루트 노드의 왼쪽에 요소를 삽입하는 메서드, 루트 노드의 오른쪽에 요소를 삽입하는 메서드, 그리고 특정 값을 검색하는 메서드를 정의하면 됩니다.
아래에서 실제 구현 예시를 확인해 보세요.
예제 코드
class BinaryTree_structure:
def __init__(self, key=None):
self.key = key
self.left = None
self.right = None
def set_root(self, key):
self.key = key
def in_order_traversal(self):
if self.left is not None:
self.left.in_order_traversal()
print(self.key, end=' ')
if self.right is not None:
self.right.in_order_traversal()
def insert_left(self, new_node):
self.left = new_node
def insert_right(self, new_node):
self.right = new_node
def search_val(self, key):
if self.key == key:
return self
if self.left is not None:
temp = self.left.search_val(key)
if temp is not None:
return temp
if self.right is not None:
temp = self.right.search_val(key)
return temp
return None
btree = 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('quit')
while True:
print('The inorder traversal of binary tree ', end='')
if btree is not None:
btree.in_order_traversal()
print()
do = input('What would you like to do? ').split()
operation = do[0].strip().lower()
if operation == 'insert':
data = int(do[1])
new_node = BinaryTree_structure(data)
sub_op = do[2].strip().lower()
if sub_op == 'at':
btree = new_node
else:
position = do[4].strip().lower()
key = int(position)
ref_node = None
if btree is not None:
ref_node = btree.search_val(key)
if ref_node is None:
print('No such key exists')
continue
if sub_op == 'left':
ref_node.insert_left(new_node)
elif sub_op == 'right':
ref_node.insert_right(new_node)
elif operation == 'quit':
break실행 결과
Menu (this assumes no duplicate keys) insert <data> at root insert <data> left of <data> insert <data> right of <data> quit The inorder traversal of binary tree What would you like to do? insert 45 at root The inorder traversal of binary tree 45 What would you like to do? insert 78 left of 45 The inorder traversal of binary tree 78 45 What would you like to do? insert 90 right of 45 The inorder traversal of binary tree 78 45 90 What would you like to do? quit
코드 설명
‘BinaryTree_structure’ 클래스를 생성합니다.
트리의 루트(root) 값을 설정할 수 있는 ‘set_root’ 메서드가 포함되어 있습니다.
‘in_order_traversal’ 메서드는 트리를 ‘왼쪽 → 노드 → 오른쪽’ 순서로 순회하며 모든 노드의 값을 출력합니다.
‘insert_left’ 메서드는 지정한 노드의 왼쪽 자리에 새로운 요소를 추가합니다.
‘insert_right’ 메서드는 지정한 노드의 오른쪽 자리에 새로운 요소를 추가합니다.
‘search_val’ 메서드는 재귀 호출을 통해 주어진 키와 일치하는 노드를 찾아 해당 노드 객체를 반환하며, 존재하지 않으면 None을 반환합니다.
사용자에게는 ‘루트에 삽입(at root)’, ‘왼쪽에 삽입(left of)’, ‘오른쪽에 삽입(right of)’, ‘종료(quit)’ 네 가지 메뉴 옵션이 제공됩니다.
사용자가 입력한 명령에 따라 각각의 연산이 수행되며, 매 반복마다 현재 트리의 중위 순회 결과가 함께 출력됩니다.
모든 결과는 콘솔 화면에 표시됩니다.