이진 탐색 트리에서 가장 작은 요소와 가장 큰 요소를 찾아야 하는 경우 이진 트리 클래스를 만들고 트리에 요소를 추가하고 특정 노드를 검색하는 메서드를 정의합니다. 클래스의 인스턴스가 생성되고 이러한 메서드와 함께 사용됩니다.
아래는 동일한 데모입니다 -
예시
class BST_Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.parent = None
def insert_elem(self, node):
if self.key > node.key:
if self.left is None:
self.left = node
node.parent = self
else:
self.left.insert_elem(node)
elif self.key < node.key:
if self.right is None:
self.right = node
node.parent = self
else:
self.right.insert_elem(node)
def search_node(self, key):
if self.key > key:
if self.left is not None:
return self.left.search_node(key)
else:
return None
elif self.key < key:
if self.right is not None:
return self.right.search_node(key)
else:
return None
return self
class BSTree:
def __init__(self):
self.root = None
def add_elem(self, key):
new_node = BST_Node(key)
if self.root is None:
self.root = new_node
else:
self.root.insert_elem(new_node)
def search_node(self, key):
if self.root is not None:
return self.root.search_node(key)
def get_smallest_elem(self):
if self.root is not None:
current = self.root
while current.left is not None:
current = current.left
return current.key
def get_largest_elem(self):
if self.root is not None:
current = self.root
while current.right is not None:
current = current.right
return current.key
my_instance = BSTree()
print('Menu (Assume no duplicate keys)')
print('add ')
print('smallest')
print('largest')
print('quit')
while True:
my_input = input('What operation would you perform ? ').split()
operation = my_input[0].strip().lower()
if operation == 'add':
key = int(my_input[1])
my_instance.add_elem(key)
if operation == 'smallest':
smallest = my_instance.get_smallest_elem()
print('The smallest element is : {}'.format(smallest))
if operation == 'largest':
largest = my_instance.get_largest_elem()
print('The largest element is : {}'.format(largest))
elif operation == 'quit':
break 출력
Menu (Assume no duplicate keys) add <key> smallest largest quit What operation would you perform ? add 5 What operation would you perform ? add 8 What operation would you perform ? add 11 What operation would you perform ? add 0 What operation would you perform ? add 3 What operation would you perform ? smallest The smallest element is : 0 What operation would you perform ? largest The largest element is : 11 What operation would you perform ? quit’
설명
-
필수 속성을 가진 'BST_Node' 클래스가 생성됩니다.
-
왼쪽, 오른쪽 및 부모 노드를 '없음'으로 설정하는 데 사용되는 '초기화' 기능이 있습니다.
-
바이너리 트리에 요소를 삽입하는 데 도움이 되는 'insert_element' 메소드가 있습니다.
-
트리에서 특정 노드를 검색하는 'search_node'라는 또 다른 메서드입니다.
-
루트가 '없음'으로 설정된 'BSTree'라는 또 다른 클래스가 정의됩니다.
-
트리에 요소를 추가하는 'add_elem'이라는 메서드가 정의되어 있습니다.
-
트리에서 특정 노드를 찾는 데 도움이 되는 'search_node'라는 또 다른 메서드가 있습니다.
-
트리에서 가장 작은 노드를 가져오는 데 도움이 되는 'get_smallest_node'라는 또 다른 메서드가 정의되어 있습니다.
-
트리에서 가장 큰 노드를 가져오는 데 도움이 되는 'get_largest_node'라는 또 다른 메서드가 정의되어 있습니다.
-
'BSTree' 클래스의 객체가 생성됩니다.
-
사용자가 선택한 작업에 따라 작업이 수행됩니다.