リンクリストを使用してバイナリツリーを実装するPythonプログラム

リンクリストを使用して二分木データ構造を実装する必要がある場合、ルートノードを設定する方法、順序どおりにトラバーサルを実行する方法、ルートノードの左側に要素を挿入する方法、ルートノードの右側、および値を検索する方法が定義されています。

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

例

class BinaryTree_structure:
   def __init__(self, key=None):
      self.key = key
      self.left = None
      self.right = None

   def set_root(self, key):
      self.key = key

   def in_order_traversal(self):
      if self.left is not None:
         self.left.in_order_traversal()
      print(self.key, end=' ')
      if self.right is not None:
         self.right.in_order_traversal()

   def insert_left(self, new_node):
      self.left = new_node

   def insert_right(self, new_node):
      self.right = new_node

   def search_val(self, key):
      if self.key == key:
         return self
      if self.left is not None:
         temp = self.left.search_val(key)
         if temp is not None:
            return temp
      if self.right is not None:
         temp = self.right.search_val(key)
         return temp
      return None

btree = None

print('Menu (this assumes no duplicate keys)')
print('insert <data> at root')
print('insert <data> left of <data>')
print('insert <data> right of <data>')
print('quit')

while True:
   print('The inorder traversal of binary tree ', end='')
   if btree is not None:
      btree.in_order_traversal()
   print()

   do = input('What would you like to do? ').split()

   operation = do[0].strip().lower()
   if operation == 'insert':
      data = int(do[1])
      new_node = BinaryTree_structure(data)
      sub_op = do[2].strip().lower()
      if sub_op == 'at':
         btree = new_node
      else:
         position = do[4].strip().lower()
         key = int(position)
         ref_node = None
         if btree is not None:
            ref_node = btree.search_val(key)
         if ref_node is None:
            print('No such key exists')
            continue
         if sub_op == 'left':
            ref_node.insert_left(new_node)
         elif sub_op == 'right':
            ref_node.insert_right(new_node)
      elif operation == 'quit':
         break

出力

Menu (this assumes no duplicate keys)
insert <data> at root
insert <data> left of <data>
insert <data> right of <data>
quit
The inorder traversal of binary tree
What would you like to do? insert 45 at root
The inorder traversal of binary tree 45
What would you like to do? insert 78 left of 45
The inorder traversal of binary tree 78 45
What would you like to do? insert 90 right of 45
The inorder traversal of binary tree 78 45 90
What would you like to do? quit

説明

• 「BinaryTree_structure」クラスが作成されます。

• ツリーのルート値を設定するのに役立つ「set_root」関数があります。

• 「in_order_traversal」という名前のメソッドが定義されています。これは、「左->ノード->右」の順序でツリーをトラバースするのに役立ちます。

• 「insert_left」という名前の別のメソッドが定義されています。これは、ルート値の左側に要素を追加するのに役立ちます。

• 「insert_right」という名前の別のメソッドが定義されています。これは、ルート値の右側に要素を追加するのに役立ちます。

• 「search_val」という名前の別のメソッドが定義されています。これは、スタックの最上位から値を削除し、削除された値を返すのに役立ちます。

• 「ルートに挿入」、「左に挿入」、「右に挿入」、「終了」など、4つのオプションがあります。

• ユーザーによる入力/選択に基づいて、それぞれの操作が実行されます。

• この出力はコンソールに表示されます。