JavaScript/TypeScript中如何最优表示同类型节点的未知深度树结构？

你当前设计的「单节点类+父引用存储」是适配「自底向上查父级」需求的最优基础结构，对比仅存储子引用的传统树结构，你的基础方案查询父级的时间复杂度已经从O(n)（n为总节点数）降到了O(k)（k为当前节点深度），在此基础上可以从以下两个方向做进一步优化：

一、计算效率优化（内存不敏感场景） #

• 新增父级路径缓存：在节点内部存储已经查询到的父级列表，首次查询后缓存结果，后续相同查询直接返回缓存，时间复杂度降到O(1)。仅当节点的父级关联发生变更时，才需要清空缓存重新构建。
• 版本号批量缓存管理：如果存在大量节点父子关系批量更新的场景，可以给整个树实例加全局版本号，每次批量更新后版本号+1，节点缓存时同步存储当前版本号，查询时对比版本号判断缓存是否过期，无需逐个节点清除缓存。
• 层级索引缓存：如果有按层级取父级的需求，可以将缓存的父级列表按「直接父级→祖父级→根节点」的顺序存储，要取第N层父级时直接通过数组下标取值，无需二次遍历。

二、可维护性提升方案 #

• 封装内部状态：将父引用、缓存字段设为私有属性，对外仅暴露setParent()、getAncestors()等公开方法，父子关系修改、缓存更新逻辑全部收拢在类内部实现，避免外部直接修改属性导致的缓存不一致问题。
• 泛型适配多业务场景：使用TS泛型约束节点数据类型，无需为不同业务的节点数据重写节点类，复用通用逻辑。
• 内置常用工具方法：将getRoot()（获取根节点）、isAncestorOf(target: TreeNode)（判断是否为某节点的父级）等通用逻辑封装在类内部，减少业务层重复编码。
• 新增循环引用校验：在setParent()方法中增加校验逻辑，判断待设置的父节点是否为当前节点的子节点，避免出现环导致父级遍历时死循环。

参考TypeScript实现 #

class TreeNode<T = unknown> {
  // 对外暴露的节点自定义数据
  public data: T;
  // 私有父节点引用，禁止外部直接修改
  #parent: TreeNode<T> | null = null;
  // 私有父级列表缓存
  #ancestorsCache: TreeNode<T>[] | null = null;

  constructor(data: T) {
    this.data = data;
  }

  /**
   * 设置当前节点的父节点
   */
  public setParent(parent: TreeNode<T> | null): void {
    // 循环引用校验：如果待设置的父节点是当前节点的子节点，抛出错误
    if (parent && parent.isAncestorOf(this)) {
      throw new Error('无法设置子节点为父节点，会产生循环引用');
    }
    this.#parent = parent;
    // 父级变更后清空缓存
    this.#ancestorsCache = null;
  }

  /**
   * 获取当前节点的所有父级列表
   * @param includeSelf 是否在返回结果中包含当前节点本身
   */
  public getAncestors(includeSelf = false): TreeNode<T>[] {
    if (this.#ancestorsCache) {
      return includeSelf ? [this, ...this.#ancestorsCache] : [...this.#ancestorsCache];
    }
    const ancestors: TreeNode<T>[] = [];
    let current = this.#parent;
    while (current) {
      ancestors.push(current);
      current = current.#parent;
    }
    this.#ancestorsCache = ancestors;
    return includeSelf ? [this, ...ancestors] : [...ancestors];
  }

  /**
   * 获取当前节点所属树的根节点
   */
  public getRoot(): TreeNode<T> {
    const ancestors = this.getAncestors();
    return ancestors.length ? ancestors[ancestors.length - 1] : this;
  }

  /**
   * 判断当前节点是否为目标节点的父级
   */
  public isAncestorOf(target: TreeNode<T>): boolean {
    return target.getAncestors().includes(this);
  }
}

可选增强方案 #

如果存在跨节点的批量父级查询需求，可以额外新增全局WeakMap缓存统一管理所有节点的父级列表，无需在每个节点内部存储缓存，适配需要统一管控缓存生命周期的场景，单节点查询效率和节点内缓存方案一致。

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