递归遍历 child 森林的算法

Question

请让我知道这是不好的做法还是某种坏事。事情是在我的程序中我需要创建一个遍历根元素和该元素的所有子节点的方法。我的元素是这样的:

|--ID--|--Parent--|--Additinal info--|
|  1   |    0     | root element     |
|  2   |    0     | root elemnet     |
|  3   |    1     |child element of 1|
|  4   |    1     |child element of 1|
|  5   |    3     |child element of 3|
--------------------------------------

现在，如果我想接收 ID 为 1 的元素的所有子元素(无论它有 1000 个子元素还是只有 2 个，就像本例中那样)，我希望我的方法也能把它带给我，但我不知道该怎么做？所有这些元素都在一个列表中，这就是我正在使用的。每次我找到一个元素时，我都需要检查它是否有任何子元素，子元素也是如此。这是因为我需要以正确的顺序输出元素。我一直在考虑也许可以做到，所以我先制作布局图，然后使用该图输出，但我有点坚持这个想法。

有什么线索吗？

Answer 1

像许多这些树问题一样，这里的神奇词是递归。您在表中描述的顺序是按 ID 排序，与深度或广度优先不完全匹配。但这没关系，您所需要的只是将节点放入一些数据结构中，这些数据结构将按照您想要的顺序返回它们。所以总体规划是

• 递归地“遍历”树以找到所有节点；将节点插入到按 ID 排序的数据结构中
• 打印有序节点

递归部分也很简单:

• 从根节点开始

• 如果根节点不在节点列表中，则添加它

• 取第一个子节点做同样的事情。

所以类似(伪代码):

dfs(node, nodelist):
   if node not in nodelist
      insert node in nodelist
   for each child node n
      dfs(n, nodelist)