Pythonでツリー内の全ノードの合計値を求めるプログラムの作成方法

ツリー構造内のすべてのノードの合計値を求める必要がある場合、「Tree_structure」クラスを作成し、ルート値を設定するメソッドや、他の値を追加するメソッドを定義します。さらに、ツリー構造のすべての要素の合計を計算するメソッドも用意します。ユーザーには複数の操作オプションが提示され、選択された内容に応じて、ツリーの要素に対して対応する処理が実行されます。

以下にその実装例を示します。

サンプルコード

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

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

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

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

   def summation_nodes(self):
      sum_val = self.key
      for child in self.children:
         sum_val = sum_val + child.summation_nodes()
      return sum_val

tree = None

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

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

   operation = my_input[0].strip().lower()
   if operation == 'add':
      data = int(my_input[1])
      newNode = Tree_structure(data)
      sub_op = my_input[2].strip().lower()
      if sub_op == 'at':
         tree = newNode
      elif sub_op == 'below':
         my_pos = my_input[3].strip().lower()
         key = int(my_pos)
         ref_node = None
         if tree is not None:
            ref_node = tree.search_val(key)
         if ref_node is None:
            print('No such key exists')
            continue
         ref_node.add_values(newNode)

   elif operation == 'summation':
      if tree is None:
         print('The tree is empty')
      else:
         summation_val = tree.summation_nodes()
         print('Sum of all the nodes is : {}'.format(summation_val))

   elif operation == 'quit':
      break

実行結果

Menu (no duplicate keys allowed)
add <data> at root
add <data> below <data>
summation
quit
What would you like to do? add 56 at root
What would you like to do? add 45 below 56
What would you like to do? add 23 below 56
What would you like to do? summation
Sum of all the nodes is : 124
What would you like to do?

解説

• まず「Tree_structure」というクラスを作成します。

• コンストラクタでは「key」属性にデータを格納し、子ノードを管理するための空のリストを「children」に設定します。

• 「set_root」関数は、ツリーのルート値を設定するために使用されます。

• 「add_values」というメソッドが定義されており、これによりツリーへ新しい要素（ノード）を追加できます。

• また、「search_val」というメソッドも定義されており、ツリー内から指定したキーの要素を検索できます。

• さらに、「summation_nodes」というメソッドは、ツリー内のすべての要素（ノード）の合計値を取得する役割を担います。

• この合計計算メソッドは再帰関数として実装されており、各子ノードに対して自身を呼び出しながら合計を積み上げていきます。

• ユーザーには「ルートへの追加」「指定ノード下への追加」「合計計算」「終了」の4つの選択肢が提示されます。

• ユーザーが選択したオプションに応じて、それぞれ対応する処理が実行されます。

• 処理結果はコンソール上に出力されます。