时间戳

首页 > 解决方案 > n 个节点可以生成多少个非同构完整二叉树？

algorithm - n 个节点可以生成多少个非同构完整二叉树？

问题描述

同构意味着交换自己的完整二叉树的任意子树可以与另一棵相同。

答案肯定不是加泰罗尼亚数，因为加泰罗尼亚数的数量包括同构数。

标签： algorithmmathtree

解决方案

我假设n节点是指n内部节点。所以它会有2n+1顶点和2n边。

接下来，我们可以对二叉树进行排序，如下所示。具有更多节点的树更大。如果两棵树的节点数相同，则比较左侧，并通过比较右侧来打破平局。如果两棵树按此顺序相等，则通过归纳法不难证明它们是同一棵树。

对于您的问题，我们可以假设对于每个同构类，我们只对该同构类中的最大树感兴趣。请注意，这意味着左子树和右子树在它们的同构类中也必须是最大的，并且左子树必须与右子树相同或大于右子树。

所以假设这是具有节点f(n)的非同构二叉树的数量。n我们现在可以递归了。以下是我们的案例：

  1. n=0有一棵，空树。
  2. n=1有一个。一个有 2 片叶子的节点。
  3. n > 1. 让我们迭代m，右边的数字。如果然后在右边，左边2m+1 < n有最大的树，所有这些都是最大的。如果我们想要一个在右边有节点的最大树，在左边有一个有节点的最大树，右边的树必须小于或等于左边的树。但是有一个众所周知的公式可以说明有多少种方法可以做到这一点，那就是. 最后我们不能有，因为在那种情况下我们没有最大的树。f(m)f(n-m-1)f(m) * f(n-m-1)2m+1 = nmmf(m) * (f(m) + 1) / 2n < 2m+1

使用它，您应该能够编写一个递归函数来计算答案。

更新这是一个这样的功能：

cache = {0: 1, 1:1}
def count_nonisomorphic_full_trees (n):
    if n not in cache:
        answer = 0
        for m in range(n):
            c = count_nonisomorphic_full_trees(m)
            if n < m+m+1:
                break
            elif n == m+m+1:
                answer = answer + c*(c+1)//2
            else:
                d = count_nonisomorphic_full_trees(n-m-1)
                answer = answer + c*d
        cache[n] = answer
    return cache[n]

请注意，它开始时比加泰罗尼亚数字慢，但仍呈指数增长。

推荐阅读