Как рассчитать количество листьев с n листьями?

Question

Предположим, у меня есть дерево, где каждый узел может иметь от 0 до 3 листьев.

Я хочу, чтобы пройти через дерево, и возвращает кортеж (a, b, c) где a = nodes with 1 leaf, b = nodes with 2 leafs и c = nodes with 3 leafs.

Мой общий код рекурсивной, и выглядит следующим образом:

treeNode(tree, (a, b, c)) = 
    if tree = Empty 
    return (a, b, c) 
    else if tree = Node(n1, n2, n3) 
    if n1 = tree and n2 = tree and n3 = tree 
     treeNode(n1, (a, b, c + 3)) + treeNode(n2, (a, b, c + 3)) + treeNode(n3, (a, b, c + 3)) 
    else if ... 

---

В тот момент, я не знаю, как идти дальше. Я застрял на двух частях.

a) Как я могу назвать рекурсивную функцию три раза без перекрытия? Я предполагаю добавить 1/3 вместо 3 и 1/2 вместо 2, когда есть два узла?

б) Как я могу в итоге добавить их все вместе? Я получаю три отдельных набора (a, b, c) каждый раз, когда есть три узла, два кортежа для двух узлов и т. Д. Я не могу использовать временные переменные в SML, поэтому я не могу обойти это.

---

Любые идеи о наилучшем способе выполнения этой функции? Я пытаюсь придерживаться рекурсии, и я думал о вызове различных функций, когда есть несколько узлов, но это означает, что мы пересекаем дерево несколько раз, и я не хочу, чтобы он был неэффективным.

Answer 1

Что-то в этом роде?

псевдокод:

# returns triple (a,b,c) of counts of nodes with 1,2 and 3 subtrees 
f(T): 
    result = (0,0,0) 

    if T.nodes.length == 0: 
    return result 

    for node in T.nodes: 
    combine result with f(node) 

    result[ T.nodes.length ] += 1 

    return result 

Пример:

  Node # returns answer (0,1,1) + 1 in position a = (1,1,1) 
     /
     Node # returns (0,0,0) + (0,0,1) + 1 in position b 
    / \ 
    Node Node # return (0,0,0) and (0,0,1) 
     /| \ 
      N N N # each return (0,0,0)