如何用Java编写四叉树递归遍历方法及相关功能？

我理解四叉树递归遍历的概念：向下遍历检查节点是否为叶子节点，若非叶子节点则继续深入，回溯后再处理其他分支，但不知道如何用Java编写对应代码。

以下是我编写的四叉树构造器代码：

public class QuadtreeBitmap {
    // location
    private final int x;
    private final int y;
    // height and width
    private final int size;
    // if leaf
    private boolean leaf;
    // either Colour.BLACK or Colour.WHITE
    private Colour colour;
    // otherwise
    private QuadtreeBitmap northWest;
    private QuadtreeBitmap northEast;
    private QuadtreeBitmap southWest;
    private QuadtreeBitmap southEast;

    /**
     * Constructs a new quadtree bitmap with height and width equal to the specified size, and
     * every pixel initialized to the given colour. The specified size must be a power of 2,
     * and must be greater than zero.
     *
     * @param size   the height and width of this quadtree bitmap
     * @param colour the colour with which to initialize every pixel in this quadtree bitmap
     */
    public QuadtreeBitmap(int size, Colour colour) {
        this(0, 0, size, colour);
    }

    /**
     * Constructs a new quadtree bitmap with height and width equal to the specified size, and
     * every pixel initialized to white. The specified size must be a power of 2, and must be
     * greater than zero.
     *
     * @param size the height and width of this quadtree bitmap
     */
    public QuadtreeBitmap(int size) {
        this(0, 0, size, Colour.WHITE);
    }

    // specifying location only supported internally
    private QuadtreeBitmap(int x, int y, int size, Colour colour) {
        // only supporting power-of-2 dimensions
        if (!powerOfTwo(size)) {
            throw new IllegalArgumentException("Size not power of 2.");
        }
        this.x = x;
        this.y = y;
        this.size = size;
        this.leaf = true;
        this.colour = colour;
        this.northWest = null;
        this.northEast = null;
        this.southWest = null;
        this.southEast = null;
    }

    // combining quads to form tree only supported internally, assumes well-positioned
    private QuadtreeBitmap(int x, int y, int size, List<QuadtreeBitmap> quads) {
        this(x, y, size, Colour.WHITE);
        northWest = quads.get(0);
        northEast = quads.get(1);
        southWest = quads.get(2);
        southEast = quads.get(3);
        this.leaf = false;
    }

    // for any basic task which needs to be repeated all four quadrants
    private List<QuadtreeBitmap> quadrants() {
        return Arrays.asList(northWest, northEast, southWest, southEast);
    }

    // retrieves the quadrant within which the specified location lies
    private QuadtreeBitmap quadrantOf(int x, int y) {
        for (QuadtreeBitmap quad : quadrants()) {
            if (quad.containsPoint(x, y)) {
                return quad;
            }
        }
        return null;
    }

    public int getSize() {
        return size;
    }

    // 补充常见的辅助方法实现（假设你还没写）
    private boolean powerOfTwo(int size) {
        return size > 0 && (size & (size - 1)) == 0;
    }

    public boolean containsPoint(int px, int py) {
        return px >= this.x && px < this.x + this.size && py >= this.y && py < this.y + this.size;
    }
}

我需要完成作业要求的一系列方法，比如统计特定颜色的像素数量等，但完全不知道如何着手。

递归遍历的核心模式拆解 #

其实四叉树的所有递归操作都遵循一个简单的模板：

1. 基线条件：如果当前节点是叶子节点，直接处理（比如返回颜色、统计像素数）
2. 递归条件：如果当前节点是非叶子节点，递归处理它的四个子象限，再合并结果

下面我给你几个作业中常见方法的实现示例，帮你把思路落地成代码：

1. 统计特定颜色的像素数量 #

这是最典型的递归应用，直接对应你理解的遍历逻辑：

public int countColourPixels(Colour targetColour) {
    // 叶子节点：直接判断颜色是否匹配，返回对应像素总数
    if (this.leaf) {
        return this.colour.equals(targetColour) ? this.size * this.size : 0;
    }
    // 非叶子节点：递归累加四个象限的统计结果
    int total = 0;
    for (QuadtreeBitmap quad : quadrants()) {
        total += quad.countColourPixels(targetColour);
    }
    return total;
}

2. 获取指定坐标的像素颜色 #

需要递归定位到目标坐标所在的叶子节点：

public Colour getPixelColour(int px, int py) {
    // 先校验坐标是否合法（可选，根据需求添加）
    if (!containsPoint(px, py)) {
        throw new IllegalArgumentException("坐标超出当前四叉树范围");
    }
    // 叶子节点：直接返回颜色
    if (this.leaf) {
        return this.colour;
    }
    // 非叶子节点：找到对应象限继续递归
    QuadtreeBitmap targetQuad = quadrantOf(px, py);
    return targetQuad.getPixelColour(px, py);
}

3. 遍历所有叶子节点（比如打印所有纯色区块） #

如果需要对所有叶子节点执行操作，递归模式同样适用：

public void traverseLeafNodes(Consumer<QuadtreeBitmap> action) {
    if (this.leaf) {
        action.accept(this); // 对叶子节点执行自定义操作
        return;
    }
    for (QuadtreeBitmap quad : quadrants()) {
        quad.traverseLeafNodes(action);
    }
}

你可以这样调用它来打印所有黑色区块：

quadtree.traverseLeafNodes(leaf -> {
    if (leaf.colour.equals(Colour.BLACK)) {
        System.out.printf("黑色区块位置：(%d,%d)，大小：%d%n", leaf.x, leaf.y, leaf.size);
    }
});

这些示例的核心都是先判断叶子节点做基线处理，非叶子节点就递归处理四个子节点，你可以基于这个思路扩展其他作业要求的方法，比如修改某个区域颜色、计算树的深度等等。

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