将分层平面数据(w/ParentID)转换为带缩进级别的排序平面列表的算法

Question

我有以下结构:

MyClass {
  guid ID
  guid ParentID
  string Name
}

我想创建一个数组，其中包含按照元素应在层次结构中显示的顺序排列的元素(例如，根据它们的“左”值)，以及将 guid 映射到缩进级别的散列。

例如:

ID     Name     ParentID
------------------------
1      Cats     2
2      Animal   NULL
3      Tiger    1
4      Book     NULL
5      Airplane NULL

这基本上会产生以下对象:

// Array is an array of all the elements sorted by the way you would see them in a fully expanded tree
Array[0] = "Airplane"
Array[1] = "Animal"
Array[2] = "Cats"
Array[3] = "Tiger"
Array[4] = "Book"

// IndentationLevel is a hash of GUIDs to IndentationLevels.
IndentationLevel["1"] = 1
IndentationLevel["2"] = 0
IndentationLevel["3"] = 2
IndentationLevel["4"] = 0
IndentationLevel["5"] = 0

为清楚起见，层次结构如下所示:

Airplane
Animal
  Cats
    Tiger
Book

我想以尽可能少的次数遍历这些项目。我也不想创建分层数据结构。我更喜欢使用数组、散列、堆栈或队列。

这两个目标是:

1. 将 ID 的散列存储到缩进级别。
2. 根据左值对包含所有对象的列表进行排序。

当我得到元素列表时，它们没有特定的顺序。 sibling 应按其 Name 属性排序。

更新:这似乎是我没有尝试自己提出解决方案，而只是希望其他人为我完成工作。然而，我曾尝试提出三种不同的解决方案，但我都陷入了困境。原因之一可能是我试图避免递归(也许是错误的)。我不会发布目前的部分解决方案，因为它们不正确并且可能会对其他人的解决方案产生严重影响。

Answer 1

我需要一个类似的算法来对具有依赖性的任务进行排序(每个任务都可以有一个需要先完成的父任务)。我找到了拓扑排序。这是一个 iterative implementation in Python有非常详细的评论。

可以在进行拓扑排序时计算缩进级别。只需将节点的缩进级别设置为其父节点的缩进级别 + 1，因为它被添加到拓扑排序中。

请注意，可以存在许多有效的拓扑排序。为确保生成的拓扑顺序将父节点与子节点分组，选择基于偏序信息生成的图的深度优先遍历的拓扑排序算法。

维基百科给出 two more algorithms for topological sort .请注意，这些算法不是很好，因为第一个是广度优先遍历，第二个是递归。