23

階層内にアイテムのリストがあり、このリストを解析してオブジェクトの実際の階層にしようとしています。このリストを保存/反復するために、変更された事前注文ツリー トラバーサルを使用しているため、すべての子を含むツリーのサブセットが「左」の値で並べられています。

たとえば、次のツリーがあるとします。

  • アイテムA
    • アイテムA.1
    • アイテムA.2
      • アイテムA.2.2
  • アイテムB
    • 項目 B.1
  • アイテムC

リストを取得します：

  • アイテムA、アイテムA.1、アイテムA.2、アイテムA.2.2、アイテムB、アイテムB.1、アイテムC

(これは、変更された予約注文ツリーの設定の「左」の値の順です)。

私がやりたいことは、これをツリーの実際の構造を含むオブジェクトに解析することです。

Class TreeObject {
    String Name;
    Guid ID; 
    Guid ParentID;
    List<TreeObject> Children;
}

フラット リストは TreeObjects のリストとして返され、各 TreeObject には ID、ParentID、Left、Right のプロパティがあります。私が探しているのは関数です：

List<TreeObject> FlatToHeirarchy(List<TreeObject> list);

フラットリストを受け取り、ネストされたリストを返します。

言い換えると：

List<TreeObject> flatSet = LoadTreeObjectsFromDatabase(); 
// flatSet.count == 7; flatSet(0).Children == null
List<TreeObject> nestedSet = FlatToHeirarchy(flatSet);
// nestedSet.count == 3; nestedSet(0).Children.count == 2

私はこれを行う方法に途方に暮れています-親を追跡し、より大きなジャンプに対処できるようにします（たとえば、アイテムA.2.2->アイテムB）。

編集:ここでは、ブルートフォース以外のソリューションを探しています(たとえば、トップレベルの親だけが残るまで、アイテムを子ノードに移動したり、数回ループしたりしません)。一度ループして、必要に応じてアイテムを配置できるエレガントな方法があると思います。

覚えておいてください、それらは常に階層的な順序になっているため (私は MPTT を使用しているため)、特定のアイテムは常に前のアイテムの子または兄弟になるか、少なくとも前のアイテムと親を共有します。ツリーの他の場所に来ることは決してありません。

4

6 に答える 6

3

あなたはすでにすべてのアイテムの親を知っていると思います。

あなたがする必要があるのは、リストのすべてのアイテムを一度繰り返して、現在のアイテムをその親の子リストに追加することです。親のないアイテムのみをターゲットのネストされたリストに保持します。

ここにいくつかの擬似コードがあります：

foreach Item item in flatlist
   if item.Parent != null
      Add item to item.Parent.ChildrenList
      Remove item from flatlist
   end if
end for

親を取得することに関しては、あなたの例で私が見ることができることから、リストを進めるにつれて名前を解析してスタックを構築する必要があるかもしれません。

この問題は難しいように見えますが、実際にはそうではありません。多くの人がこの問題を間違った角度から見ています。すべての子リストにデータを入力するのではなく、フラットリストから子アイテムを削除する必要があります。そうすれば簡単になります。

于 2008-11-25T22:31:06.923 に答える
1

正常にコンパイルされる代替バージョンですが、上記のコードに問題があるかどうかはわかりませんでした。

private List<Page> FlatToHierarchy(List<Page> list) {
      // hashtable lookup that allows us to grab references to the parent containers, based on id
        Dictionary<int, Page> lookup = new Dictionary<int, Page>();
      // actual nested collection to return
      List<Page> nested = new List<Page>();

      foreach(Page item in list) {
        if (lookup.ContainsKey(item.parentId)) {
          // add to the parent's child list 
          lookup[item.parentId].children.Add(item); //add item to parent's childs list
          lookup.Add(item.pageId, item); //add reference to page in lookup table
        } else {
          // no parent added yet (or this is the first time)
          nested.Add(item);     //add item directly to nested list                
          lookup.Add(item.pageId, item); //add reference to page in lookup table
        }
      }
    return nested;
    }
于 2011-09-05T23:27:59.647 に答える
0

gregmacによって与えられた例を修正する

IList<TreeObject> FlatToHierarchy(IQueryable<lcc_classe> list, int? parentId)
    {
        var q = (from i in list
                where i.parent_id == parentId
                select new
                {
                    id = i.id,
                    parent_id = i.parent_id,
                    kks = i.kks,
                    nome = i.nome
                }).ToList();
        return q.Select(x => new TreeObject
            {
                children = FlatToHierarchy(list, x.id)
            }).ToList();
    }
于 2014-02-28T17:44:42.217 に答える
0

ここに例があります。これが役立つことを願っています

class Program
{
    static void Main(string[] args)
    {
        TreeObject a  = new TreeObject() { Name = "Item A" };
        a.Children.Add( new TreeObject() { Name = "Item A.1" });
        a.Children.Add( new TreeObject() { Name = "Item A.2" });

        TreeObject b = new TreeObject() { Name = "Item B" };
        b.Children.Add(new TreeObject() { Name = "Item B.1" });
        b.Children.Add(new TreeObject() { Name = "Item B.2" });

        TreeObject c = new TreeObject() { Name = "Item C" };

        List<TreeObject> nodes = new List<TreeObject>(new[] { a, b, c });

        string list = BuildList(nodes);
        Console.WriteLine(list); // Item A,Item A.1,Item A.2,Item B,Item B.1,Item B.2,Item C

        List<TreeObject> newlist = new List<TreeObject>();
        TreeObject temp = null;

        foreach (string s in list.Split(','))
        {
            if (temp == null || !s.Contains(temp.Name) || temp.Name.Length != s.Length)
            {
                temp = new TreeObject() { Name = s };
                newlist.Add(temp);
            }
            else
            {
                temp.Children.Add(new TreeObject() { Name = s });
            }                              
        }

        Console.WriteLine(BuildList(newlist)); // Item A,Item A.1,Item A.2,Item B,Item B.1,Item B.2,Item C
    }

    static string BuildList(List<TreeObject> nodes)
    {
        StringBuilder output = new StringBuilder();
        BuildList(output, nodes);
        return output.Remove(output.Length - 1, 1).ToString();
    }

    static void BuildList(StringBuilder output, List<TreeObject> nodes)
    {
        foreach (var node in nodes)
        {
            output.AppendFormat("{0},", node.Name);
            BuildList(output, node.Children);
        }
    }
}

public class TreeObject
{
    private List<TreeObject> _children = new List<TreeObject>();

    public string Name { get; set; }
    public Guid Id { get; set; }
    public List<TreeObject> Children { get { return _children; } }
}

}

于 2008-11-25T23:19:26.483 に答える