# recursion.py -- 2分木を扱う再帰関数の例

from collections import namedtuple

# 2分木のデータ構造(節の生成)
Node = namedtuple('Node', ['node', 'left', 'right'])

def Leaf(c):
    """2分木の葉の生成"""
    return Node(c, None, None)

def show(t):
    """木を表す文字列"""
    if t is None: return '#'
    else:         return t.node + '(' + show(t.left) + ',' + show(t.right) + ')'

def size(t):
    """木の大きさ(節の総数)を再帰的に計算"""
    if t is None: return 0
    else:         return size(t.left) + size(t.right) + 1

def display(t, d=0):
    """木の大きさの再帰計算の様子を表示"""

    # 関数の開始直後，節情報を表示
    print('>       '*d, end='')
    if t is None: print('#')
    else:         print(repr(t.node))

    # 節数の計算本体
    if t is None: size = 0
    else:         size = display(t.left, d+1) + display(t.right, d+1) + 1

    # 関数の終了直前，部分木の大きさを表示
    print('>       '*d, end='')
    print(f'size = {size}')

    return size

# 木を表す文字列，木の節数，節数の再帰計算の過程 を順に表示

if __name__ == '__main__':

    t = Node('+',    # 算術式 a*b + c/d を表す木
             Node('*', Leaf('a'), Leaf('b')),
             Node('/', Leaf('c'), Leaf('d'))
             )             

    print(f't = {show(t)}')
    print(f'size(t) = {size(t)}')
    print('computation of size(t) :'); display(t)