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

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

本文详解如何基于带跳转逻辑（linksTo）的问答结构，通过深度优先递归遍历构建所有完整决策路径，并输出标准化的 PathsData 格式结果。

本文详解如何基于带跳转逻辑（`linksto`）的问答结构，通过深度优先递归遍历构建所有完整决策路径，并输出标准化的 `pathsdata` 格式结果。

在构建动态问卷、智能导购或分支式交互流程时，常需将线性问题数组转化为可执行的「决策路径集合」。核心挑战在于：每个问题的选项可能指向不同后续问题（由 linksTo 字段指定），形成有向非循环图（DAG）；而目标是穷举所有从起始问题出发、沿有效 linksTo 链路直至终点（无 linksTo）的完整路径。

解决该问题的关键思路是：以 DFS（深度优先搜索）驱动递归，维护当前路径状态，并在叶子节点收集结果。以下是经过工程化优化的实现方案：

✅ 步骤一：预处理——构建问题索引映射表

为避免每次递归都遍历整个 questions 数组查找目标问题，我们预先构建一个以 questionIdx 为键的对象字典：

const buildQuestionMap = (questions: Question[]): Record<number question> => 
  questions.reduce((map, q) => {
    map[q.questionIdx] = q;
    return map;
  }, {} as Record<number question>);</number></number>

该映射支持 O(1) 时间复杂度的问题定位，显著提升递归效率。

✅ 步骤二：主递归函数 —— collectAllPaths

该函数接收当前问题节点和当前累积路径，对每个选项做以下操作：

将当前问题 + 当前选项信息（answerLabel、可选 linksTo）压入路径；
若存在 linksTo，则递归访问对应问题；
若不存在 linksTo，说明路径终止，保存当前完整路径。

type PathItem = {
  questionIdx: number;
  question: string;
  answerLabel: string;
  linksTo?: number; // 仅当非终点时存在
};

type PathNode = {
  pathIdx: number;
  show: true;
  path: PathItem[];
};

type PathsData = {
  name: string;
  paths: PathNode[];
};

const collectAllPaths = (
  rootQuestion: Question,
  questionsMap: Record<number question>,
  treeName: string
): PathsData => {
  const paths: PathNode[] = [];
  let pathIndex = 0;

  const visit = (node: Question, currentPath: PathItem[]) => {
    node.options.forEach(option => {
      const pathItem: PathItem = {
        questionIdx: node.questionIdx,
        question: node.question,
        answerLabel: option.answerLabel,
      };

      // 只有存在跳转时才添加 linksTo 字段（符合示例输出规范）
      if (option.linksTo !== undefined && option.linksTo !== null) {
        pathItem.linksTo = option.linksTo;
      }

      const newPath = [...currentPath, pathItem];

      if (option.linksTo && questionsMap[option.linksTo]) {
        // 继续递归到下一题
        visit(questionsMap[option.linksTo], newPath);
      } else {
        // 到达终点，保存路径
        paths.push({
          pathIdx: ++pathIndex,
          show: true,
          path: newPath,
        });
      }
    });
  };

  visit(rootQuestion, []);
  return { name: treeName, paths };
};</number>

✅ 使用示例与调用方式

结合原始 mockData，完整调用如下：

// 假设已定义 mockData 和类型接口 Question / Option
const questionMap = buildQuestionMap(mockData.questions);
const result = collectAllPaths(
  mockData.questions[0], // 起始问题（通常为 questionIdx === 1）
  questionMap,
  mockData.name
);

console.log(JSON.stringify(result, null, 2));

⚠️ 注意事项与最佳实践

起点唯一性：本方案默认从 questions[0]（即首个问题）启动。若业务中存在多个入口点，请封装为 questions.map(q => collectAllPaths(q, ...)) 并合并结果。
环路防护（进阶）：当前代码未检测循环引用（如 A→B→A）。生产环境建议增加 visitedSet: Set 参数，在 visit() 中检查 linksTo 是否已在路径中出现，防止栈溢出。
类型安全：强烈建议配合 TypeScript 接口定义（如 Question、Option、PathsData），确保 linksTo 类型为 number | undefined，避免运行时错误。
性能提示：对于超大规模决策树（>1000 节点），可考虑使用迭代 DFS（显式栈）替代递归，规避 JavaScript 调用栈限制。