algorithm - 创建具有 n 个节点和 L 个叶节点的 AVL 树的方法数

Question

我想知道有多少种方法可以创建具有 n 个节点和 L 个叶节点的平衡二叉树。

我还知道 n 必须是 ( 2*L - 1 )。

Answer 1

平衡二叉树是这样一棵树，给定任何节点，该节点的两个子树的高度最多相差一个。所以节点数不一定是2^L -1。如果一棵树有 2^L-1 个节点，那么根据定义，它就是一棵满二叉树。所以回答你的问题..如果订单确实重要..有 (n choose 1) 种方式(或 n 种方式)选择顶端节点。然后，由于顺序很重要，因此有 (n-1 choose 2) 个选项来选择该节点的子节点。依此类推。所以它将是 (n 选择 1) *(n-1 选择 2) * (n-3 选择 2) * .... 直到 n = 1 或 0。

如果顺序不重要..顶级节点仍然是相同的。对于顶级节点，您仍然有 (n choose 1) 个选择。对于那个节点的一个 child ，我们有 n-1 个选择，在我们选择了那个之后，我们对另一个 child 有 n-2 个选择。然后我们继续，直到我们用完选择。所以在这种情况下会有 n*(n-1)*(n-2)... = n!方法

----编辑---其实我犯了一个错误。总节点数不一定是 2^L -1。给定 n 个节点，树的高度为 floor(lg(n))。叶子节点的个数与树中的节点总数没有相关性。