用于将分层平面数据（带 ParentID）转换为带缩进级别的排序平面列表的算法

我有以下结构：

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. 根据所有对象的左值对包含所有对象的列表进行排序。

当我获得元素列表时，它们没有特定的顺序。兄弟姐妹应按其 Name 属性排序。

Update:这似乎是我自己没有尝试提出解决方案，只是希望其他人为我做这项工作。然而，我尝试提出三种不同的解决方案，但我都陷入了困境。原因之一可能是我试图避免递归（也许是错误的）。我不会发布迄今为止的部分解决方案，因为它们是不正确的，并且可能会严重影响其他人的解决方案。

我需要一个类似的算法来对具有依赖性的任务进行排序（每个任务可能有一个需要首先完成的父任务）。我发现拓扑排序。这是一个Python 中的迭代实现 http://www.bitformation.com/art/python_toposort.html有非常详细的评论。

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

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

维基百科给出另外两种拓扑排序算法 http://en.wikipedia.org/wiki/Topological_sorting#Algorithms。请注意，这些算法并不那么好，因为第一个算法是广度优先遍历，而第二个算法是递归的。