Comptage du nombre de sous-arbres possibles

Question

Étant donné un arbre n-aire, comment compter le nombre de sous-arbres possibles enracinés sur un nœud particulier et contenant au moins une arête.

Answer 1

Traverse l'arbre via DFS et calculer le nombre de sous-arbres possibles pour chaque arbre:

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 

Le nombre de sous-arbres possibles pour un noeud donné est le nombre de sous-arbres possibles qui peuvent être construits à partir de tous les enfants multipliés avec l'un l'autre.

Tenir compte trois enfants, a, b et c d'un nœud n, pour lequel les ensembles de sous-arbres sont possibles A, B et C. Ensuite, l'ensemble des sous-arbres possibles pour n est

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

Avec cardinalité |N| = |A| * |B| * |C| + 1.

Maintenant, pour la racine de l'arbre, nous devons éliminer les deux cas:

• le sous-arbre vide
• le sous-arbre qui ne contient que n

Ainsi:

_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 

La récurrence correcte pour calculer le nombre de sous-arbres possibles pour un noeud donné