如何计算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？

b）我怎样才能最终将它们加在一起？每次有三个节点，两个节点有两个元组，等等，我得到三个单独的（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)