表示树结构的列表的广度优先搜索

Question

我正在尝试开发一种算法，可以读取包含一些数据的字典键列表。

读入应用程序的列表示例

ID: 1 Level: 0 Data:"Animal"
ID: 2 Level: 1 Data:"Dog"
ID: 3 Level: 1 Data:"Cat"
ID: 4 Level: 1 Data:"Sheep"
ID: 5 Level: 2 Data:"Collie"
ID: 6 Level: 2 Data:"Dalmation"
ID: 7 Level: 3 Data:"Tabby"
ID: 8 Level: 4 Data:"Suffolk"
ID: 9 Level: 5 Data:"Jimmy"
ID: 10 Level: 6 Data:"Sally"

现在，如果我想搜索 "Sally"，程序将通过树结构读取到 return:

Sally is a dog of type dalmation

这可以通过以下逻辑计算：

Animal 位于树的顶部，Dog、Cat 和 Sheep 构成下一层。 Level 2 赋给 Level 1 的第一个元素，Level 3 赋给 Level 1 的第二个元素，Level 4 赋给 Level1 的第三个元素。因为 Level 1 已经被填写完毕我进入下一个级别；在本例中为级别 2。级别 2 有 2 个元素，因此级别 5 应用于第一个元素，级别 6 应用于第二个元素，在本例中 Sally 是 child Dalmation 是 Dog 的 child。

我认为广度优先搜索算法效果最好，因为较低的 ID 始终位于树上某个级别的左侧。我需要能够搜索树以找到值输入（在本例中为 Sally），然后在树中找到直接 link 到树顶部的其他值（Animal).

Answer 1

做 bfs/dfs 来回答一个查询说找到 "Sally" 就足够了。您将需要一个 hashtable H 这样当遍历树并且您在一个节点时说 x 然后只存储在 hash table x 的父级，H[x]=parent(x)。另请注意，您可以将根节点的父节点标记为根本身或某些值，例如 -1，让我们使用 -1.You 可以使用 bfs/dfs 来查找填充散列 table 的节点遍历。现在，如果你得到一个查询 "Sally"，在使用 bfs/dfs 找到 "Sally" 之后执行以下操作（不包含在伪代码中）：（它是一个伪代码，不在特定语言中）

           search_element = sally // element to be searched
           list=[] // empty list
           while H[search_element]! = -1
                list.append(H[search_element])
                search_element = H[search_element]

你的列表看起来像 [animal,dog,dalmation] 所以你可以从头开始遍历说 sally 是一种动物，它是一只狗，它是一只 dalmation。（或者其他什么你想要的顺序，因为你的树顺序有点混乱）。

表示树结构的列表的广度优先搜索

Breadth First Search of a list that represents a tree structure

algorithm

tree

list

breadth-first-search