将深度数组转换为树的高效算法

Question

我有一个存储过程，它返回一个按树形结构组织的平面名称列表。为了确定每个名称的父级关系，需要使用Depth值。例如，当返回5条记录时（共3层），结果如下：

Depth|Name
----------
    0|Ford
    1|Compact Cars
    2|Pinto
    1|Trucks
    2|H-Series

我正在尝试通过读取深度值来构造一棵树。有没有显而易见的算法可以将这个数组序列构造成一棵树？我添加了C#标签，因为我可以接受使用LINQ解决此问题，但一般的计算机科学答案也将非常有帮助。

以下是我的当前尝试：

class Record
{
  public string Name{ get; set; }
  public List<Record> children { get; set; }
}

var previousLevel = 0;
var records = new List<Record>();

foreach (var thing in TreeFactory.fetch(dao))
{
  if(this.Depth == 0) {
    //Root node
  } else if(thing.Depth > previousLevel) {
    //A Child of the last added node
  } else if(thing.Depth < previousLevel) {
    //A Cousin of the last added node
  } else {
    //A Sibling of the of the last added node
  }
  previousLevel = this.Depth;
}

所谓“高效”，指的是列表大小达到200,000个元素和树深度达到100级，因此我只是希望找到一些更容易理解的东西。

- Jason Sperske

---

我的当前代码从一个简单的List<Record>开始，其中Record包含一个名为Children的List<Record>。然后我保留先前深度的副本并进行测试。如果新深度等于先前深度，则是兄弟节点；如果新深度大于先前深度，则是子节点；如果新深度小于先前深度，则是最近添加的父节点的兄弟节点。我说“尝试”，因为代码变得相当混乱。 - Jason Sperske

这些downvote是因为问题表述含糊不清还是因为使用了福特汽车作为例子？ - Jason Sperske

我猜测 Pinto 汽车永远无法摆脱它们易燃的时期。 - Jon Hanna

当你说你需要一个高效的解决方案时，你的数据集有多大？你真的有数十万个项目要添加，或者有成千上万个类似的列表要填充，还是只是因为“效率总是好”的原因而说出来的？ - Servy

Answer 1

这里不需要递归。我相信最快的方法是这样的：

public static TreeView TreeFromArray(Item[] arr)
{
    var tv = new TreeView();
    var parents = new TreeNodeCollection[arr.Length];
    parents[0] = tv.Nodes;

    foreach (var item in arr)
    {
        parents[item.Depth + 1] = parents[item.Depth].Add(item.Name).Nodes;
    }

    return tv;
}

Item是任何具有深度和名称信息的东西：

public class Item
{
    public int Depth;
    public string Name;
}

当使用自己实现的TreeNode时，为了简化过程并剥离不必要的功能以减慢整个过程的速度，并稍微修改方法以适应这些变化，我想到了这个：

类:

    public class Node
    {
        public string Name;
        public List<Node> Childs = new List<Node>();
    }

    public class Item
    {
        public int Depth;
        public string Name;
    }

实现：

    public static Node TreeFromArray(Item[] arr)
    {
        var tree = new Node();

        var parents = new Node[arr.Length];
        parents[0] = tree;

        foreach (var item in arr)
        {
            var curr = parents[item.Depth + 1] = new Node {Name = item.Name};
            parents[item.Depth].Childs.Add(curr);
        }

        return tree;
    }

结果：

根据给定的数据：1,000,000次在900毫秒内完成

（Note: 为了保持格式一致，我没有翻译“Results”这个单词）

- SimpleVar

---

嗯...是的，这只是我脑海中浮现的第一件事情，所以我觉得这是一个显而易见的解决方案。确实，没有必要提及它。 - SimpleVar

不管递归的必要性或非必要性如何，我打算实现这个解决方案，但遇到了一些问题。我认为foreach块需要一个特殊情况来处理根节点，否则第一个节点会成为父节点[0]的子节点。 - Jason Sperske

@JasonSperske 的想法是树的根节点将作为所有零深度子节点的容器。如果您知道只会有一个零深度节点（并且是第一个），那么您可以将parents [0]设置为它，而不是新的（然后无用的）根节点（或树）。 - SimpleVar

已实现（只有一个小改动，返回行现在为“return tree.Children;”，我必须说，这很快速且易于理解。） - Jason Sperske

@JasonSperske 很高兴你觉得它有用 :) - SimpleVar

Answer 2

public void AddNode(Tree tree, Node nodeToAdd, int depth)
{
  //you might need to add a special case to handle adding the root node
  Node iterator = tree.RootNode;  
  for(int i = 0; i < depth; i++)
  {
    iterator = iterator.GetLastChild(); //I assume this method won't exist, but you'll know what to put here
  }

  iterator.AddChild(nodeToAdd);
}

这有点伪代码的感觉。它没有添加错误处理，并且我假装方法存在于我想象中你自己可以理解的代码部分。

- Servy

Answer 3

这个数组看起来像是原始树结构从左到右的“展开”。如果可以安全地假设如此，那么方法就很简单：

For each element in the array
   If the depth of the element is less than or equal to the "current node"
      traverse upwards to the parent until current depth = element depth -1
   Create a child node of the current node
   Traverse to that node as the new "current" node

- KeithS

Answer 4

材料：

1. 一个允许子节点的类。
2. 一个这个类类型的堆栈。
3. 一个这个类类型的数组或列表。
4. 一个整数来存储当前深度。
5. 一个本地变量来保存我们当前感兴趣的项。

方法：

1. 从列表中取出第一项。将其放入堆栈中。将 0 作为当前深度存储。
2. 依次取出列表中的每个剩余项。查看其深度。如果深度等于或小于当前深度，则从堆栈中弹出（currentdepth - depth + 1）个项，并在堆栈中查看以获取新的当前项。将我们的新项设置为“当前项”的子项，将其设置为当前项，将其深度设置为当前深度。

在200°C或燃气6号下的编译器中烘烤300毫秒，或者直到金黄色。

- Jon Hanna