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

Question

我有一个存储过程，它返回按树组织的名称的平面列表。为了传达谁是有深度值的父级，所以 5 条记录(上升到 3 级)的结果如下所示:

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

我试图通过读取深度值从这个数组中构建一个树。是否有一些明显的算法可以从这样的数据序列中构建树？我添加 C# 标签是因为我对 LINQy 解决这个问题持开放态度，尽管通用的计算机科学答案会非常有帮助。

这是我目前的尝试:

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 个级别，所以实际上我只是在寻找更容易推理的东西。

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;
}

项目是任何具有深度和名称信息的东西:

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;
    }

结果:

With the given data: 1,000,000 times in 900 milliseconds