algorithm - n片叶子怎么计算叶子的个数？

Question

假设我有一棵树，其中每个节点可以有 0-3 个叶子。

我想遍历树，并返回一个元组 (a, b, c) 其中 a = nodes with 1 leaf, b = nodes有 2 个叶子，c = 有 3 个叶子的节点。

我的一般代码是递归的，看起来像这样:

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)