3

ツリーに編成された名前のフラットリストを返すストアドプロシージャがあります。Depth値が存在する親が誰であるかを伝えるために、5つのレコード（3レベルまで）の結果は次のようになります。

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

深さの値を読み取って、この配列からツリーを構築しようとしています。このような一連のデータからツリーを構築するための明らかなアルゴリズムはありますか？一般的なコンピュータサイエンスの回答は非常に役立ちますが、この問題に対するLINQyソリューションを受け入れているため、C＃タグを追加しています。

これが私の現在の試みです：

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

それはちょっと擬似コードです-y。エラー処理は追加されません。コードのセクションにメソッドが存在するふりをして、自分で理解できると思います。

于 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またはガスマーク6で300ミリ秒、または黄金色になるまで焼きます。

于 2012-08-27T17:08:01.273 に答える