如何遍历十进制搜索树？（Java实现，节点最多10个子节点）

我来帮你理清十进制搜索树的遍历逻辑，你的contains和get方法的核心问题在于没有正确按每一位数字来遍历树的层级，而是错误地直接用循环索引访问子节点，完全没用到key的各位数字。

先明确十进制搜索树的遍历核心逻辑 #

根据老师的定义，这个树的结构有几个关键特点：

• 每一层对应key的一位数字，按最高有效位（MSD）到最低有效位的顺序排列（比如digitCount=3时，第一层是百位，第二层是十位，第三层是个位）
• 每个节点的children数组索引对应当前位的数字（0-9）
• 只有最底层的叶子节点存储非null的value，所有分支节点的value都是null
• 遍历路径完全由key的每一位数字决定：从根节点出发，每一步根据当前位的数字，走到对应索引的子节点，直到走完所有digitCount层

你的现有代码问题分析 #

• contains方法中，你用node.children[i].equals(key)做判断：children[i]是DecimalNode对象，和整数key完全不是同一类型，逻辑完全错误；而且循环的i只是层数索引，没有关联key的各位数字。
• get方法中，node.children[i].children[key]的写法完全不符合树的结构：key是完整整数，不是某一位的数字，而且分支节点的value都是null，不可能返回有效数据。

正确实现方案 #

首先我们需要一个辅助方法，用来获取key在指定位置的数字（从最高位开始计数），这里提供两种实现方式：

辅助方法：获取key指定位置的数字 #

方式1：数学计算法

private int getDigit(int key, int position) {
    // position从0开始，对应最高位（比如digitCount=3，position=0是百位，position=2是个位）
    int divisor = (int) Math.pow(10, digitCount - 1 - position);
    return (key / divisor) % 10;
}

方式2：字符串格式化法（更安全，避免大数溢出）

private int getDigit(int key, int position) {
    // 把key转为固定长度的字符串，不足digitCount位补前导零
    String keyStr = String.format("%0" + digitCount + "d", key);
    return Character.getNumericValue(keyStr.charAt(position));
}

正确的contains方法实现 #

@Override
public boolean contains(int key) {
    // 先校验key是否超出digitCount的范围（可选，但能提前终止无效判断）
    if (key < 0 || key >= Math.pow(10, digitCount)) {
        return false;
    }

    DecimalNode current = root;
    for (int i = 0; i < digitCount; i++) {
        int digit = getDigit(key, i);
        // 如果当前层对应数字的子节点不存在，说明key不在树中
        if (current.children[digit] == null) {
            return false;
        }
        // 向下遍历一层
        current = current.children[digit];
    }
    // 走完所有层后，只有叶子节点的value非null才说明key存在
    return current.value != null;
}

正确的get方法实现 #

@Override
public E get(int key) {
    // 提前校验key范围
    if (key < 0 || key >= Math.pow(10, digitCount)) {
        return null;
    }

    DecimalNode current = root;
    for (int i = 0; i < digitCount; i++) {
        int digit = getDigit(key, i);
        if (current.children[digit] == null) {
            // 路径不存在，直接返回null
            return null;
        }
        current = current.children[digit];
    }
    // 返回叶子节点的value（可能为null，对应key不存在的情况）
    return (E) current.value;
}

关键逻辑总结 #

1. 从根节点出发，按key的每一位数字（从高位到低位）逐层遍历
2. 每一步根据当前位的数字，访问对应索引的子节点
3. 如果中途某一层的子节点不存在，直接判定key不存在
4. 走完所有digitCount层后，检查最终叶子节点的value是否非null，以此确定key是否存在或获取对应值

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