有 Java 编程相关的问题?

你可以在下面搜索框中键入要查询的问题!

java在二叉搜索树中查找每个深度的节点数

我想知道如何找到每个深度的节点数

我有一个最大深度代码,看起来像这样

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

我想要的是一个代码,可以计算每个深度级别的节点数量


共 (1) 个答案

  1. # 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);
        }
    }