B树迭代中序遍历实现findKthElement功能出现死循环问题求助

问题根因 #

你的代码出现无限循环和输出重复内容的核心原因是：B树的每个节点包含多个key和多个子节点，仅在栈中存储节点本身无法记录该节点的遍历进度，导致每次处理同一个节点时都会重复从第一个子节点开始遍历，形成死循环。同时你的遍历逻辑不符合B树中序遍历的规则，输出顺序也存在错误。

具体错误点 #

• 内层遍历子节点的for循环逻辑完全混乱：你从i=0到current.numNodes遍历，只要节点不是叶子就压栈并切换为第i个子节点，此时当前节点已经被替换，后续的i++遍历逻辑完全无效，且没有记录当前节点已经处理到第几个子节点。
• 弹出节点后直接输出所有key：B树的中序遍历规则是「遍历第i个子节点 → 输出第i个key → 遍历第i+1个子节点」，你一次性输出该节点所有key的做法不符合中序遍历要求，也没有处理当前key对应的下一个子节点。
• 没有标记节点的已处理状态：栈中仅存储节点对象，每次回到该节点时都会重新从第一个子节点开始处理，导致相同节点被反复压栈、相同key被重复打印，最终形成无限循环。

修复方案 #

你需要修改栈的存储结构，同时存储当前节点和该节点已经处理到的索引位置，用来记录遍历进度。以下是修复后的迭代中序遍历实现：

public void findKth(int k) {
    // 栈存储 Pair<节点, 下一个要处理的索引位置>
    Stack<Map.Entry<BTreeNode, Integer>> s = new Stack<>();
    BTreeNode current = this.root;
    int idx = 0;
    int count = 0;

    while (current != null || !s.isEmpty()) {
        // 一路压入最左侧的未处理子节点
        while (current != null) {
            s.push(new AbstractMap.SimpleEntry<>(current, idx));
            current = current.isLeaf ? null : current.children[idx];
            idx = 0;
        }

        // 弹出栈顶节点和对应的处理索引
        Map.Entry<BTreeNode, Integer> entry = s.pop();
        current = entry.getKey();
        idx = entry.getValue();

        // 匹配到第k个元素直接返回
        count++;
        if (count == k) {
            System.out.println("第k个元素是：" + current.keys[idx].getName());
            return;
        }

        // 索引+1，接下来处理下一个子节点
        idx++;
        // 如果还有子节点就切换到下一个子节点，否则当前节点处理完毕置为null
        if (idx <= current.numNodes && !current.isLeaf) {
            current = current.children[idx];
        } else {
            current = null;
        }
    }
}

内容的提问来源于stack exchange，提问作者Luka Jozić