生成所有可能问答路径的递归遍历实现教程-js教程-PHP中文网

生成所有可能问答路径的递归遍历实现教程

本文介绍如何使用深度优先递归遍历，从带跳转逻辑（linksTo）的树状问答数据中提取全部完整路径，并输出结构化路径数组，适用于问卷引导、决策树渲染等场景。

本文介绍如何使用深度优先递归遍历，从带跳转逻辑（`linksto`）的树状问答数据中提取全部完整路径，并输出结构化路径数组，适用于问卷引导、决策树渲染等场景。

在构建动态问卷、交互式决策树或分支式表单时，常需将“问题→选项→跳转目标”的链式结构展开为所有可达的完整路径。这类数据本质上是一棵有向图（可能含多个出边但无环），而核心挑战在于：每个选项可指向下一个问题（linksTo），且同一问题可能有多个选项，需穷举所有组合路径。此时，递归回溯是最自然、最清晰的解法。

核心思路：字典预处理 + DFS 递归遍历

为高效跳转，我们首先将原始 questions 数组转换为以 questionIdx 为键的查找字典（Map），避免每次递归都线性搜索下一个问题。随后，从起始问题（通常为 questions[0]）出发，维护当前路径 path，对每个选项：

将当前问题与该选项信息合并为路径节点；
若该选项含 linksTo，则递归访问对应问题；
若无 linksTo，说明路径终止，将当前完整路径存入结果集。

完整可运行实现（TypeScript）

// 类型定义（增强可读性与类型安全）
type Option = {
  answerIdx: number;
  answerLabel: string;
  linksTo?: number; // 可选：undefined 表示路径终点
};

type Question = {
  questionIdx: number;
  question: string;
  description: string;
  options: Option[];
};

type Tree = {
  name: string;
  description: string;
  questions: Question[];
};

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

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

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

// 主函数：生成所有路径
function generateAllPaths(tree: Tree): PathsData {
  // Step 1: 构建 questionIdx → Question 的 O(1) 查找字典
  const questionMap = new Map<number question>();
  tree.questions.forEach(q => questionMap.set(q.questionIdx, q));

  const result: PathItem[] = [];
  let pathIndex = 0;

  // Step 2: DFS 递归函数
  function dfs(currentQuestion: Question, currentPath: PathNode[]): void {
    currentQuestion.options.forEach(option => {
      // 构造当前路径节点
      const node: PathNode = {
        questionIdx: currentQuestion.questionIdx,
        question: currentQuestion.question,
        answerLabel: option.answerLabel,
      };

      // 若有跳转目标，添加 linksTo 字段
      if (option.linksTo !== undefined) {
        node.linksTo = option.linksTo;
      }

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

      // 若存在 linksTo，继续递归；否则保存完整路径
      if (option.linksTo !== undefined && questionMap.has(option.linksTo)) {
        dfs(questionMap.get(option.linksTo)!, newPath);
      } else {
        result.push({
          pathIdx: ++pathIndex,
          show: true,
          path: newPath,
        });
      }
    });
  }

  // 从第一个问题开始遍历（可根据业务调整起点）
  if (tree.questions.length > 0) {
    dfs(tree.questions[0], []);
  }

  return {
    name: tree.name,
    paths: result,
  };
}

// 使用示例
const mockData: Tree = {
  name: "My tree",
  description: "string",
  questions: [
    {
      questionIdx: 1,
      question: "Do you like potato",
      description: "string",
      options: [
        { answerIdx: 1, answerLabel: "Yes", linksTo: 2 },
        { answerIdx: 2, answerLabel: "No", linksTo: 3 },
      ],
    },
    {
      questionIdx: 2,
      question: "Do you like carrot",
      description: "string",
      options: [
        { answerIdx: 1, answerLabel: "Yes", linksTo: 3 },
        { answerIdx: 2, answerLabel: "No" },
      ],
    },
    {
      questionIdx: 3,
      question: "Do you like anything",
      description: "string",
      options: [
        { answerIdx: 1, answerLabel: "Yes" },
        { answerIdx: 2, answerLabel: "No" },
      ],
    },
  ],
};

console.log(JSON.stringify(generateAllPaths(mockData), null, 2));</number>

关键注意事项

✅ 无环保证：本实现假设输入数据无循环引用（如 Q1 → Q2 → Q1）。若存在环，需额外引入 visitedSet 防止无限递归；
✅ 起点灵活：当前从 questions[0] 开始，实际中可通过参数指定起始 questionIdx；
✅ 空选项容错：代码已处理 options 为空数组的情况（forEach 不执行）；
⚠️ 性能提示：路径总数呈指数级增长（如每题平均 k 个选项，深度 d，则最多 k^d 条路径），大数据量时建议增加最大深度限制或提供流式/分页导出能力；
? 扩展建议：如需支持「返回上一题」「并行分支」等高级逻辑，可在 Option 中扩展字段（如 backTo?: number, forkTo?: number[]），并在 dfs 中相应处理。

通过该递归方案，你不仅能准确生成所有合法路径，还能保持代码简洁、可测试、易维护——这是处理树状分支逻辑的经典范式。