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

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

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

2012-11-21 Dilon Duuuman

你的意思是你可以爲你插入到AVL樹中的對象設置多少個排序？ – zbrunson

不，假設我們畫一個圖來展示一個有n個節點和L個葉節點的AVL樹。 –

你的意思是一個完全平衡的2^k-1頂點的二叉樹（對於某些k）？你的意思是一個近似平衡的[2 ^（k-1），2^k-1]頂點的二叉樹嗎？你的意思是一個準平衡二叉樹的紅黑樹或AVL樹嗎？排序是否重要？ – Rafe

平衡二叉樹是一棵樹，給定任何節點時，該節點的兩個子樹的高度相差至多一個。所以節點的數量不一定是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-22 00:37:43 Calpis

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

回答

相關問題