递归关系：写递归关系

Question

我正在尝试为此写一个递归关系 algorithm.But 我对 "root" variable.Can 感到困惑任何人帮助我或建议我一个更好的递归算法来计数具有 n 个节点的可能二叉树的数量？

Algorithm countTrees(n) {
    if(n<=1) then return 1
    else {
        sum = 0
        for root=1 to root<= n do {
            left = countTrees(root-1)
            right = countTrees(n-root)
            sum = sum+(left*right)
        }
        return sum
    }
}

到目前为止我已经写了这个但是我不知道如何处理根来解决这个问题。

T(n) = n[T(root-1)+T(n-root)]

Answer 1

你的代码已经是二叉树个数的递归关系，只是表示为算法。我猜你被困住了，因为你对一个循环进行了求和。这是标准数学符号——循环值从 1..n 更改为 0..n-1 更标准：

C(0) = C(1) = 1
C(n) = sum(C(i) * C(n-i-1) for i = 0...n-1)

手写（或使用 LaTeX）您会使用求和符号而不是 sum，但逻辑上是相同的。

这是 Catalan numbers 的递归关系（尽管通常不会明确列出 C(1) 的情况）并且链接的维基百科页面还包括递归关系的封闭形式解决方案和其正确性的证明。

递归关系：写递归关系

Recurrence Relation: Writing a recurrence relation

algorithm

recursion

binary-tree

catalan