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):
ifself.key> node.key:
ifself.leftis None:
self.left= node
node.parent= self
else:
self.left.insert_elem(node)
elifself.key< node.key:
ifself.rightis None:
self.right= node
node.parent= self
else:
self.right.insert_elem(node)
def search_node(self, key):
ifself.key> key:
ifself.leftis not None:
return self.left.search_node(key)
else:
return None
elifself.key< key:
ifself.rightis 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)
ifself.rootis None:
self.root = new_node
else:
self.root.insert_elem(new_node)
def search_node(self, key):
ifself.rootis not None:
return self.root.search_node(key)
def get_smallest_elem(self):
ifself.rootis not None:
current = self.root
whilecurrent.leftis not None:
current = current.left
return current.key
def get_largest_elem(self):
ifself.rootis not None:
current = self.root
whilecurrent.rightis 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) addsmallest 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”类。
它具有一个“init”功能，该功能用于将左，右和父节点设置为“None”。
它具有一个“insert_element”方法，可帮助将元素插入二叉树。
另一个名为“search_node”的方法可在树中搜索特定节点。
定义了另一个名为“BSTree”的类，其中根设置为“无”。
定义了一个名为“add_elem”的方法，该方法将元素添加到树中。
还有另一种名为“search_node”的方法，可帮助搜索树中的特定节点。
定义了另一个名为“get_smallest_node”的方法，该方法有助于获取树中的最小节点。
定义了另一个名为“get_largest_node”的方法，该方法有助于获取树中最大的节点。
创建了“BSTree”类的对象。
基于用户选择的操作，执行该操作。