Python 程序寻找二叉查找树中最小和最大元素的

  • Z时代
  • 2024-01-10
  • 分类：综合

当需要在二叉搜索树中找到最小和最大元素时，将创建二叉树类，并定义将元素添加到树中，搜索特定节点的方法。将创建该类的实例，并将其与这些方法一起使用。

以下是相同的演示-

示例

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)
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”类。

  • 它具有一个“ init”功能，该功能用于将左，右和父节点设置为“ None”。

  • 它具有一个“ insert_element”方法，可帮助将元素插入二叉树。

  • 另一个名为“ search_node”的方法可在树中搜索特定节点。

  • 定义了另一个名为“ BSTree”的类，其中根设置为“无”。

  • 定义了一个名为“ add_elem”的方法，该方法将元素添加到树中。

  • 还有另一种名为“ search_node”的方法，可帮助搜索树中的特定节点。

  • 定义了另一个名为“ get_smallest_node”的方法，该方法有助于获取树中的最小节点。

  • 定义了另一个名为“ get_largest_node”的方法，该方法有助于获取树中最大的节点。

  • 创建了“ BSTree”类的对象。

  • 基于用户选择的操作，执行该操作。

以上是 Python 程序寻找二叉查找树中最小和最大元素的 的全部内容， 来源链接： utcz.com/z/311486.html

回到顶部