查找給定n個鍵的二叉樹數量的變化

給定一個列表A的n不同的鍵，可以形成多少二叉搜索樹使得在任何子樹中，節點數目之間的差異它的左邊和右邊的子樹最多一個在？查找給定n個鍵的二叉樹數量的變化

爲二叉搜索樹數遞推關係不條件是

f(1) = f(0) = 1; 
Let total_trees = 0; 
for(int i = 1; i<= n; ++i) 
    total_trees += f(i-1) * f(n-i)

任何人都可以使用的變化幫助嗎？

我嘗試（這是錯誤的）：

f(1) = f(0) = 1; 
Let total_trees = 0; 
for(int i = 1; i<= n; ++i) 
    total_trees += f(i) * f(i-1)

2012-04-01 Sunny Raj

如果這是作業，請相應標記。 – 2012-04-01 23:54:28

@Adam這不是一個家庭作業。我正在準備考試。如果有必要，我會提供一個鏈接，說這個問題是爲了練習。 – 2012-04-02 00:00:56

到目前爲止你有什麼想法？ – svick 2012-04-02 11:17:48

讓我們所有的按鍵都是線性陣列。如果鍵的數量是偶數，則有2個變體的根 - 2箇中心元素。對於奇數個鍵，只有一個以中心元素作爲根的變體來滿足條件。所以遞歸看起來像：

F（1）= F（0）= 1架

F（2 * K）= F（K-1）×F（K + 1）+ F（K + 1 ）* F（K-1）= 2 * F（K-1）×F（K + 1）

F（2 * K + 1）= F（k）的* F（k）的

2012-04-02 12:26:39 MBo

回答