二項ツリーを実装するPythonプログラム

Pythonで二項ツリーを実装する必要がある場合は、オブジェクト指向メソッドが使用されます。ここでは、クラスが定義され、属性が定義されています。関数は、特定の操作を実行するクラス内で定義されます。クラスのインスタンスが作成され、関数は電卓操作を実行するために使用されます。

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

例

class binomial_tree:
   def __init__(self, key):
      self.key = key
      self.children = []
      self.order = 0
   def add_at_end(self, t):
      self.children.append(t)
      self.order = self.order + 1
my_tree = []
print('Menu')
print('create <key>')
print('combine <index1> <index2>')
print('exit')
while True:
   option = input('What do you wish like to do? ').split()
   operation = option[0].strip().lower()
   if operation == 'create':
      key = int(option[1])
      b_tree = binomial_tree(key)
      my_tree.append(b_tree)
      print('Binomial tree has been created.')
   elif operation == 'combine':
      index_1 = int(option[1])
      index_2 = int(option[2])
      if my_tree[index_1].order == my_tree[index_2].order:
         my_tree[index_1].add_at_end(my_tree[index_2])
         del my_tree[index_2]
         print('Binomial trees have been combined.')
      else:
         print('Order of trees need to be the same to combine them.')
   elif operation == 'exit':
      print("Exit")
      break
   print('{:>8}{:>12}{:>8}'.format('Index', 'Root key', 'Order'))
   for index, t in enumerate(my_tree):
print('{:8d}{:12d}{:8d}'.format(index, t.key, t.order))

出力

Menu
create <key>
combine <index1> <index2>
exit
What do you wish like to do? create 7
Binomial tree has been created.
Index Root key Order
0 7 0
What do you wish like to do? create 11
Binomial tree has been created.
Index Root key Order
0 7 0
1 11 0
What do you wish like to do? create 4
Binomial tree has been created.
Index Root key Order
   0    7    0
   1    11    0
   2    4    0
What do you wish like to do? combine 0 1
Binomial trees have been combined.
Index Root key Order
   0    7    1
   1    4    0
What do you wish like to do? exit
Exit

説明

• 「binomial_tree」という名前のクラスが定義されています。
• ツリーの最後に要素を追加するメソッドがあります。
• 空のリストが作成されます。
• オプションに基づいて、ユーザーはオプションを選択します。
• キーの作成を選択すると、クラスのインスタンスが作成され、二項ツリーが作成されます。
• インデックス、ルート値、順序も計算されます。
• インデックスを組み合わせる必要がある場合は、別のオプションが選択され、組み合わせる必要のあるノードのインデックス値も示されます。
• これによりデータが結合され、表示されます。