如何用Java构建深度为4、高度为16的4叉键树结构？

先澄清下表述：你提到的「深度=4、高度=16」可能有点概念混淆——通常树的深度是从根节点到叶子节点的最长路径长度（比如根深度为0的话，深度4意味着整棵树有5层节点），而高度是从当前节点到叶子的最长路径。我先按你明确的「深度=4」来构建四叉树（每个节点4个子节点），如果「高度=16」是指每个节点需要16个分支，后面也会给出适配方案。

1. 定义四叉树节点类 #

首先我们需要一个节点类，每个节点包含4个子节点（对应四叉的四个分支，比如西北、东北、西南、东南四个方向），同时可以存储键值对：

public class QuadTreeNode<K, V> {
    // 四个子节点
    private QuadTreeNode<K, V> northwest;
    private QuadTreeNode<K, V> northeast;
    private QuadTreeNode<K, V> southwest;
    private QuadTreeNode<K, V> southeast;
    
    // 节点存储的键值
    private K key;
    private V value;

    // 构造方法
    public QuadTreeNode(K key, V value) {
        this.key = key;
        this.value = value;
        // 初始化子节点为null，构建时再赋值
        this.northwest = null;
        this.northeast = null;
        this.southwest = null;
        this.southeast = null;
    }

    // Getter & Setter 方法
    public QuadTreeNode<K, V> getNorthwest() { return northwest; }
    public void setNorthwest(QuadTreeNode<K, V> northwest) { this.northwest = northwest; }
    public QuadTreeNode<K, V> getNortheast() { return northeast; }
    public void setNortheast(QuadTreeNode<K, V> northeast) { this.northeast = northeast; }
    public QuadTreeNode<K, V> getSouthwest() { return southwest; }
    public void setSouthwest(QuadTreeNode<K, V> southwest) { this.southwest = southwest; }
    public QuadTreeNode<K, V> getSoutheast() { return southeast; }
    public void setSoutheast(QuadTreeNode<K, V> southeast) { this.southeast = southeast; }
    public K getKey() { return key; }
    public void setKey(K key) { this.key = key; }
    public V getValue() { return value; }
    public void setValue(V value) { this.value = value; }
}

2. 实现四叉树的构建逻辑 #

接下来写一个树的管理类，包含递归构建指定深度四叉树的方法。这里定义根节点深度为0，叶子节点深度为4，也就是整棵树有5层节点：

public class QuadKeyTree<K, V> {
    private QuadTreeNode<K, V> root;
    private int targetDepth; // 目标深度

    public QuadKeyTree(int targetDepth) {
        this.targetDepth = targetDepth;
        // 初始化根节点，键值可以根据业务自定义
        this.root = new QuadTreeNode<>("root-key", "root-value");
        // 递归构建树
        buildTree(root, 0);
    }

    // 递归构建四叉树
    private void buildTree(QuadTreeNode<K, V> currentNode, int currentDepth) {
        // 达到目标深度时停止递归（当前节点是叶子节点）
        if (currentDepth >= targetDepth) {
            return;
        }

        // 为当前节点创建4个子节点，键值按分支+深度命名，可根据需求修改
        QuadTreeNode<K, V> nw = new QuadTreeNode<>(String.format("nw-%d", currentDepth+1), String.format("val-nw-%d", currentDepth+1));
        QuadTreeNode<K, V> ne = new QuadTreeNode<>(String.format("ne-%d", currentDepth+1), String.format("val-ne-%d", currentDepth+1));
        QuadTreeNode<K, V> sw = new QuadTreeNode<>(String.format("sw-%d", currentDepth+1), String.format("val-sw-%d", currentDepth+1));
        QuadTreeNode<K, V> se = new QuadTreeNode<>(String.format("se-%d", currentDepth+1), String.format("val-se-%d", currentDepth+1));

        // 绑定子节点到当前节点
        currentNode.setNorthwest(nw);
        currentNode.setNortheast(ne);
        currentNode.setSouthwest(sw);
        currentNode.setSoutheast(se);

        // 递归构建每个子节点的下一层
        buildTree(nw, currentDepth + 1);
        buildTree(ne, currentDepth + 1);
        buildTree(sw, currentDepth + 1);
        buildTree(se, currentDepth + 1);
    }

    // 测试用：按深度遍历打印树结构
    public void printTree(QuadTreeNode<K, V> node, int depth) {
        if (node == null) return;
        System.out.printf("Depth %d: Key=%s, Value=%s%n", depth, node.getKey(), node.getValue());
        printTree(node.getNorthwest(), depth + 1);
        printTree(node.getNortheast(), depth + 1);
        printTree(node.getSouthwest(), depth + 1);
        printTree(node.getSoutheast(), depth + 1);
    }

    public QuadTreeNode<K, V> getRoot() {
        return root;
    }

    // 测试入口
    public static void main(String[] args) {
        // 构建深度为4的四叉树
        QuadKeyTree<String, String> tree = new QuadKeyTree<>(4);
        // 打印树结构
        tree.printTree(tree.getRoot(), 0);
    }
}

3. 适配「高度=16」的需求 #

如果「高度=16」实际是指每个节点需要16个分支（也就是十六叉树），只需要修改节点类用数组存储子节点，再调整构建逻辑即可：

// 十六叉节点类
public class HexTreeNode<K, V> {
    private HexTreeNode<K, V>[] children;
    private K key;
    private V value;

    @SuppressWarnings("unchecked")
    public HexTreeNode(K key, V value) {
        this.key = key;
        this.value = value;
        this.children = new HexTreeNode[16]; // 初始化16个子节点
    }

    // Getter & Setter 方法...
}

构建树时，循环创建16个子节点并递归，逻辑和四叉树一致，只是把4个分支改成16个即可。

注意事项 #

• 键值生成：示例用了简单的命名规则，你可以根据实际业务（比如空间坐标、字符串分片等）自定义键的生成逻辑。
• 递归限制：如果目标深度很大（比如超过1000），递归会导致栈溢出，建议改用迭代方式构建。
• 节点简化：如果不需要存储值，只保留键即可，简化节点类的属性。

内容的提问来源于stack exchange，提问作者Ji Young Park