c++ - n 个元素的二叉搜索树的数量

Question

我需要在 n 个元素上找到许多不同的二叉搜索树。我知道，n 个不同元素的二叉搜索树的数量是加泰罗尼亚数。但如果数字可以重复怎么办？在二叉搜索树中，左子树的元素小于根，右子树的元素等于或大于根。

这是我的代码，用于计算 n 个元素上的多个不同的二叉搜索树。我通过模 123456789 来计算这个数字，因为它可能非常大。我可以简单地改变它来解决我的问题吗？

#include <algorithm>
#include <vector>
#include <iostream>
#include <limits>

using std::vector;
using std::cin;
using std::cout;
using std::endl;


long long countTreeDP(int nodeNumber) 
{
    vector <vector<long long> > cNumbers;
    for (int i = 0; i < nodeNumber + 2; ++i)
    {
        vector<long long> cur(nodeNumber + 2, 0);
        cNumbers.push_back(cur);
    }
    for (int i = 0; i < nodeNumber + 2; ++i)
    {
        cNumbers[i][0] = 1;
    }

    long long sum = 0;
    for (int i = 1; i < nodeNumber + 1; ++i) 
    {
        sum = 0;
        for (int j = 1; j <= i; ++j) 
        {
            long long numFirst = cNumbers[nodeNumber + 1][i - j] % 123456789;
            long long numSecond = cNumbers[nodeNumber + 1][j - 1] % 123456789;
            cNumbers[j][i] = (numFirst * numSecond) % 123456789;
            sum += cNumbers[j][i];
            sum = sum % 123456789;
        }
        cNumbers[nodeNumber+1][i] = sum;
    }

    return cNumbers[nodeNumber+1][nodeNumber];
}

int main()
{
    vector<long long> nodesValues;
    int size = 0;
    cin >> size;

    for (int i = 0; i < size; ++i)
    {
        long long elem;
        cin >> elem;
        nodesValues.push_back(elem);        
    }

    std::sort(nodesValues.begin(), nodesValues.end());

    int uniqueCount = 0;

    for (int i = 1; i < nodesValues.size(); ++i)
    {
        if (nodesValues[i] != nodesValues[i-1])
            ++uniqueCount;
    }
    cout << countTreeDP(uniqueCount + 1) << endl;
    system("pause");
    return 0;
}

Answer 1

我假设 a[i]对于 0 ≤ i < n是节点值的排序数组。这就是我要做的:创建一个二维表 T这样条目 T[x][y]计算子序列 x ≤ i < y 的搜索树数量。您可以通过设置所有 T[i][i] 来初始化它对于 0 ≤ i ≤ n为 1，因为空序列只有一棵搜索树，即空树。

现在您将编写三个嵌套循环。最外面的循环在序列长度上迭代，中间的循环在可能的起始位置上迭代，最里面的循环在可能的树节点上迭代。类似的东西

for (int len = 1; len <= n; ++len) {
  for (int pos = 0; pos <= n - len; ++pos) {
    int left = pos, right = pos + len;
    long long cnt = 0;
    for (int root = left; root < right; ++root) {
      if (root > left && a[root] == a[root - 1])
        continue; // duplicate element may not be root
      cnt += T[left][root]*T[root + 1][right];
    }
  }
}

上面的代码在没有 if 的情况下也可以工作。对于不同元素的情况。如果可以有重复的元素，则只有当该元素之前的元素严格小于该元素本身，或者它是子树的第一个元素时，该元素才能被视为子树的根(根据您的定义)。所以上面的检查会跳过无效的根，所以最后T[0][n]将保留您想要的计数。

我将把模算术留给你。我还将让您将这个想法与您自己编写的代码进行比较，因为我现在不想阅读那么多未注释的代码。