計數數字操作系統BST

Question

有人可以解釋我們如何計算可能的BST在這裏。我理解我們依賴實際左樹和右子樹數來獲得總數的基本部分。我很難理解循環。

public static int countTrees(int numKeys){ 
    if(numKeys<=1){ 
     return(1); 
    } 
    else{ 
     // there will be one value at the root, with whatever remains 
     // on the left and right each forming their own subtrees. 
     // Iterate through all the values that could be the root... 
     int sum=0; 
     int left,right,root; 
     for(root=1;root<=numKeys;root++){ 
      left=countTrees(root-1); 
      right=countTrees(numKeys-root); 
      // number of possible trees with this root == left*right 
      sum+=left*right; 
     } 
     return(sum); 
    } 
} 

Answer 1

顯然這與二叉搜索樹，特別是二叉樹無關，但一般來說，二叉樹。該實現使用歸納參數來計算可能的二叉樹數量，並用n節點進行計數。

第一種情況是基本情況，其中一個onr沒有節點可能可能被排列到一棵樹中。

第二種情況通過假設出n節點的計數的節點的數目，每個節點可以是根，這意味着剩餘n-1節點將被分配到左和右子樹，其中，所有可能的conbinations的分佈是遞歸評估的;注意顯然節點是有區別的，這意味着同構樹被多次計數。

在遞歸評估左右子樹的可能實現之後，最終的可能性被相乘以獲得整個樹的可能實現的總數。

作爲一個例子，假設您想評估3節點的樹數，對應節點集{1,2,3}。該數字大於1 ，並且這些節點中的每一個都可以是根，從而導致該循環進行3次迭代，如下所示。

1 is the root, 2 remaining nodes to distribute. 
2 is the root, 2 remaining nodes to distribute. 
3 is the root, 2 remaining nodes to distribute. 

爲2節點的評估將是相同的，所以我們擴大呼叫只是第一個電話。對於2節點，對應節點集{1,2}。該數字大於1，導致循環進行如下2次迭代。

1 is the root, 1 remaining node to distribute. 
2 is the root, 1 remaining node to distribute. 

爲1節點的evaulations將是相同的，即會出現正好1可能性。

1 is the root, 1 remaining node to distribute; 
the 1 node can be in either the left or the right subtree, 
resulting in 1 possiblity each, which is 2 possibilities in total. 

這意味着，對於一個呼叫爲2節點結果將是2。

回到上面的評估，我們獲得以下內容。

1 is the root, 2 remaining nodes to distribute; 
    possibilites: 
    2 in the left subtree, 0 in the right subtree; 
     results in 4*1 = 4 possibilities. 
    1 in the left subtree, 1 in the right subtree; 
     results in 1*1 = 1 possibilities. 
    0 in the left subtree, 2 in the right subtree; 
     results in 1*4 = 4 possibilities. 

總結這些possibilites，有4 + 1 + 4 = 9種可能性只要根選擇安排與3節點樹;然而，總共有3方式來選擇根，這給出了總結果。

1 is the root, 2 remaining nodes to distribute; 
    results in 9 possibilites. 
2 is the root, 2 remaining nodes to distribute; 
    results in 9 possibilites. 
3 is the root, 2 remaining nodes to distribute; 
    results in 9 possibilites. 

如果這些總結出來的，這是在總9+9+9=27可能的樹。