创建具有n个节点和L个叶节点的AVL树的方法数量 [英] Number of ways to create an AVL Tree with n nodes and L leaf node

问题描述

我想知道几种创建n个节点和L个叶节点的平衡二叉树的方法。

I'd like to know number of ways I can create a Balanced Binary Tree with n nodes and L leaf nodes .

我也知道n必须是（ 2 * L-1）。

also I know that n must be ( 2*L - 1 ) .

推荐答案

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

A balanced binary tree is a tree such that given any node, the two subtrees of that node has their height differing by at most one. So the number of nodes is not necessarily 2^L -1. If a tree has 2^L-1 nodes, then it is by definition, a full binary tree. So to answer your question.. If order does matter.. there are (n choose 1) ways (or n ways) to choose the top node. Then since order does matter, there are (n-1 choose 2) choices to choose the children of that node. And so on so forth. So it would be (n choose 1) *(n-1 choose 2) * (n-3 choose 2) * .... until n = 1 or 0.

如果顺序无关紧要。.
顶部节点仍然相同。您仍将拥有（n个选择1个）顶部节点的选择。对于该节点的一个子节点，我们有n-1个选择，选择之后，另一个子节点有n-2个选择。然后我们继续，直到用尽所有选择。因此在这种情况下，将存在n *（n-1）*（n-2）... = n！

If order doesn't matter.. the top node is still the same. You'll still have (n choose 1) choices for the top node. For one of the children of that node, we have n-1 choices and after we choose that, we have n-2 choices for the other child. Then we continue until we run out of choices. So in this case there would be n*(n-1)*(n-2)... = n! ways

----编辑---
实际上我犯了一个错误。总节点数不一定是2 ^ L -1。给定n个节点，树的高度为floor（lg（n））。叶节点的数量与树中节点的总数没有关系。

----Edit--- Actually I made a mistake. the number of total nodes is not necessarily 2^L -1. Given n nodes, the height of a tree is floor(lg(n)). The number of leaf nodes has no correlation to the total number of nodes in the tree.

这篇关于创建具有n个节点和L个叶节点的AVL树的方法数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！