计数数字操作系统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可能的树。