如何在 Java 中编写递归四叉树遍历方法?

Question

我理解这个概念，但我不知道如何用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;
}

从本质上讲，我需要为作业实现一大堆方法，例如计算某些颜色的像素等，但我不知道如何开始

Answer 1

让我们简化一下。你会如何在二叉树上写遍历？

好吧，你会写一个像

public int CountNodes(){
int leftcount = (this.left==null) ? 0 : this.left.CountNodes();
int rightcount = (this.right==null) ? 0 : this.right.CountNodes();
return 1 + leftcount + rightcount;
}

因此，您希望使用固定的内部值东北、西北、东南、西南而不是"左"和"右"来实现这一点。请注意，节点值中的 +1 考虑了节点本身，因此不需要显式的"叶检查"。

应该提到的是，您需要了解环境中的堆栈大小限制。Foxpro 曾经有 32 个调用的有限堆栈高度，像这样的递归调用可能会深入到非常大的主题材料中。