Поиск количества узлов для каждой глубины в двоичном дереве поиска

Question

Им интересно узнать, как определить количество узлов на глубину?

У меня есть максимальная глубина код, который выглядит, как этот

int maxDepth(BinNode n) { 
    if (n == null) { 
     return (0); 
    } else { 
     // compute the depth of each subtree 
     int leftDepth = maxDepth(n.venstre); 
     int rightDepth = maxDepth(n.hoyre); 
     // use the larger one 
     if (leftDepth > rightDepth){ 
      return (leftDepth + 1); 
     } 
     else{ 
      return (rightDepth + 1); 
     } 
    } 
} 

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

Answer 1

У меня была такая задача в моем университетском классе. Full Code Сохраняет счетчик для каждого уровня в hashmap и затем вычисляет некоторую статистику.

private int maxDepth; 
private int sum; 
private Map<Integer, Integer> map; 

public void statistik() { 
    maxDepth = 0; 
    sum = 0; 
    map = new HashMap<>(); 
    statistikR(root, 0); 

    System.out.println("max:" + maxDepth); 
    System.out.println("sum:" + sum); 
    double average = 0; 
    for (int key : map.keySet()) { 
     // key = level, value = count per level 
     average += (key * map.get(key)); 
    } 
    System.out.printf("avg: %.2f%n", (average/sum)); 

} 

private void statistikR(Node p, int depth) { 
    if (p != null) { 
     ++sum; 
     if (depth > maxDepth) 
      maxDepth = depth; 

     if (!map.containsKey(depth)) 
      map.put(depth, 0); 
     int countPerLevel = map.get(depth).intValue(); 
     map.put(depth, ++countPerLevel); 

     ++depth; 

     statistikR(p.left, depth); 
     statistikR(p.right, depth); 
    } 
}