有多少种方法构建完全平衡树？
问题是，有多少种方法可以构建一个包含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
4 个回答
可能会有一个公式可以找到。可以用一个小树来看看有多少种可能性。
比如说，对于3个不同的元素，只有1种可能的树。
对于4个元素，有2种可能。
对于5个元素，有3种可能。
对于6个元素，只有2种可能（3和4作为根，其他的都是隐含的）。
对于7个元素，只有1种可能。
对于15个元素，给定一个根节点，有14个元素需要放置，这恰好是7+7，这种情况只有一种形式可以表示，所以我猜你的问题是只有一个解决方案，根节点是8。
我不太明白你说的“完美平衡”是什么意思。不过如果你指的是每个节点的左边和右边的节点数量是相等的，那对于15个元素[1-15]，你可以构建这样一棵树，因为四层的完全二叉树正好有15个元素。
从你的问题来看，你似乎是想问完全二叉搜索树。对于15个元素（1-15），只有一种这样的树可以构建。
想想根节点可以放什么数字。1到15的中间值是什么？就是8，只有8可以放在根节点上。如果你用归纳法思考，你会发现所有节点只有一个可能的值。
正确的数字是21964800。这个数字对应的整数序列是：
简单来说，你需要不断地把可能性相乘：在最底层，你可以选择两种可能的组合，比如：2-1-3和2-3-1。在上面一层，你可以把下面两层选择的顺序结合在一起，有(6选3)种方式，依此类推。