使用递归函数遍历决策树并生成所有可能路径的完整教程-js教程-PHP中文网

使用递归函数遍历决策树并生成所有可能路径的完整教程

本文详解如何基于带跳转逻辑（linksTo）的问答数据结构，设计健壮的递归算法，自动生成所有从根问题出发的完整路径，并输出标准化的路径集合。

本文详解如何基于带跳转逻辑（`linksto`）的问答数据结构，设计健壮的递归算法，自动生成所有从根问题出发的完整路径，并输出标准化的路径集合。

在构建动态问卷、决策流程图或分支式交互系统时，常需将线性问题数组转化为可执行的“路径树”——即从起始问题出发，依据用户每一步选择（通过 linksTo 指向下一题），穷举所有合法终点路径。这类问题天然适合深度优先递归遍历（DFS）：每个选项触发一次子调用，无后续跳转时即为一条完整路径。

关键在于避免常见误区：
❌ 不应尝试“循环展开所有问题再拼接”，这会破坏路径的因果依赖；
❌ 不宜在顶层对 questions 数组做 .map() 扁平化处理（如原代码中 originalData.questions.map(...)），因为路径是跨问题的链式结构，而非单问题映射；
✅ 正确思路是：以首个问题为入口，递归探索每个 option 的 linksTo 分支，沿途累积路径节点，遇到无跳转选项时终止并收集结果。

✅ 实现步骤详解

1. 构建快速查找字典（O(1) 访问任意题）

原始数据中问题按顺序排列，但 linksTo 指向的是 questionIdx（非数组索引）。因此第一步是预处理，建立 { questionIdx → question } 映射：

const questionDict = mockData.questions.reduce((acc, q) => {
  acc[q.questionIdx] = q;
  return acc;
}, {} as Record<number typeof mockdata.questions>);</number>

2. 定义递归核心函数 visit

该函数接收当前问题节点和当前路径片段，对每个选项执行：

将「当前问题 + 当前选项答案」构造成路径节点；
若该选项含 linksTo，则递归访问目标问题；
否则（即 linksTo 不存在），将当前完整路径存入结果集。

function getAllPaths(
  rootQuestion: typeof mockData.questions[number],
  questionDict: Record<number typeof mockdata.questions>
): { pathIdx: number; show: true; path: Array }[] {
  const result: ReturnType<typeof getallpaths> = [];
  let pathIndex = 0;

  function visit(current: typeof mockData.questions[number], path: Array<any>) {
    current.options.forEach(option => {
      // 构建当前步路径节点
      const step = {
        questionIdx: current.questionIdx,
        question: current.question,
        answerLabel: option.answerLabel,
      } as const;

      // 若有跳转，追加 linksTo 字段（仅当存在时）
      if (option.linksTo !== undefined) {
        (step as any).linksTo = option.linksTo;
      }

      const newPath = [...path, step];

      // 递归继续：存在 linksTo，且目标问题存在
      if (option.linksTo && questionDict[option.linksTo]) {
        visit(questionDict[option.linksTo], newPath);
      } else {
        // 终止路径：无跳转或目标问题不存在（视为合法终点）
        result.push({
          pathIdx: ++pathIndex,
          show: true,
          path: newPath,
        });
      }
    });
  }

  visit(rootQuestion, []);
  return result;
}</any></typeof></number>

3. 调用并整合输出结构

假设 mockData.questions[0] 是根问题（questionIdx: 1），最终输出需符合 PathsData 类型：

const paths = getAllPaths(mockData.questions[0], questionDict);

const output: PathsData = {
  name: mockData.name,
  paths,
};

⚠️ 注意事项与最佳实践

根节点确认：确保 mockData.questions 中存在 questionIdx: 1 的问题，且无外部 linksTo 指向它（即它是唯一入口）。若存在多个入口，需对每个入口调用 getAllPaths 并合并结果。
环路检测（进阶）：当前实现未防止循环引用（如 Q1→Q2→Q1）。生产环境建议添加 visitedSet: Set 参数，在 visit 前检查 current.questionIdx 是否已存在，避免无限递归。

类型安全增强：使用 TypeScript 可严格定义 Tree 和 PathsData 接口，例如：

interface Question {
  questionIdx: number;
  question: string;
  options: Array;
}
interface PathStep {
  questionIdx: number;
  question: string;
  answerLabel: string;
  linksTo?: number;
}