B树深度优先搜索实现非递归中序遍历输出顺序错误问题求解

代码问题根源 #

你现有代码的问题完全是遍历逻辑和栈特性不匹配导致的，具体有两点核心缺失：

• 没有遵循B树中序遍历的执行顺序：对于B树的任意非叶子节点，正确遍历顺序为遍历第i个子树 → 输出第i个key，全部key输出完成后再遍历最后一个子树。你当前的实现弹出节点后直接输出所有key，完全没有等待对应左侧子树遍历完成，顺序必然出错。
• 栈是后进先出结构，你按从左到右的顺序压入子节点，弹出时会自动变成从右到左遍历子节点，进一步打乱输出顺序。
• 没有记录当前节点的遍历进度，每次弹出节点都从第0个key开始处理，无法承接上一次的遍历状态。

修复后的实现 #

你可以给栈元素补充「当前节点+下一个要处理的下标」的状态标记，就能完美实现非递归遍历：

public void iterative() {
    // 栈存储数组，第一个元素为节点，第二个元素为该节点下一个要处理的位置下标
    Stack<Object[]> stack = new Stack<>();
    stack.push(new Object[]{this, 0});
    
    while (!stack.isEmpty()) {
        Object[] entry = stack.pop();
        BTreeNode<T> curr = (BTreeNode<T>) entry[0];
        int processIdx = (int) entry[1];
        
        // 叶子节点没有子树，直接输出所有key即可
        if (curr.isLeaf) {
            for (int i = 0; i < curr.numNodes; i++) {
                System.out.println(curr.keys[i].toString());
            }
            continue;
        }
        
        // 还有未处理的key和对应子树
        if (processIdx < curr.numNodes) {
            // 先把当前节点+下一个待处理下标压回栈，等子树遍历完再回来处理后续内容
            stack.push(new Object[]{curr, processIdx + 1});
            // 压入当前下标对应的子树，先遍历完这个子树
            stack.push(new Object[]{curr.children[processIdx], 0});
            // 子树遍历完成后输出对应key
            System.out.println(curr.keys[processIdx].toString());
        } 
        // 所有key处理完成后，遍历最后一个子树
        else if (processIdx == curr.numNodes) {
            stack.push(new Object[]{curr.children[processIdx], 0});
        }
    }
}

如果你不想在栈里存额外的下标标记，也可以选择把节点的内容从右到左逆序压栈（子节点和key交替压入），不过上面的写法逻辑更直观，调试成本更低。

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