Python程序查找二叉搜索树中最小和最大元素

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’类的对象。

  • 根据用户选择的操作执行操作。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程