我想知道有多少种方法可以创建具有 n 个节点和 L 个叶节点的平衡二叉树。
我也知道 n 必须是 (2*L - 1) 。
问问题
2526 次
1 回答
1
平衡二叉树是一棵树，使得给定任何节点，该节点的两个子树的高度最多相差一个。所以节点数不一定是2^L -1。如果一棵树有 2^L-1 个节点，则根据定义，它是一棵完整的二叉树。所以回答你的问题.. 如果顺序确实很重要.. 有（n 选择 1）种方式（或 n 种方式）来选择顶部节点。然后由于顺序确实很重要，因此有 (n-1 选择 2) 个选项来选择该节点的子节点。依此类推。所以它将是 (n 选择 1) *(n-1 选择 2) * (n-3 选择 2) * .... 直到 n = 1 或 0。
如果顺序无关紧要..顶部节点仍然相同。对于顶部节点，您仍然有（n 选择 1）个选项。对于该节点的其中一个孩子，我们有 n-1 个选择，在我们选择之后，我们有 n-2 个选择给另一个孩子。然后我们继续，直到我们没有选择。所以在这种情况下会有 n*(n-1)*(n-2)... = n! 方法
----编辑--- 其实我犯了一个错误。总节点数不一定是 2^L -1。给定 n 个节点，树的高度是 floor(lg(n))。叶节点的数量与树中的节点总数无关。
于 2012-11-22T00:37:43.980 回答