如何利用带标记的前序文本文件递归生成树结构？

嗨，我来帮你捋捋这个递归构建树的问题～你卡在递归基准情况和BufferedReader的处理上，核心问题其实是没理清前序遍历的行与树结构的对应关系，还有怎么解决“读过头”的痛点。

先搞懂核心逻辑：前序遍历与树的对应 #

你说行按树的前序排列，且以1开头的是问题，我先默认你的文本带层级标识（比如1是一级问题，1.1是二级子问题），举个例子：

1 主问题
回答1
1.1 子问题1
回答2
回答3
1.2 子问题2
回答4
2 兄弟问题
回答5

对应的树结构是：主问题下挂着回答和子问题，子问题再挂回答，最后是同级的兄弟问题。前序遍历的顺序就是上面的行顺序，所以递归的核心是判断当前行是不是当前节点的子节点，同时解决BufferedReader不能回头读的问题。

你之前的基准情况错在哪？ #

你以为基准情况是“读取到回答”，其实不对：

• 真正的递归终止基准有两个：
  1. 读到null（文件读完了），直接返回null
  2. 读到的行是当前节点的同级或更高级问题，这时候得把这行“放回”输入流，结束当前节点的子节点读取，返回当前节点
• 回答节点本身是叶子，创建后直接返回，这是叶子的基准，但不是递归终止的核心——核心是知道什么时候停止给当前节点加子节点。

完整代码示例（Java） #

先定义树节点类：

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    boolean isQuestion; // true=问题，false=回答
    String content;     // 去掉前缀的文本内容
    int level;          // 问题层级（回答层级设为0）
    List<TreeNode> children;

    TreeNode(boolean isQuestion, String content, int level) {
        this.isQuestion = isQuestion;
        this.content = content;
        this.level = level;
        this.children = new ArrayList<>();
    }
}

然后是递归构建方法，关键用mark()和reset()解决回退问题：

import java.io.BufferedReader;
import java.io.IOException;

public class TreeBuilder {
    public TreeNode buildTree(BufferedReader reader) throws IOException {
        return buildTree(reader, 0);
    }

    // 重载方法，传入父节点层级，用来判断当前行是不是子节点
    private TreeNode buildTree(BufferedReader reader, int parentLevel) throws IOException {
        String line = reader.readLine();
        if (line == null) {
            return null; // 基准1：文件读完了
        }

        TreeNode currentNode;
        if (line.startsWith("1")) {
            // 解析问题的层级和内容
            String[] parts = line.split(" ", 2); // 按第一个空格分割前缀和内容
            int currentLevel = parts[0].split("\\.").length; // 比如"1.1"分割后是2个元素，层级就是2
            String content = parts[1].trim();

            // 如果当前问题层级 <= 父节点层级，说明是同级/更高级，回退给上层处理
            if (currentLevel <= parentLevel) {
                reader.reset(); // 把刚才读的行放回去
                return null; // 基准2：停止当前节点的子节点读取
            }

            currentNode = new TreeNode(true, content, currentLevel);

            // 递归读取所有子节点
            while (true) {
                reader.mark(1024); // 标记当前位置，确保能装下一行内容
                TreeNode child = buildTree(reader, currentLevel);
                if (child == null) {
                    break; // 没有更多子节点了，退出循环
                }
                currentNode.children.add(child);
            }
        } else {
            // 回答节点：直接创建叶子节点返回
            currentNode = new TreeNode(false, line.trim(), 0);
        }

        return currentNode;
    }
}

关键细节讲清楚 #

• 层级判断：通过问题前缀的点数量计算层级，比如1.1是二级，只能当一级问题的子节点，这样就能区分父子和兄弟节点。
• mark()和reset()的作用：每次读下一行前先标记位置，要是发现这行不属于当前节点的子节点，就重置到标记位置，让上层递归处理这行——完美解决了BufferedReader不能回头读的痛点。
• 递归逻辑：每个问题节点会不断添加子节点，直到遇到同级/更高级问题或文件结束；回答直接作为叶子节点返回。

如果你的文本没有层级标识？ #

要是你说的“以1开头”只是问题的标识，所有问题都用1开头（不管层级），那树结构就是每个问题下面可以挂回答和子问题，子问题的所有内容处理完后才会回到父问题的下一个子节点。这时候递归方法可以简化成这样：

private TreeNode buildTree(BufferedReader reader) throws IOException {
    String line = reader.readLine();
    if (line == null) {
        return null;
    }

    TreeNode currentNode;
    if (line.startsWith("1")) {
        currentNode = new TreeNode(true, line.substring(1).trim(), 0);
        while (true) {
            reader.mark(1024);
            String nextLine = reader.readLine();
            if (nextLine == null) {
                break;
            }
            if (nextLine.startsWith("1")) {
                reader.reset();
                // 递归处理子问题的所有子节点
                currentNode.children.add(buildTree(reader));
            } else {
                // 直接添加回答节点
                currentNode.children.add(new TreeNode(false, nextLine.trim(), 0));
            }
        }
    } else {
        currentNode = new TreeNode(false, line.trim(), 0);
    }
    return currentNode;
}

不过这种情况所有后续问题都会变成前一个问题的子节点，可能不符合你的预期，所以还是建议给问题加层级标识，这样才能正确构建树结构。

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