计算可能的子树数

Question

给定一个n元树，我们如何计算以特定节点为根，并包含至少一条边的所有可能子树的数量。

Answer 1

导线通过DFS树，并计算出可能的子树，每棵树的数量：

def _count_subtrees(node): 
    result = 1 

    # multiply the number of possibilities for each subtree 
    # to get the total number of possible subtrees 
    while node.has_more_children(): 
     result *= count_subtrees(node.next_child()) 

    # allow the empty subtree 
    return result + 1 

def count_subtrees(node): 
    # two of the counted subtrees are invalid: the tree containing only 
    # the root and the empty tree 
    return _count_subtrees(node) - 2 

给定节点可能的子树的数量是可以从所有的孩子乘以建立可能的子树的数量与彼此。

考虑三个孩子，a，b和节点n，针对可能的子树的集A，B和C的c。那么对于n一组可能的子树是

N = { {n} x A x B x C } + {} 

随着基数|N| = |A| * |B| * |C| + 1。

现在，因为我们需要消除两种情况下的树的根：

• 空树
• 只包含n

这样子树：

_S(leave) = 2 # two valid subtrees: empty tree and only 'leave' 
_S(n) = S(c1(n)) * S(c2(n)) * ... + 1 
S(n) = _S(n) - 2 

计算可能的子树的数量是正确的重现给定节点