Python程序查找二叉搜索树中最小和最大元素
当需要查找二叉搜索树中的最小值和最大值时,需要创建一个二叉树类,并定义向树中添加元素以及搜索特定节点的方法。然后创建该类的实例,并使用这些方法。
下面是一个演示示例:
示例
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('菜单(假设没有重复的键)')
print('加')
print('最小值')
print('最大值')
print('退出')
while True:
my_input = input('要执行哪个操作?').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('最小元素是:{}'.format(smallest))
if operation == 'largest':
largest = my_instance.get_largest_elem()
print('最大元素是:{}'.format(largest))
elif operation == 'quit':
break
输出
菜单(假设没有重复的键)
加 <key>
最小值
最大值
退出
要执行哪个操作?添加5
要执行哪个操作?添加8
要执行哪个操作?添加11
要执行哪个操作?添加0
要执行哪个操作?添加3
要执行哪个操作?最小值
最小元素是:0
要执行哪个操作?最大值
最大元素是:11
要执行哪个操作?退出
说明
-
创建了具有所需属性的‘BST_Node’类。
-
它有一个‘init’函数,用于将左、右和父节点设置为“None”。
-
它有一个‘insert_element’方法,用于将元素插入二叉树。
-
另一个名为‘search_node’的方法,在树中搜索特定节点。
-
定义了另一个名为‘BSTree’的类,其中根节点被设置为“None”。
-
定义了一个名为‘add_elem’的方法,用于向树中添加元素。
-
还有另一个名为‘search_node’的方法,用于在树中搜索特定节点。
-
定义了另一个名为‘get_smallest_node’的方法,用于获取树中最小的节点。
-
定义了另一个名为‘get_largest_node’的方法,用于获取树中最大的节点。
-
创建了‘BSTree’类的对象。
-
根据用户选择的操作执行操作。