ツリー内のリーフノードの数をカウントするPythonプログラム

ツリー内のリーフノードの数をカウントする必要がある場合は、「Tree_structure」クラスが作成され、ルート値を追加するメソッド、およびその他の子の値が定義されます。ユーザーが選択できるさまざまなオプションが用意されています。ユーザーの選択に基づいて、操作はツリー要素に対して実行されます。

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

例

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

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

   def add_vals(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 count_leaf_node(self):
      leaf_nodes = []
      self.count_leaf_node_helper_fun(leaf_nodes)
      return len(leaf_nodes)

   def count_leaf_node_helper_fun(self, leaf_nodes):
      if self.children == []:
         leaf_nodes.append(self)
      else:
         for child in self.children:
            child.count_leaf_node_helper_fun(leaf_nodes)

tree = None

print('Menu (this assumes no duplicate keys)')
print('add <data> at root')
print('add <data> below <data>')
print('count')
print('quit')

while True:
   my_input = input('What operation would you like to perform ? ').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.')
            continue
         ref_node.add_vals(newNode)

   elif operation == 'count':
      if tree is None:
         print('The tree is empty')
      else:
         count = tree.count_leaf_node()
         print('The number of leaf nodes are : {}'.format(count))

   elif operation == 'quit':
      break

出力

Menu (this assumes no duplicate keys)
add <data> at root
add <data> below <data>
count
quit
What operation would you like to perform ? add 78 at root
What operation would you like to perform ? add 90 below 78
What operation would you like to perform ? add 8 below 78
What operation would you like to perform ? count
The number of leaf nodes are : 2
What operation would you like to perform ? quit

説明

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

• 「キー」をTrueに設定し、ツリーの子に空のリストを設定します。

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

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

• ツリー内の要素の検索に役立つ「search_val」という名前の別のメソッドが定義されています。

• 「count_leaf_nodes」という名前の別のメソッドが定義されています。これは、ツリーのリーフノードの数を取得するのに役立ちます。

• 「count_leaf_nodes_helper」という名前の別のメソッドが定義されています。これは、以前に定義された関数を呼び出します。これは再帰関数です。

• 「ルートに追加」、「下に追加」、「カウント」、「終了」など、4つのオプションがあります。

• ユーザーが指定したオプションに応じて、それぞれの操作が実行されます。

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