Pythonでツリーのリーフノード（葉ノード）の数を数える方法

ツリー構造においてリーフノード（葉ノード）とは、子を持たない末端のノードのことです。本記事では、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」クラスを定義します。
• コンストラクタでは、ノードの値を格納する「key」と、子ノードを保持する空のリスト「children」を初期化します。
• 「set_root_node」メソッドは、ツリーのルートの値を設定するために使用します。
• 「add_vals」メソッドは、指定したノードに新しい要素（子ノード）を追加します。
• 「search_val」メソッドは、指定したキーの値を持つノードをツリー内から再帰的に検索します。
• 「count_leaf_node」メソッドは、ツリー内のリーフノードの総数を取得します。内部ではリーフノードを格納するリストを作成し、ヘルパー関数を呼び出した後、そのリストの長さを返します。
• 「count_leaf_node_helper_fun」は再帰的なヘルパー関数です。子ノードが存在しない場合（つまりリーフノードの場合）、そのノード自身をリストに追加し、子ノードがある場合は各子ノードに対して自分自身を再帰的に呼び出します。
• メイン部分では、「ルートに追加」「指定ノードの下に追加」「カウント」「終了」の4つの操作メニューを提供しています。
• ユーザーが選択した操作に応じて、対応する処理が実行され、その結果がコンソールに出力されます。

この例では、値78をルートとし、その下に90と8という2つの子ノードを追加しているため、リーフノードは90と8の2つとなり、カウント結果として「2」が出力されます。このように再帰処理を活用することで、任意の深さのツリー構造でも効率的にリーフノードを数えることができます。