2-3树递归遍历未遍历所有子节点问题求助

我太懂你这种困扰了——之前写树遍历的时候也踩过类似的坑，递归走着走着就只钻了一条分支，完全没处理其他子节点对吧？核心问题大概率是你的递归逻辑没遍历节点的所有子节点，毕竟2-3树的每个节点最多有4个子节点，得确保每个子节点都被触发递归才行。

先把你给出的Node类代码贴出来方便参考：

class Node<T extends Comparable<T>> { 
    List<T> vals = new ArrayList<T>(); 
    List<Node<T>> children = new ArrayList<Node<T>>(); 

    boolean isLeaf() { 
        return children.size() == 0; 
    } 

    boolean is4Node() { 
        return vals.size() == 3; 
    }
    // 其他未展示的方法
}

方案1：递归式深度优先遍历（带层级标记） #

这种方式会先打印当前节点的层级和值，然后循环遍历所有子节点，每个子节点都触发递归，这样就不会只走单一方向了——递归完一个分支后会回到循环，继续处理下一个子节点。

代码实现：

// 对外调用的入口方法，初始层级设为1
public void printLevelsDFS(Node<T> root) {
    if (root == null) return;
    printNodeWithLevel(root, 1);
}

// 递归核心方法，负责打印单个节点并遍历子节点
private void printNodeWithLevel(Node<T> node, int level) {
    // 打印当前节点的层级和存储的值
    System.out.printf("层级 %d: %s%n", level, node.vals);
    
    // 遍历当前节点的所有子节点，递归进入下一层级
    for (Node<T> child : node.children) {
        printNodeWithLevel(child, level + 1);
    }
}

方案2：广度优先遍历（更直观的按层输出） #

如果想要同一层级的节点集中展示（比如所有层级2的节点放在一起打印），那广度优先（BFS）的方式会更合适，用队列来维护待处理的节点和对应的层级：

public void printLevelsBFS(Node<T> root) {
    if (root == null) return;
    
    // 用两个队列分别存节点和对应的层级，也可以用自定义类封装，这里为了简单分开存
    Queue<Node<T>> nodeQueue = new LinkedList<>();
    Queue<Integer> levelQueue = new LinkedList<>();
    nodeQueue.add(root);
    levelQueue.add(1);
    
    int currentPrintLevel = 1;
    System.out.printf("层级 %d: ", currentPrintLevel);
    
    while (!nodeQueue.isEmpty()) {
        Node<T> currentNode = nodeQueue.poll();
        int nodeLevel = levelQueue.poll();
        
        // 如果当前节点的层级和正在打印的层级不一致，换行开启新层级的打印
        if (nodeLevel != currentPrintLevel) {
            currentPrintLevel = nodeLevel;
            System.out.printf("%n层级 %d: ", currentPrintLevel);
        }
        
        // 打印当前节点的值
        System.out.print(currentNode.vals + " ");
        
        // 将当前节点的所有子节点加入队列，层级+1
        for (Node<T> child : currentNode.children) {
            nodeQueue.add(child);
            levelQueue.add(nodeLevel + 1);
        }
    }
    System.out.println();
}

你原来递归出错的常见原因 #

大概率是你之前的递归只处理了单个子节点（比如只调用了children.get(0)），没有遍历整个children列表，比如下面这种错误写法：

// 错误示例：只处理第一个子节点，导致只走单一分支
private void wrongPrint(Node<T> node, int level) {
    System.out.printf("层级 %d: %s%n", level, node.vals);
    if (!node.isLeaf()) {
        // 只递归第一个子节点，其他子节点完全被忽略
        wrongPrint(node.children.get(0), level + 1);
    }
}

只要改成循环遍历所有子节点，就能解决只走单一方向的问题啦，你可以根据自己的需求选择DFS或者BFS的实现方式，测试的时候可以构造一个简单的2-3树验证效果~

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