二分探索木で最小要素と最大要素を見つける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('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」関数があります。

• バイナリツリーに要素を挿入するのに役立つ「insert_element」メソッドがあります。

• ツリー内の特定のノードを検索する「search_node」という名前の別のメソッド。

• 「BSTree」という名前の別のクラスが定義されており、ルートは「None」に設定されています。

• ツリーに要素を追加する「add_elem」という名前のメソッドが定義されています。

• ツリー内の特定のノードを検索するのに役立つ「search_node」という名前の別のメソッドがあります。

• ツリー内の最小ノードをフェッチするのに役立つ「get_smallest_node」という名前の別のメソッドが定義されています。

• ツリーで最大のノードをフェッチするのに役立つ「get_largest_node」という名前の別のメソッドが定義されています。

• 「BSTree」クラスのオブジェクトが作成されます。

• ユーザーが選択した操作に基づいて、操作が実行されます。