ZOJ Problem Set - 1062 Trees Mad

#encoding=utf8

import sys

 
# h(n)表示具有n个结点的不同形态的二叉树的数目
h = []
# s(n)表示具有n个结点的二叉树的第一棵树的编号
# s(n) = h(n-1) + s(n-1)
s = []
def print_tree(node_n, no):

    """打印出节点数为node_n的第no棵数，no从1开始"""
    index = 1
    for i in range(0, node_n):
        if no < index + h[i] * h[node_n - 1 - i]:
            no_right = (no - index + 1) % h[node_n - 1 - i]
            if no_right == 0:
                no_left = (no - index + 1) / h[node_n - 1 - i]
                no_right = h[node_n - 1 - i]
            else:
                no_left = (no - index + 1) / h[node_n - 1 - i] + 1
            # 存在左子树
            if i > 0:
                sys.stdout.write('(')
                print_tree(i, no_left)
                sys.stdout.write(')')
            sys.stdout.write('X')

            # 存在右子树
            if node_n - 1 - i > 0:
                sys.stdout.write('(')
                print_tree(node_n - 1 - i, no_right)
                sys.stdout.write(')')
            break
        else:
            index += h[i] * h[node_n - 1 - i]

            
if __name__ == '__main__':

    # 为s[]和h[]赋初值
    h.append(1)
    h.append(1)
    s.append(0)
    s.append(1)
    # 迭代计算s[]和h[]
    while s[-1] < 500000000:
        n = len(h)
        h_n = 0
        for i in range(0, n):
            h_n += h[i] * h[n - 1 - i]
        h.append(h_n)
        s.append(s[-1] + h[len(s) - 1])

    for no in sys.stdin:
        no = int(no)
        if no == 0:
            break
        for i in reversed(range(0, len(s))):
            if no >= s[i]:
                # node_n为结点数
                node_n = i
                print_tree(node_n, no - s[i] + 1)

        print ''