如何在TypeScript中按值搜索树形结构且不触发最大调用栈溢出

调用栈溢出原因 #

• 递归逻辑混淆了入参和实例属性：函数接收的入参protcolTree未被使用，全程读取this.protocolTree根节点数据，导致递归永远在遍历同一层级，触发死递归最终栈溢出。
• 缺失边界判断：未处理叶子节点无subNodes属性的情况，传入undefined进行递归会导致逻辑异常，进一步加剧死循环。
• 直接修改原树数据：递归过程中直接赋值this.protocolTree，会破坏原始树结构，导致后续遍历逻辑错乱。

字母匹配搜索实现说明 #

完全可以仅通过节点value的字母内容进行搜索，可根据需求选择精确匹配、模糊匹配、大小写不敏感匹配等规则，只需调整匹配判断逻辑即可。

修复后的代码实现 #

版本1：返回所有匹配节点的扁平列表 #

// 先补充SessionTree类型定义，方便类型校验
interface SessionTree {
  size: number;
  offset: number;
  value: string;
  subNodes?: SessionTree[];
}

// 搜索方法
searchTree(tree: SessionTree[], searchString: string): SessionTree[] {
  const result: SessionTree[] = [];
  const traverse = (nodes: SessionTree[]) => {
    for (const node of nodes) {
      // 匹配规则可自定义，这里用大小写不敏感的模糊匹配示例
      if (node.value.toLowerCase().includes(searchString.toLowerCase())) {
        result.push(node);
      }
      // 有子节点就递归遍历子节点
      if (node.subNodes?.length) {
        traverse(node.subNodes);
      }
    }
  }
  traverse(tree);
  return result;
}

// 调用示例：搜索所有value含D的节点
const matchedNodes = searchTree(this.protocolTree, 'D');

版本2：返回保留原有层级的过滤树（适用于可展开树的搜索筛选展示） #

filterTree(tree: SessionTree[], searchString: string): SessionTree[] {
  return tree.filter(node => {
    const isMatch = node.value.toLowerCase().includes(searchString.toLowerCase());
    // 递归过滤子节点
    if (node.subNodes?.length) {
      const filteredSub = this.filterTree(node.subNodes, searchString);
      // 子节点有匹配项就保留当前节点，替换为过滤后的子节点
      if (filteredSub.length) {
        node.subNodes = filteredSub;
        return true;
      }
    }
    return isMatch;
  })
}

// 调用示例：过滤后保留匹配节点的父级层级，适合树形控件展示
const filteredTree = filterTree(this.protocolTree, 'E');

补充说明 #

如果你的树形结构深度超过10000层，才需要将递归实现改为迭代的广度/深度优先遍历，避免栈溢出，普通业务场景下上述递归实现足够稳定。

内容的提问来源于stack exchange，提问作者d.Foo