Khi cần tìm các phần tử nhỏ nhất và lớn nhất trong cây tìm kiếm nhị phân, một lớp cây nhị phân được tạo và các phương thức thêm phần tử vào cây, tìm kiếm một nút cụ thể được xác định. Một thể hiện của lớp được tạo và được sử dụng với các phương thức này.
Dưới đây là một minh chứng về điều tương tự -
Ví dụ
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 Đầu ra
MenuMenu (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’
Giải thích
-
Lớp ‘BST_Node’ với các thuộc tính bắt buộc được tạo.
-
Nó có một hàm 'init' được sử dụng để đặt các nút bên trái, bên phải và nút cha thành 'Không có'.
-
Nó có phương thức ‘insert_element’ giúp chèn một phần tử vào cây nhị phân.
-
Một phương thức khác có tên là ‘search_node’ tìm kiếm một nút cụ thể trong cây.
-
Một lớp khác có tên là ‘BSTree’ được xác định, trong đó gốc được đặt thành ‘Không có’.
-
Phương thức có tên ‘add_elem’ được xác định để thêm các phần tử vào cây.
-
Có một phương thức khác có tên là ‘search_node’ giúp tìm kiếm một nút cụ thể trong cây.
-
Một phương thức khác có tên là ‘get_smallest_node’ được định nghĩa để giúp tìm nạp nút nhỏ nhất trong cây.
-
Một phương thức khác có tên là ‘get_largest_node’ được định nghĩa để giúp tìm nạp nút lớn nhất trong cây.
-
Một đối tượng của lớp ‘BSTree’ được tạo.
-
Dựa trên thao tác do người dùng chọn, thao tác được thực hiện.