问题是，有多少种方法可以构建一个具有15个元素的完美平衡二叉树?
一种可能性将贝8-4-12-2-6-10-14-1-3-5-7-9-11-13-15 . .
我的想法是写一些代码来生成每一个可能的排列(就像…15!)，然后删除不正确的。
正确的是8作为第一个元素，4总是在2和6之前，2总是在1和3之前，6总是在5和7之前，等等。
但是像perms2 = list(itertools.permutations([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]))这样的东西会导致内存错误。
是否有一种方法可以使用上述规则生成排列?
或者有没有更简单的方法来解决我的问题?顺便说一句. .
- 如果元素数量为1，则有1种方法
- 3个元素有2种方式(2-1-3或2-3-1)
- 有7个元素，有80种方法(根据我的代码和手动执行)
但这并没有帮助我得到某种公式…
编辑:这是我正在谈论的树:http://666kb.com/i/bz9znnpdj7etw0fo9.gif
正确的数字是21964800。这是合适的整数序列:
http://oeis.org/A076615基本上你递归地乘以可能性:在最低级别，你可以在两种可能性中选择，例如:2-1-3和2-3-1。在上面一层，你可以将两个下层的选定顺序缠绕在(6/3)中方法等等。
我不太清楚你所说的完全平衡是什么意思。但如果你的意思是左右节点的数量相等对于每个节点，你有15个元素[1-15]，其中2^4 -1个元素，你可以得到这样一个树。因为一个完全的四层二叉树正好有15个元素。
同样从你的问题看来，你指的是一个完整的二叉搜索树。对于15个元素(1-15)，只有一个这样的树是可能的。
考虑根节点中可以包含的内容。1-15的中位数是多少?只有8和8。所以根上只能有8。如果你使用归纳，你会得出结论，所有的节点只有一个可能的值
可能会找到一个公式。看一棵小树有多少种可能性。
例如，对于3个不同的元素，只有1棵可能的树。
对于4，有2
对于5，有3
对于6，只有2(3和4作为根，其余的是隐含的)
For 7，只有1.
对于15，给定一个根，有14个元素要放置，正好是7+7，它只能用一种形式表示，所以我猜你的问题是只有一个解，8是根
根据你对完美平衡的定义，所有的结构变化都发生在树的最深处，所以你只需要担心这一层。
高度为h的最大平衡树将有2^(h-1)个叶子——例如高度为1的树，唯一的叶子是根。这些都是最深层次的。
高度为h的最小平衡树在最深处只有一个节点。
因此，构建一棵完美平衡二叉树的方法数与在最深层1到2^(h-1)个节点之间的方法数相同。
有2^(h-1)个节点可能存在，也可能不存在(一个组合问题，不是排列问题)，所以你得到2^(2^(h-1))种可能性，其中只有一种("无"情况)是无效的。
所以我想你的答案是(2^(2^(h-1)))-1。所以如果你能确定正确的h…
这是假设二叉搜索树(项目值唯一且顺序一致)，因此二叉树完全由选择存在哪些最深层节点来决定。否则，将其乘以值序列的排列次数。
请注意我对h的定义-零高度树根本没有节点，并给出一个无意义的结果- sqrt(2)-1至少在两种意义上是一个不合理的答案。
编辑
马克的评论让我思考了更多。对于一个特定的高度，我想我的答案是正确的。问题是，一个特定的高度允许有不同数量的节点，因为它允许在最深处有不同数量的节点。所以我不能用这种方法得到一个特定节点数的正确答案。所以…让我们再试一次…如果我们的树的高度是h，它总共最多可以有(2^h)-1个节点。除了最深层，它有(2^(h-1))-1个节点——所有节点都必须存在。
我们在最深处有c-(2^(h-1))-1)个节点，我们要从最深处2^(h-1)个可能的位置中选择放置这些节点的位置。我用c表示计数，因为我想定义…
n = 2^(h-1)
k = c-((2^(h-1))-1)
answer = n choose k
我还没有从c中推导出h -它应该是以2为底的对数的底数，但我有一种超出1的感觉