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

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”，程序将读取树结构并返回:

Sally is a dog of type dalmation

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

Animal 位于树的顶部，Dog、Cat 和 Sheep 构成下一层。 Level 2 赋给Level 1 的第一个元素，Level 3 赋给Level 1 的第二个元素，Level 4 赋给Level 的第三个元素 1. 因为Level 1 已经填写了I移动到下一个级别；在本例中为级别 2。级别 2 有 2 个元素，因此级别 5 应用于第一个元素，级别 6 应用于第二个元素，在本例中 Sally 是 Dalmation 是 Dog 的子代。

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

Answer 1

做 bfs/dfs 来回答一个查询说找到“Sally”就足够了。您将需要一个哈希表 H 以便在遍历树时您在一个节点处说 x 然后只需将 x 的父级存储在哈希表中>, H[x]=parent(x)。另请注意，您可以将根节点的父节点标记为根本身或某个值，例如 -1，让我们使用 -1。您可以使用 bfs/dfs 在遍历时查找填充哈希表的节点。现在，如果你得到一个查询“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 is an animal, its a dog, its a dalmation.(或者任何你想要的顺序，因为你的树顺序有点困惑)。