java - 从子树节点聚合值的算法

Question

我在树结构中有对象，我想聚合子节点的状态信息并使用聚合状态更新父节点。假设节点 A 有 child B1、B2，而 B1 有 C1、C2、C3 作为 child 。每个节点都有一个状态属性。

现在，如果 C1、C2、C3 都已完成，那么我想将 B1 标记为已完成。如果 C4、C5、C6、C7 完整，则使 B2 完整。当 B1 和 B2 都完成时，将 A 标记为完成。

我可以用强力方法遍历这些节点并进行更新，有人可以建议一种有效的算法来做到这一点。

一个{ B1 { C1, C2, C3}, B2 { C4, C5, C6, C7}

Answer 1

您需要后序遍历 - 首先访问节点的子节点，然后递归地标记节点本身。

类似于(伪代码):

iscomplete(node):
  if node == Null:
     return False
  elsif no children:
     return some "complete" value according to node value
  else:
     for child in node.children:
         if not iscomplete(child):
             return False

  return True