Algorithm for aggregating values ​​from nodes of child trees

Question

I have objects in a tree structure, I would like to aggregate status information from child nodes and update the parent node with aggregated status. Suppose node A has children B1, B2 and B1 has C1, C2, C3 as children. Each of the nodes has a status attribute.

Now, if C1, C2, C3 are completely full, I would like to mark B1 as completed. And if C4, C5, C6, C7 are complete, make B2 complete. When B1 and B2 are completed as full label A.

I can use these nodes in brute force method and make updates, can someone suggest an efficient algorithm for this.

A {B1 {C1, C2, C3}, Bi 2 {C4, C5, C6, C7}}

Answer 1

: node, node, .

- ():

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

Answer 2

, - .

, . , "", complete node.

, complete . . - :

class NodeWithCompletenessInfo : public Node {

  private bool internalComplete; // Am I personally done?
  private bool childrenComplete; // Are my children done?

  public bool isComplete() {
    return internalComplete && childrenComplete;
  }

  public void markComplete() {
    internalComplete = true;
    if( isComplete() )
      parent.markChildComplete();
  }

  public void markIncomplete() {
    if( isComplete() )
      parent.markChildIncomplete();
    internalComplete = false;
  }

  private void markChildComplete() {
    for( child in children ) {
      if( !child.isComplete() )
        return;
      childrenComplete = true;
    }
    if( isComplete() )
      parent.markChildComplete()
  }

  private void markChildIncomplete() {
    if( isComplete() )
      parent.markChildIncomplete();
    this.childrenComplete = false;
  }
}

Answer 3

, ,

 A { 
    B1 
        {C1, C2 = false, C3},
    B2 
        {C4, C5=false, C6=false, C7} 
  } // those not marked false are true ;)

not_complete_leaf_nodes_with_different_parents = [ C2 , C5]

mark_not_complete(node):
    node.complete = false
    if parent != null
        mark_not_complete(node.parent)

for each in not_complete_leaf_nodes_with_different_parents:
    mark_not_complete(each.parent)

Answer 4

, " ".

.

http://www.javaworld.com/javaworld/javatips/jw-javatip98.html

http://sourcemaking.com/design_patterns/visitor