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

Question

我有以下结构：

MyClass {
  guid ID
  guid ParentID
  string Name
}

我想创建一个数组，其中包含按元素应在层次结构中显示的顺序排列的元素（例如，根据其“ left”值），以及将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属性排序。

更新：看来我似乎没有尝试过自己想出一个解决方案，而只是希望别人为我完成工作。但是，我尝试提出三种不同的解决方案，但每种方法我都陷入困境。原因之一可能是我试图避免递归（也许是错误的）。我不会发布到目前为止的部分解决方案，因为它们不正确，可能会严重影响其他解决方案。

Answer 1

Wonsungi 的帖子很有帮助，但那是针对通用图而不是树。所以我对它进行了相当多的修改，创建了一个专门为树设计的算法：

// Data strcutures:
nodeChildren: Dictionary['nodeID'] = List<Children>;
indentLevel: Dictionary['nodeID'] = Integer;
roots: Array of nodes;
sorted: Array of nodes;
nodes: all nodes

// Step #1: Prepare the data structures for building the tree
for each node in nodes
  if node.parentID == NULL
    roots.Append(node);
    indentLevel[node] = 0;
  else
    nodeChildren[node.parentID].append(node);

// Step #2: Add elements to the sorted list
roots.SortByABC();
while roots.IsNotEmpty()
  root = roots.Remove(0);
  rootIndentLevel = indentLevel[root];
  sorted.Append(root);
  children = nodeChildren[root];
  children.SortByABC();
  for each child in children (loop backwards)
    indentLevel[child] = rootIndentLevel + 1
    roots.Prepend(child)