получить среднее значение из дерева узлов

Question

Я должен реализовать этот метод:

public int GetAverage(Node root){ 
    //TODO implement 
} 

этот метод должен получить среднее значение всех узлов корня дерева. где:

public interface Node { 
    int getValue(); 

    List<Node> getNodes(); 
} 

у вас есть идеи, как реализовать этот метод?

спасибо

моя попытка:

public static double value; 
public static int count; 
public static double getAverage(Node root) { 
count++; 
value += root.getValue(); 
for (Node node : root.getNodes()) { 
getAverage(node); 
} 
return value/count; 
} 

, но как сделать это без статических полей вне метода?

Answer 1

public static double getAverage(Node root) { 
    Pair p = new Pair(0,0); 
    algo(root, p); 
    return ((double) p.element1)/((double) p.element2); 
} 

private static void algo(Node root, Pair acc) { 
    for(Node child : root.getNodes()) { 
     algo(child, acc); 
    } 
    acc.sum += root.getValue(); 
    acc.nbNodes++; 
} 

парной определяются следующим образом:

public class Pair { 

    public int sum; 
    public int nbNodes; 

    public Pair(int elt1, int elt2) { 
     this.sum = elt1; 
     this.nbNodes = elt2; 
    } 

} 

Answer 2

Просто пройти через все узлы и запомнить количество и общую сумму всех значений. Затем вычислите среднее значение. Это пример, написанный на Java.

public interface INode { 
    int getValue(); 

    List<INode> getNodes(); 
} 

public class Node implements INode { 
    private List<INode> children = new ArrayList<INode>(); 
    private int value; 

    @Override 
    public int getValue() { 
     return value; 
    } 

    @Override 
    public List<INode> getNodes() { 
     return children; 
    } 

    public static int getAverage(INode root) { 
     if (root == null) 
      return 0; 

     Counter c = new Counter(); 
     calculateAverage(root, c); 

     return c.sum/c.count; 
    } 

    class Counter { 
     public int sum; 
     public int count; 
    } 

    private static void calculateAverage(INode root, Counter counter) { 
     if (root == null) 
      return; 

     counter.sum += root.getValue(); 
     counter.count++; 

     // recursively through all children 
     for (INode child : root.getNodes()) 
      calculateAverage(child, counter); 
    } 
}