二分探索木を使用してソートするPythonプログラム

二分探索木を並べ替える必要がある場合は、クラスが作成され、その中に要素の挿入や順序どおりの走査の実行などの操作を実行するメソッドが定義されます。

以下は同じのデモンストレーションです-

例

class BinSearchTreeNode:
   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 inorder_traversal(self):
      if self.left is not None:
         self.left.inorder_traversal()
      print(self.key, end=' ')
      if self.right is not None:
         self.right.inorder_traversal()

class BinSearchTree:
   def __init__(self):
      self.root = None

   def inorder_traversal(self):
      if self.root is not None:
         self.root.inorder_traversal()

   def add_val(self, key):
      new_node = BinSearchTreeNode(key)
      if self.root is None:
         self.root = new_node
      else:
         self.root.insert_elem(new_node)

my_instance = BinSearchTree()

my_list = input('Enter the list of numbers... ').split()
my_list = [int(x) for x in my_list]
for x in my_list:
   my_instance.add_val(x)
print('Sorted list: ')
print(my_instance.inorder_traversal())

出力

Enter the list of numbers... 67 54 89 0 11 34 99
Sorted list:
0 11 34 54 67 89 99

説明

• 必要な属性を持つ「BinSearchTreeNode」クラスが作成されます。

• 「左」、「右」、「親」ノードを「なし」に割り当てるために使用される「init」関数があります。

• ツリーにノードを追加するのに役立つ「insert_elem」という名前の別のメソッドが定義されています。

• 「inorder_traversal」という名前の別のメソッドが定義されています。これは、ツリーで順序どおりのトラバーサルを実行するのに役立ちます。

• 「BinSearchTree」という名前の別のクラスが定義されています。

• ルートを「なし」に設定します。

• ツリー上で順序どおりの走査を実行するのに役立つ「inorder_traversal」という名前のメソッドがあります。

• ツリーにノードを追加するのに役立つ「add_val」という名前の別のメソッドが定義されています。

• 「BinSearchTree」のインスタンスが作成されます。

• 番号のリストはユーザーが取得します。

• これを使用してツリーが作成されます。

• リストがソートされ、その順序どおりのトラバーサルが実行されます。

• 関連する出力がコンソールに表示されます。