創建具有n個節點和L葉節點的AVL樹的方法數量

Question

我想知道有多少種方法可以創建具有n個節點和L個葉節點的平衡二叉樹。

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

Answer 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））。葉節點的數量與樹中節點的總數不相關。