2

我需要在 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;
}
4

1 回答 1

4

我假设a[i]for0 ≤ i < n是您排序的节点值数组。这是我要做的：创建一个二维表T，以便 entryT[x][y]计算 subsequence 的搜索树的数量x ≤ i < y。您可以通过将 all T[i][i]for设置为0 ≤ i ≤ n1 来初始化它，因为空序列只有一棵搜索树，即空树。

现在您将编写三个嵌套循环。最外面的循环遍历序列长度，中间的循环遍历可能的起始位置，最里面的循环遍历可能的树节点。就像是

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]会保留你想要的计数。

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

于 2013-11-24T15:40:04.317 回答