c**********e
发帖数: 2007 | 1 A binary tree is full if all of its vertices have either zero or two
children. Let B_n denote the number of full binary trees with n
vertices. What is B_n? |
t*****j
发帖数: 1105 | 2 我感觉这题应该用数学归纳法。
首先可以确定的是n一定要是奇数，偶数个数的n不存在full binary trees.
B(1) = 1
B(3) = 1
given B(n)
B(n+2): 实际上就是在B(n)个数上加两个节点。可以确定的是这两个节点一定是在一起
的。因为B(n)的所有节点都是偶数个小孩。要保持平衡只能加在同一个节点上。
所以这就是计算B(n)颗树总共有多少叶节点。总共有（n+1）/2个节点。因为每次的递
增都是只增加一个叶节点。
所以 B(n+2)=B(n)×（n+1）/2
然后算通式。。。
A binary tree is full if all of its vertices have either zero or two
children.
Let B_n denote the number of full binary trees with n vertices. What is B_n?
【在 c**********e 的大作中提到】
: A binary tree is full if all of its vertices have either zero or two
: children. Let B_n denote the number of full binary trees with n
: vertices. What is B_n?
|
t*****j
发帖数: 1105 | 3 我这个算法可能不一定对，可能有些数算重复了。
我感觉这题应该用数学归纳法。
首先可以确定的是n一定要是奇数，偶数个数的n不存在full binary trees.
B(1) = 1
B(3) = 1
given B(n)
B(n+2): 实际上就是在B(n)个数上加两个节点。可以确定的是这两个节点一定是在一起
的。因为B(n)的所有节点都是偶数个小孩。要保持平衡只能加在同一个节点上。
所以这就是计算B(n)颗树总共有多少叶节点。总共有（n+1）/2个节点。因为每次的递
增都是只增加一个叶节点。
所以 B(n+2)=B(n)×（n+1）/2
然后算通式。。。
A binary tree is full if all of its vertices have either zero or two
children.
Let B_n denote the number of full binary trees with n vertices. What is B_n?
【在 t*****j 的大作中提到】
: 我感觉这题应该用数学归纳法。
: 首先可以确定的是n一定要是奇数，偶数个数的n不存在full binary trees.
: B(1) = 1
: B(3) = 1
: given B(n)
: B(n+2): 实际上就是在B(n)个数上加两个节点。可以确定的是这两个节点一定是在一起
: 的。因为B(n)的所有节点都是偶数个小孩。要保持平衡只能加在同一个节点上。
: 所以这就是计算B(n)颗树总共有多少叶节点。总共有（n+1）/2个节点。因为每次的递
: 增都是只增加一个叶节点。
: 所以 B(n+2)=B(n)×（n+1）/2
|
t*****j
发帖数: 1105 | 4 可能应该用剪枝法来算。。。。
不会用telnet修改文章的下场。。。一遍遍地发。
【在 t*****j 的大作中提到】
: 我这个算法可能不一定对，可能有些数算重复了。
:
: 我感觉这题应该用数学归纳法。
: 首先可以确定的是n一定要是奇数，偶数个数的n不存在full binary trees.
: B(1) = 1
: B(3) = 1
: given B(n)
: B(n+2): 实际上就是在B(n)个数上加两个节点。可以确定的是这两个节点一定是在一起
: 的。因为B(n)的所有节点都是偶数个小孩。要保持平衡只能加在同一个节点上。
: 所以这就是计算B(n)颗树总共有多少叶节点。总共有（n+1）/2个节点。因为每次的递
|
c**********e
发帖数: 2007 | 5 B_3=1
B_5=2
B_7=5 or 6? I got 5.
【在 t*****j 的大作中提到】
: 我感觉这题应该用数学归纳法。
: 首先可以确定的是n一定要是奇数，偶数个数的n不存在full binary trees.
: B(1) = 1
: B(3) = 1
: given B(n)
: B(n+2): 实际上就是在B(n)个数上加两个节点。可以确定的是这两个节点一定是在一起
: 的。因为B(n)的所有节点都是偶数个小孩。要保持平衡只能加在同一个节点上。
: 所以这就是计算B(n)颗树总共有多少叶节点。总共有（n+1）/2个节点。因为每次的递
: 增都是只增加一个叶节点。
: 所以 B(n+2)=B(n)×（n+1）/2
|
t*****j
发帖数: 1105 | 6 所以说我算重了。还应该去掉重复的数。
我这个是搭数的步骤的数目，而不是最终的数的数目。
有的数可能最有一样但是步骤不同。
【在 c**********e 的大作中提到】
: B_3=1
: B_5=2
: B_7=5 or 6? I got 5.
|
b******v
发帖数: 1493 | 7 我得到的递推公式是
B(n) = 0 if n is even
B(n) = B(1)*B(n-2)+B(3)*B(n-4)+ ... +B(n-4)*B(3)+B(n-2)*B(1)
= \sum_{k=1,...,n-2, k is odd} B(k)*B(n-1-k) if n is odd
n?
【在 t*****j 的大作中提到】
: 我感觉这题应该用数学归纳法。
: 首先可以确定的是n一定要是奇数，偶数个数的n不存在full binary trees.
: B(1) = 1
: B(3) = 1
: given B(n)
: B(n+2): 实际上就是在B(n)个数上加两个节点。可以确定的是这两个节点一定是在一起
: 的。因为B(n)的所有节点都是偶数个小孩。要保持平衡只能加在同一个节点上。
: 所以这就是计算B(n)颗树总共有多少叶节点。总共有（n+1）/2个节点。因为每次的递
: 增都是只增加一个叶节点。
: 所以 B(n+2)=B(n)×（n+1）/2
|
t*****j
发帖数: 1105 | 8 我觉得你这个递推还是会算重复。
我得到的递推公式是
B(n) = 0 if n is even
B(n) = B(1)*B(n-2)+B(3)*B(n-4)+ ... +B(n-4)*B(3)+B(n-2)*B(1)
= \sum_{k=1,...,n-2, k is odd} B(k)*B(n-1-k) if n is odd
n?
【在 b******v 的大作中提到】
: 我得到的递推公式是
: B(n) = 0 if n is even
: B(n) = B(1)*B(n-2)+B(3)*B(n-4)+ ... +B(n-4)*B(3)+B(n-2)*B(1)
: = \sum_{k=1,...,n-2, k is odd} B(k)*B(n-1-k) if n is odd
:
: n?
|
t*****j
发帖数: 1105 | 9 而且比我那个算重复的数目还多。。
【在 t*****j 的大作中提到】
: 我觉得你这个递推还是会算重复。
:
: 我得到的递推公式是
: B(n) = 0 if n is even
: B(n) = B(1)*B(n-2)+B(3)*B(n-4)+ ... +B(n-4)*B(3)+B(n-2)*B(1)
: = \sum_{k=1,...,n-2, k is odd} B(k)*B(n-1-k) if n is odd
: n?
|
b******n
发帖数: 823 | 10 (n-1)/2个inner node，
应该就是算(n-1)/2个node的tree有多少不同形态？因为对应一个形态，把leaf补满即是对应full binary tree了
【在 c**********e 的大作中提到】
: A binary tree is full if all of its vertices have either zero or two
: children. Let B_n denote the number of full binary trees with n
: vertices. What is B_n?
|
b******v
发帖数: 1493 | 11 这个是不会重复的
我的想法是根节点的左子树，右子树分别都是完全二叉树
假设左边是k个节点的完全二叉树，右边则是n-1-k个节点的完全二叉树
而k的可能取值是从1到n-2所有的奇数
【在 t*****j 的大作中提到】
: 而且比我那个算重复的数目还多。。
|
a**********k
发帖数: 1953 | |
b******v
发帖数: 1493 | 13 多谢，学习了
【在 a**********k 的大作中提到】
: google
: Catalan number
|
