TypeScript 中异步/等待递归树遍历

Question

我有如下简单的树结构：

class Group {
  id: ObjectId;
  name: string;
  subGroups: [ObjectId]
}

例如A组有两个子组B、C组，C组有三个子组F、G、H等

我需要实现一个算法来递归地获取所有组： 预期产出 = [A组、B组、C组、D组、E组、F组、G组、H组、I组、J组]

但是我需要从数据库中获取子组，以便它应该是异步/等待的。

方法1

    const tr = async (group: Group, result: Group[]) => {
      console.log(group);
      result.push(group);
      for (const id of group.subGroups) {
        const groupId = id.toHexString();
        const subGroup = this.findGroup(groupId);
        tr(await subGroup, result);
      }
    };

    const result = [];
    await tr(user.group, result);
    console.log(result);

方法2

  async transverse(group: Group, result: Group[]) {
    console.log(group);
    result.push(group);
    for (const id of group.subGroups) {
      const groupId = id.toHexString();
      const subGroup = await this.findGroup(groupId);
      await this.transverse(subGroup, result);
    }
  }

  const result = [];
  await transverse(user.group, result);
  console.log(result);

方法1无法输出正确的数组，也没有输出完成的Gourp A到J。方法2可以得到正确的数组，但代码看起来不干净。有谁知道如何以优雅的方式实现这个目标并回答我为什么方法1不起作用？

Answer 1

您可以利用一些现代功能（例如异步生成器）来遍历树。

正如您给出的示例所示，遍历是广度优先的，我不会进行递归，而是在树的每个级别上进行循环迭代。当 Group 对象位于同一级别时，可以“并行”解析它们，因为这些结果彼此不依赖。这是一个很好的用例，可以为每个节点使用

Promise.all

而不是单独的

await

。

这是它的样子——我已经包含了数据库部分的模拟：

class Group {
    constructor(id, subGroups) {
        this.id = id;
        this.subGroups = subGroups;
    }
}

// Mock of asynchronous DB
const delay = ms => new Promise(resolve => setTimeout(resolve, ms));
const db = {
    _tree: {
        "A": ["B", "C"],
        "B": ["D", "E"],
        "C": ["F", "G", "H"],
        "D": [],
        "E": [],
        "F": ["I", "J"],
        "G": [],
        "H": [],
        "I": [],
        "J": []
    },
    async findGroup(groupId) {
        await delay(Math.random() * 1000);
        return new Group(groupId, db._tree[groupId]);
    }
};

// Make an async generator
async function* tr(groupId) {
    let result = [await db.findGroup(groupId)];
    while (result.length) {
        yield* result;
        // Use Breadth-first traversal order, and allow some parallellism
        result = await Promise.all(result.flatMap(group => group.subGroups.map(db.findGroup)));
    }
};

// Consume the async iterator you get from the above function. The call starts with the id of the tree's root:
(async () => {
    for await (const result of tr("A")) {
        console.log(result);
    }
})();

Answer 2

好的，所以你的班级看起来像这样

class Group {
  id: ObjectId;
  name: string;
  subGroups: [ObjectId]
} 

我们需要定义我们需要什么 所以， 预期输出是：

【A组、B组、C组、D组、E组、F组、G组、H组、I组、J组

换句话说，我们需要按以下方式循环： 分组 -> 所有子项并重复。

我们可以使用一个变量来保存下一组，然后循环遍历它。 该变量将使用您获取的第一个组（例如组 A）进行初始化，然后循环将打印它的名称，循环遍历它的子项，并将每个子项保存为我们刚刚创建的打印到变量的下一个。 当我们完成对孩子们的循环后，我们将删除主要组。

我们将使用 while 循环，仅当 nextToPrint 变量为空数组时才会停止。

nextToPrint = []; // variable to hold the next groups to print so it will need to be initialized with groupA.


// some method that runs when your app starting, like mounted() on Vue, attached() on aureliaJS or ngOnInit on Angular
async someMethod() {
  const first = await getGroup(first) // get first group
  nextToPrint.push(first); // push to the queue-like variable


  // loop through the next to print 
  while(nextToPrint.length) {
      printGroup(nextToPrint[0]); // print first item in the next list
  }
}

async printGroup(group: Group) {
   console.log(group.name); // print Group name
   group.subGroups.forEach(g => {
       const child = await getGroup(g); // send it to get the next group
       nextToPrint.push(child); // add child to be the last one to print
       console.log(child.name); // print the child name
   });

   nextToPrint.shift(); // remove first element from the next to print
}

希望它能有所帮助，请随时发表评论并提出更多问题，直到我们解决为止