#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 ''
ZOJ Problem Set - 1062 Trees Made to Order Python&n
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- Day 12 神句文档 The team contends that these bear more than a...
- 避免陷入问题无处不在的思维模式。 今天花了一上午体检排队，发的晚了。 文章内容对我的启发是我们要用积极乐观的态度看...
- 由于公司php环境升级 之前公司一使用织梦dede二次开发的网站趴窝了 。报错DedeCMS错误DedeCMS E...
