我有以下结构：

MyClass {
  guid ID
  guid ParentID
  string Name
}

我想创建其中载有它们应显示在一个层次结构中的顺序元件的阵列（例如，根据它们的左的值），以及将映射的GUID到缩进级别的散列。

I'd like to create an array which contains the elements in the order they should be displayed in a hierarchy (e.g. according to their "left" values), as well as a hash which maps the guid to the indentation level.

例如：

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

这将从根本上产生以下对象：

This would essentially produce the following objects:

// 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

为了清楚起见，这是层次结构是这样的：

For clarity, this is what the hierarchy looks like:

Airplane
Animal
  Cats
    Tiger
Book

我想通过项迭代最少量的次可能的。我也不想来创建分层的数据结构。我倒是preFER使用数组，哈希表，栈，队列或

I'd like to iterate through the items the least amount of times possible. I also don't want to create a hierarchical data structure. I'd prefer to use arrays, hashes, stacks, or queues.

这两个目标是：

当我得到的元素列表，他们是在没有特定的顺序。兄弟姐妹应由其Name属性进行排序。

When I get the list of elements, they are in no particular order. Siblings should be ordered by their Name property.

更新：这似乎是我没试过想出一个解决方案，我自己，只是希望别人做的工作对我来说。不过，我曾试图想出三种不同的解决方案，而且我已经得到停留在每个。其中一个原因可能是，我已经试图避免递归（也许错的话）。我没有张贴的部分解决方案我到目前为止，因为它们是不正确的，可能会严重影响其他人的解决方案。

Update: This may seem like I haven't tried coming up with a solution myself and simply want others to do the work for me. However, I have tried coming up with three different solutions, and I've gotten stuck on each. One reason might be that I've tried to avoid recursion (maybe wrongly so). I'm not posting the partial solutions I have so far since they are incorrect and may badly influence the solutions of others.

推荐答案

Wonsungi的帖子帮了不少忙，不过这是一个通用图，而不是一棵树。所以，我修改了它颇有几分创建专门为一棵树而设计的算法：

Wonsungi's post helped a lot, however that is for a generic graph rather than a tree. So I modified it quite a bit to create an algorithm designed specifically for a tree:

// 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)