查找二叉搜索樹中每個深度的節點數量

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 它將每個級別的計數保存在散列映射中，然後計算一些統計數據。

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); 
    } 
}