Pythonにおける木構造の実装と応用

木構造の基本概念

木構造は階層的な関係を模倣するデータ構造で、各要素はノードと呼ばれます。木の各ノードはゼロ個以上の子ノードを持つことができますが、各ノードは親ノードを一つしか持たない、という特徴があります。ルートノードだけは親ノードを持たない例外です。木構造の重要な特性は、循環がないことです。つまり、あるノードから出発しても、同じノードに戻ることはできません。

木構造の基本的な構成要素は以下の通りです：

• ルートノード：木の開始点となるノードで、親ノードがありません。
• 枝：ルートノードに接続されるサブツリー。
• 葉ノード：子ノードを持たないノード。
• ノード：木内の任意の要素。

木のデータ抽象化

Pythonでは、リストを使って木を表現できます。木のデータ抽象化にはコンストラクタとセレクタが含まれます：

def 木構築(根ラベル, 枝=[]):
    for branch in 枝:
        assert is_tree(branch), '枝は木でなければなりません'
    return [根ラベル] + list(枝)

def ノード値(木):
    return 木[0]

def 枝(木):
    return 木[1:]

def is_tree(木):
    if type(木) != list or len(木) < 1:
        return False
    for branch in 枝(木):
        if not is_tree(branch):
            return False
    return True

def is_leaf(木):
    return not 枝(木)

木の構築と操作の例

ネストされた式を使って木を構築できます。例えば、以下の木`t`は根ラベル10と3つの枝を持っています：

t = 木構築(10, [木構築(5), 木構築(7, [木構築(3), 木構築(4)]), 木構築(8)])
print(t)  # [10, [5], [7, [3], [4]], [8]]
print(ノード値(t))  # 10
print(枝(t))  # [[5], [7, [3], [4]], [8]]
print(ノード値(枝(t)[1]))  # 7
print(is_leaf(t))  # False
print(is_leaf(枝(t)[0]))  # True

木の再帰関数

木の再帰関数を使って、木を構築したり処理したりできます。例えば、階乗木は再帰的に階乗の木構造を構築します：

def 階乗木(n):
    if n == 0 or n == 1:
        return 木構築(1)
    else:
        左, 右 = 階乗木(n-1), 階乗木(n-2)
        fact_n = ノード値(左) * ノード値(右)
        return 木構築(fact_n * n, [左, 右])

print(階乗木(4))  # [24, [6, [2, [1], [1]], [2, [1], [1]]], [2, [1], [1]]]

木の葉の数え上げ

再帰関数を使って木の葉ノードの数を計算できます：

def 葉の数(木):
    if is_leaf(木):
        return 1
    else:
        枝の数 = [葉の数(b) for b in 枝(木)]
        return sum(枝の数)

print(葉の数(階乗木(4)))  # 5

分割木

分割木は整数の分割を表現します。分割木の構築と出力は以下の通りです：

def 分割木(n, m):
    if n == 0:
        return 木構築(True)
    elif n < 0 or m == 0:
        return 木構築(False)
    else:
        左 = 分割木(n-m, m)
        右 = 分割木(n, m-1)
        return 木構築(m, [左, 右])

def 分割を出力(木, 分割=[]):
    if is_leaf(木):
        if ノード値(木):
            print(' + '.join(分割))
    else:
        左, 右 = 枝(木)
        m = str(ノード値(木))
        分割を出力(左, 分割 + [m])
        分割を出力(右, 分割)

分割を出力(分割木(5, 3))

二分木への変換

二分木への変換は、木を右枝の二分木に変換します：

def 右二分木化(木):
    if is_leaf(木):
        return 木
    if len(木) > 2:
        木 = [木[0], 木[1:]]
    return [右二分木化(b) for b in 木]

print(右二分木化([1, 2, 3, 4, 5, 6, 7, 8]))  # [1, [2, [3, [4, [5, [6, [7, 8]]]]]]]

演習問題

1. 木の構築：根ノードが15で、2つの枝を持つ木を構築してください。最初の枝は葉ノード7で、2つ目の枝は根ノードが12の木で、その木には葉ノード5と3があります。
2. ノード数の計算：木のすべてのノードの数を計算する関数`全ノード数`を記述してください。
3. 木構造の出力：インデント付き形式で木の構造を出力する関数`木を出力`を記述してください。
4. 木の深さ：木の最大深さを計算する関数`木の深さ`を記述してください。

演習問題の解答

1. 木の構築

t = 木構築(15, [木構築(7), 木構築(12, [木構築(5), 木構築(3)])])
print(t)  # [15, [7], [12, [5], [3]]]

2. ノード数の計算

def 全ノード数(木):
    if is_leaf(木):
        return 1
    else:
        return 1 + sum(全ノード数(b) for b in 枝(木))

print(全ノード数(t))  # 5

3. 木構造の出力

def 木を出力(木, インデント=0):
    print(' ' * インデント + str(ノード値(木)))
    for branch in 枝(木):
        木を出力(branch, インデント + 2)

木を出力(t)

4. 木の深さ

def 木の深さ(木):
    if is_leaf(木):
        return 1
    else:
        return 1 + max(木の深さ(b) for b in 枝(木))

print(木の深さ(t))  # 3