二分木のすべてのノードの合計を見つけるPythonプログラム

ツリーのすべてのノードの合計を見つける必要がある場合は、クラスが作成されます。このクラスには、ルートノードの設定、ツリーへの要素の追加、特定の要素の検索、およびツリーの要素の追加を行うためのメソッドが含まれています。合計などを見つけます。これらのメソッドにアクセスして使用するために、クラスのインスタンスを作成できます。

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

例

class Tree_struct:
   def __init__(self, data=None):
      self.key = data
      self.children = []

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

   def add_node(self, node):
      self.children.append(node)

   def search_node(self, key):
      if self.key == key:
         return self
      for child in self.children:
         temp = child.search_node(key)
         if temp is not None:
            return temp
      return None

   def sum_node(self):
      my_summation = self.key
      for child in self.children:
         my_summation = my_summation + child.sum_node()
      return my_summation

my_instance = None

print('Menu (assume no duplicate keys)')
print('add <data> at root')
print('add <data> below <data>')
print('sum')
print('quit')

while True:
   my_input = input('What operation would you do ? ').split()

   operation = my_input[0].strip().lower()
   if operation == 'add':
      data = int(my_input[1])
      new_node = Tree_struct(data)
      suboperation = my_input[2].strip().lower()
      if suboperation == 'at':
         my_instance = new_node
      elif suboperation == 'below':
         position = my_input[3].strip().lower()
         key = int(position)
         ref_node = None
         if my_instance is not None:
            ref_node = my_instance.search_node(key)
         if ref_node is None:
            print('No such key')
            continue
         ref_node.add_node(new_node)

   elif operation == 'sum':
      if my_instance is None:
         print('The tree is empty')
      else:
         my_summation = my_instance.sum_node()
         print('Sum of all nodes is: {}'.format(my_summation))

   elif operation == 'quit':
      break

出力

Menu (assume no duplicate keys)
add <data> at root
add <data> below <data>
sum
quit
What operation would you do ? add 5 at root
What operation would you do ? add 7 below 5
What operation would you do ? add 0 below 7
What operation would you do ? sum
Sum of all nodes is: 12
What operation would you do ? quit

説明

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

• 空のリストを作成するために使用される「init」関数があります。

• 二分木のルート値を設定するのに役立つ「set_root」メソッドが定義されています。

• ツリーに要素を追加するのに役立つ「add_node」メソッドがあります。

• 「search_elem」という名前のメソッドが定義されており、特定の要素の検索に役立ちます。

• 「sum_node」という名前のメソッドが定義されています。これは、ツリーの要素を追加して合計を見つけるのに役立ちます。

• インスタンスが作成され、「なし」に割り当てられます。

• 実行する必要のある操作に対してユーザー入力が行われます。

• ユーザーの選択に応じて、操作が実行されます。

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