3

我有一个存储过程，它返回按树组织的名称的平面列表。为了传达谁是有深度值的父级，因此 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 个级别，所以实际上我只是在寻找更容易推理的东西。

4

4 回答 4

3

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

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

结果：

使用给定数据：900 毫秒内 1,000,000 次

于 2012-08-27T17:09:06.353 回答
1 
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);
}

这有点像伪代码。它没有添加错误处理，我假设代码部分存在方法，我想你可以自己弄清楚。

于 2012-08-27T17:03:09.420 回答
1

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

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
于 2012-08-27T17:05:36.837 回答
1

原料：

  1. 允许子节点的类。
  2. 此类类型的堆栈。
  3. 此类类型的数组或列表。
  4. 用于存储当前深度的 int。
  5. 持有我们当前感兴趣的项目的本地人。

方法。

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

在编译器中以 200°C 或 Gas-mark 6 烘烤 300 毫秒，或直至金黄色。

于 2012-08-27T17:08:01.273 回答