计算 n 个元素上所有可能根的高度为 h 的二叉搜索树的数量

Question

我有 n 个元素，例如 1,2,3,4....n。我想计算所有可能根的高度为 H 的可能二叉搜索树的数量

计算所有可能高度的二叉搜索树的数量：

int countTrees(int N) {

  if (N <=1) { 
    return(1); 
  } 
  else {
    int sum = 0; 
    int left, right, root;

    for (root=1; root<=N; root++) { 
      left = countTrees(root - 1); 
      right = countTrees(N - root);

      // number of possible trees with this root == left*right 
      sum += left*right; 
    }

    return(sum); 
  } 
}

在上面的程序中，我想添加高度H的约束

编辑： 例子-

Input N = 3 H = 3

我不想计算高度大于 H 的树

Total No. of tree 5
There are 2 trees with root =1, 1 tree with root =2, 2 trees with root =3

我的最终答案是10（所有根节点数的总和）因此，答案 = 1*2 + 2*1 + 3*2 = 10

Answer 1

方法可能是将第三个参数传递给 countTrees（高度）并添加一个条件，如果 h 大于某个值，只需 return（显然您可以在递归调用函数时增加该参数）

Answer 2

勾选http://ideone.com/okPqj9

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        System.out.println(countTrees(3, 1, 3));
    }

 public static int countTrees(int N, int curH, int H) {
  if ( curH > H ) return 0;

  if (N <=1) { 
    return(1); 
  } 
  else {
    int sum = 0; 
    int left, right, root;

    for (root=1; root<=N; root++) { 
      left = countTrees(root - 1, curH+1, H); 
      right = countTrees(N - root, curH+1, H);

      // number of possible trees with this root == left*right 
      sum += left*right; 
    }

    return(sum); 
  } 
} 
}

我不保证它是正确的，但总体思路 - 修剪所有高度大于 H

的树

这个算法对于大 N 来说很慢，有更快的解决方案（尽管没有 H 约束）：http://techieme.in/count-binary-search-trees/

Answer 3

你已经完成了90%以上的工作，让我来做剩下的。

我尽量保持大部分代码不变。

如果我们不想统计高度超过给定h的树的数量，我们干脆不调用相应的递归调用。

该函数将像这样从主函数中调用：

countTrees(3,2,0);

N = 3, H = 2 并且 0 是从根向下路径遍历的边数.

代码中数组arr长度为3，是全局的arr[i]会给出树的数量可能与 root i+1.

int countTrees(int N,int h,int l) {
  if (N <=1) { 
    return(1); 
  } 
  else {     
    int sum=0;
    int left, right, root;
    for (root=1; root<=N; root++) { 
      left=0;right=0;
      if(l+1<=h)
      {
      left = countTrees(root - 1,h,l+1); 
      right = countTrees(N - root,h,l+1);      
      if(l==0)
       arr[root-1]+=left*right;
      sum+=left*right;
      }
    }     
    return sum;
  } 
}

计算 n 个元素上所有可能根的高度为 h 的二叉搜索树的数量

count number of binary search tree of height h for all possible roots over n elements

c++

java

algorithm

tree

binary-search-tree