如何统计四叉树表示的位图中指定颜色的像素数？是否用BFS？

嘿，这个问题其实很好理清～首先得先搞懂四叉树的节点逻辑，然后再选遍历方法就一目了然了！

四叉树里的节点分两种，这是统计的关键：

• 叶子节点：对应一块纯色的像素区域，只要颜色和目标匹配，直接加上这块区域的像素总数就行
• 内部节点：本身没有颜色，需要遍历它的四个子节点（对应左上、右上、左下、右下四个象限），把每个子节点的统计结果加起来

两种方法都能用，没有绝对的优劣，看你的场景：

• DFS（深度优先，递归实现）：代码写起来最简洁，不用额外的数据结构存节点，适合大部分常规深度的四叉树，是我个人优先推荐的写法
• BFS（广度优先，队列实现）：用迭代的方式遍历，不会有递归栈溢出的风险（比如四叉树特别深的时候），代码稍微繁琐一点，但稳定性更好

假设你的四叉树节点类有这些基础方法：isLeaf()（判断是否为叶子）、getColour()（叶子节点取颜色）、getChildren()（内部节点取四个子节点），另外需要知道整个位图的初始边长（比如size，必须是2的幂，比如256、512）

DFS递归版本（简洁首选） #

// 先假设你的四叉树节点类结构
class QuadTreeNode {
    private boolean isLeaf;
    private Colour colour;
    private List<QuadTreeNode> children;

    public boolean isLeaf() { return isLeaf; }
    public Colour getColour() { return colour; }
    public List<QuadTreeNode> getChildren() { return children; }
    // 构造器、setter省略
}

public class QuadTreeBitmap {
    private QuadTreeNode root;
    private int size; // 整个位图的边长，比如256

    public int countPixels(Colour targetColour) {
        return countRecursive(root, size, targetColour);
    }

    private int countRecursive(QuadTreeNode node, int currentSize, Colour target) {
        if (node == null) return 0;
        
        // 叶子节点：颜色匹配就返回区域像素数
        if (node.isLeaf()) {
            return node.getColour().equals(target) ? currentSize * currentSize : 0;
        }
        
        // 内部节点：递归遍历四个子节点，每个子区域边长是当前的一半
        int childSize = currentSize / 2;
        int total = 0;
        for (QuadTreeNode child : node.getChildren()) {
            total += countRecursive(child, childSize, target);
        }
        return total;
    }
}

BFS迭代版本（防栈溢出） #

如果担心递归深度太大导致栈溢出，就用队列来实现：

public int countPixelsBFS(Colour targetColour) {
    if (root == null) return 0;
    
    Queue<NodeSizePair> queue = new LinkedList<>();
    queue.add(new NodeSizePair(root, size));
    int total = 0;

    while (!queue.isEmpty()) {
        NodeSizePair pair = queue.poll();
        QuadTreeNode node = pair.node;
        int currentSize = pair.size;

        if (node.isLeaf()) {
            if (node.getColour().equals(targetColour)) {
                total += currentSize * currentSize;
            }
            continue;
        }

        // 把四个子节点加入队列，子区域边长减半
        int childSize = currentSize / 2;
        for (QuadTreeNode child : node.getChildren()) {
            queue.add(new NodeSizePair(child, childSize));
        }
    }
    return total;
}

// 辅助类：存节点和对应的区域边长
private static class NodeSizePair {
    QuadTreeNode node;
    int size;

    NodeSizePair(QuadTreeNode node, int size) {
        this.node = node;
        this.size = size;
    }
}

• 一定要确保Colour类的equals方法是正确实现的，不然颜色匹配会出错
• 初始的size必须是2的幂，因为四叉树是不断把区域四等分，只有2的幂才能一直分下去
• 如果你的四叉树叶子节点已经直接存储了该区域的像素数，那可以直接用这个数，不用计算currentSize * currentSize

内容的提问来源于stack exchange，提问作者binkibo