有多少种方法可以构建完美平衡的树？
问题是，有多少种方法可以构建具有 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
The question is, how many ways are there to build a perfectly balanced binary tree with 15 elements?
One possibility would bei 8-4-12-2-6-10-14-1-3-5-7-9-11-13-15..
My idea was to write some code that generates every possible permutation (which would be like.. 15!) and then remove the ones that are incorrect.
Correct ones have the 8 as the first element, 4 always comes before 2 and 6, 2 always comes before 1 and 3, 6 always comes before 5 and 7 and so on.
But something like perms2 = list(itertools.permutations([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15])) causes a memory error.
Is there a way to generate permutations with the rules as above?
Or is there even a more simple way to solve my problem?
Btw..
- if the amount of elements is 1, there is 1 way
- with 3 elements there are 2 ways (2-1-3 or 2-3-1)
- with 7 elements there are 80 ways (according to my code and doing it manually)
but that didn't help me to get some kind of formula..
Edit: this is the tree i am talking about: http://666kb.com/i/bz9znnpdj7etw0fo9.gif
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
正确的数字是 21964800。这是适当的整数序列：
http://oeis.org/A076615
基本上你递归地乘以可能性：
在最低级别，您可以在两种可能性之间进行选择，例如：2-1-3 和 2-3-1。在上面的级别上，您可以将两个较低层的所选顺序纠缠在（6 over 3）中
方式等等。
The correct number is 21964800. This is the appropriate integer sequence:
http://oeis.org/A076615
Basically you recursively multiply the possibilities:
On the lowest level you can choose between two possibilities, e.g: 2-1-3 and 2-3-1. On the level above that you can entangle the chosen order of both lower layers in (6 over 3)
ways and so on.
我不确定你所说的完美平衡是什么意思。但是，如果您的意思是每个节点的左右节点数量都相等，并且您有 15 个元素 [1-15]，其中 2^4 -1 个元素，您可以拥有这样一棵树。因为四层完全二叉树正好有 15 个元素。
另外从你的问题来看，你的意思似乎是一个完整的二叉搜索树。对于 15 个元素 (1-15)，只有一棵这样的树可能。
考虑根节点中可以包含哪些内容。 1-15 的确切中位数是多少？只有8和8。所以根只能是8。如果你使用归纳法，你会得出结论：所有节点只有一个可能的值
I am not sure what you mean by perfectly balanced. But if you mean both number of left and right nodes are equal for every node and you have 15 elements [1-15] which 2^4 -1 elements you can have a such a tree. Because a complete binary tree of four levels exactly has 15 elements.
Also from your question it seems like you mean a complete binary search tree. With 15 elements ( 1-15) there is only one such tree possible.
Consider what can go in the root node. What number is the exact median of 1-15. It is 8 and 8 only. so only 8 can be at the root. And if you use induction you will conclude that all nodes only have one possible value
或许可以找到一个公式。看看一棵小树有多少可能性。
例如，对于 3 个不同的元素，只有 1 棵可能的树。
对于 4，有 2 个
对于 5，有 3 个
对于 6，只有 2 个（3 和 4 作为根，其余是隐含的）
对于 7，只有 1 个。
对于 15，给定一个根，需要放置 14 个元素，恰好是 7+7，只能以一种形式表示，所以我对你的问题的猜测是只有一种解决方案，而 8 是根。
There is probably a formula to be found. See with a small tree how many posibilities there are.
For example, for 3 different elements, there is only 1 possible tree.
For 4, there are 2
For 5, there are 3
For 6, there are only 2 (3 and 4 as root, the rest is implied)
For 7, only 1.
For 15, given a root, there are 14 elements to place, which happens to be 7+7, which is representable in only one form, so my guess as to your problem is that there is only one solution, and 8 is root.
根据您对完美平衡的定义，结构的所有变化都发生在树的最深层，因此您只需要担心这一层。
高度为 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 至少在两个意义上是一个不合理的答案。
编辑
Marc的评论让我思考更多。对于特定的高度，我认为我的答案是正确的。问题是特定的高度允许有各种不同数量的总节点，因为它允许最深层中有各种不同数量的节点。因此，我无法通过这种方式获得某个特定节点数的正确答案。所以...让我们再试一次...
如果我们的树的高度为 h，那么它总共最多可以有 (2^h)-1 个节点。不包括最深的级别，它有 (2^(h-1))-1 个节点 - 所有这些节点都必须存在。
我们在最深层有 c-((2^(h-1))-1) 个节点，我们可以从最深层的 2^(h-1) 个可能位置中选择将这些节点放置在哪里。我使用 c 进行计数，因为我想定义...
answer = n 选择 k
我仍然还没有从 c 导出 h - 它应该是以 2 为底的对数的下限，但我有一种一一对应的感觉。
With your definition of perfectly balanced, all the variation in structure happens at the deepest level of the tree, so you only need to worry about that one level.
A maximal balanced tree with height h will have 2^(h-1) leaves - e.g. for height 1, the only leaf is the root. These are all at the deepest level.
A minimal balanced tree with height h has only one node at the deepest level.
The number of ways you can construct a perfectly balanced binary tree is therefore the same as the number of ways you can have between 1 and 2^(h-1) nodes at the deepest level.
There are 2^(h-1) nodes that may or may not be present at that level (a combinations problem, not permutations), so you get 2^(2^(h-1)) possiblilities, of which only one (the "none" case) is invalid.
So I think your answer is (2^(2^(h-1)))-1. So if you can determine the correct h...
That's assuming a binary search tree (with item values unique and in order), so the binary tree is fully determined by the choice of which deepest-level nodes are present. Otherwise, you multiply that by the number of permutations of the sequence of values.
Take care with my definition of h - a zero-height tree would have no nodes at all, and give a nonsense result - sqrt(2)-1 is an irrational answer in at least two senses.
EDIT
Marcs comment made me think some more. For a particular height I think my answer is right. The problem is that a particular height allows various different numbers of total nodes, because it allows various different numbers of nodes in that deepest layer. So I can't get the correct answer for one particular node count this way. So... lets try again...
If our tree has height h, it can have at most (2^h)-1 nodes in total. Excluding the deepest level, it has (2^(h-1))-1 nodes - all of which must be present.
We have c-((2^(h-1))-1) nodes at the deepest level, and we get to choose where to put those nodes from the 2^(h-1) possible positions at the deepest level. I use c for count, because I want to define...
answer = n choose k
I still haven't derived h from c - it should be the floor of the base 2 logarithm, but I have that out-by-one-somewhere feeling.