53

カテゴリのリストがあります：

╔════╦═════════════╦═════════════╗
║ Id ║ Name        ║ Parent_id   ║
╠════╬═════════════╬═════════════╣
║ 1  ║ Sports      ║ 0           ║
║ 2  ║ Balls       ║ 1           ║
║ 3  ║ Shoes       ║ 1           ║
║ 4  ║ Electronics ║ 0           ║
║ 5  ║ Cameras     ║ 4           ║
║ 6  ║ Lenses      ║ 5           ║
║ 7  ║ Tripod      ║ 5           ║
║ 8  ║ Computers   ║ 4           ║
║ 9  ║ Laptops     ║ 8           ║
║ 10 ║ Empty       ║ 0           ║
║ -1 ║ Broken      ║ 999         ║
╚════╩═════════════╩═════════════╝

各カテゴリには親があります。親が 0 の場合、それはルート カテゴリであることを意味します。

以下のようなツリー構造に変換する最も良い方法は何ですか?

Sport
 ├ Balls
 └ Shoes

Electronics
 ├ Cameras
 │  ├ Lenses
 │  └ Tripod
 │
 └ Computers
    └ Laptops

Empty

つまり、この構造からデータを取得する方法は次のとおりです。

class category
{
    public int Id;
    public int ParentId;
    public string Name;
}

これに：

class category
{
    public int Id;
    public int ParentId;
    public string Name;

    public List<Category> Subcategories;
}

普遍的な方法で？// Universal は、言及されたクラスだけではないことを意味します。

賢いアイデアはありますか？;)

データ：

var categories = new List<category>() {
    new category(1, "Sport", 0),
    new category(2, "Balls", 1),
    new category(3, "Shoes", 1),
    new category(4, "Electronics", 0),
    new category(5, "Cameras", 4),
    new category(6, "Lenses", 5),  
    new category(7, "Tripod", 5), 
    new category(8, "Computers", 4),
    new category(9, "Laptops", 8),
    new category(10, "Empty", 0),
    new category(-1, "Broken", 999),
};
4

10 に答える 10

70

ユニバーサルメソッドが必要な場合は、追加のクラスが必要です。

public class TreeItem<T>
{
    public T Item { get; set; }
    public IEnumerable<TreeItem<T>> Children { get; set; }
}

次に、このヘルパーで使用します。

internal static class GenericHelpers
{
    /// <summary>
    /// Generates tree of items from item list
    /// </summary>
    /// 
    /// <typeparam name="T">Type of item in collection</typeparam>
    /// <typeparam name="K">Type of parent_id</typeparam>
    /// 
    /// <param name="collection">Collection of items</param>
    /// <param name="id_selector">Function extracting item's id</param>
    /// <param name="parent_id_selector">Function extracting item's parent_id</param>
    /// <param name="root_id">Root element id</param>
    /// 
    /// <returns>Tree of items</returns>
    public static IEnumerable<TreeItem<T>> GenerateTree<T, K>(
        this IEnumerable<T> collection,
        Func<T, K> id_selector,
        Func<T, K> parent_id_selector,
        K root_id = default(K))
    {
        foreach (var c in collection.Where(c => EqualityComparer<K>.Default.Equals(parent_id_selector(c), root_id)))
        {
            yield return new TreeItem<T>
            {
                Item = c,
                Children = collection.GenerateTree(id_selector, parent_id_selector, id_selector(c))
            };
        }
    }
}

使用法：

var root = categories.GenerateTree(c => c.Id, c => c.ParentId);

テスト:

static void Test(IEnumerable<TreeItem<category>> categories, int deep = 0)
{
    foreach (var c in categories)
    {
        Console.WriteLine(new String('\t', deep) + c.Item.Name);
        Test(c.Children, deep + 1);
    }
}
// ...
Test(root);

出力

Sport
    Balls
    Shoes
Electronics
    Cameras
        Lenses  
        Tripod
    Computers
        Laptops
Empty
于 2013-10-29T02:04:11.637 に答える
33 
foreach (var cat in categories)
{
    cat.Subcategories = categories.Where(child => child.ParentId == cat.Id)
                                  .ToList();
}

O(n*n)コンプレックスが出てきます。

より最適化された方法は、ルックアップ テーブルを使用することです。

var childsHash = categories.ToLookup(cat => cat.ParentId);

foreach (var cat in categories)
{
    cat.Subcategories = childsHash[cat.Id].ToList();
}

これはあなたにO(2*n)≈を与えますO(n)

その結果、次の構造が得られます (LinqPad から表示):

ここに画像の説明を入力

于 2013-10-29T01:41:56.053 に答える
3

ここに私がホイップした小さな例があります。それはかなり「ジェネリック」です。

インターフェイスを定義することで汎用的なアプローチを作成することもできます (これにより、関数の引数を単純化できます)。しかし、私はそうしないことにしました。いずれにせよ、「マッパー」とセレクター関数により、これは異なるタイプ間で機能します。

また、これは非常に効率的な実装ではないことに注意してください(すべてのサブツリーの可能なすべての子を保持し、繰り返し反復するため)、特定のタスクには適している場合があります。過去に、Dictionary<key,collection>より良い境界を持つアプローチも使用しましたが、そのように書く気がしませんでした:)

これは「LINQPad C# プログラム」として実行されます。楽しみ！

// F - flat type
// H - hiearchial type
IEnumerable<H> MakeHierarchy<F,H>(
    // Remaining items to process
    IEnumerable<F> flat,
    // Current "parent" to look for
    object parentKey,
    // Find key for given F-type
    Func<F,object> key,
    // Convert between types
    Func<F,IEnumerable<H>,H> mapper,
    // Should this be added as immediate child?
    Func<F,object,bool> isImmediateChild) {

    var remainder = flat.Where(f => !isImmediateChild(f, parentKey))
        .ToList();

    return flat
        .Where(f => isImmediateChild(f, parentKey))
        .Select(f => {
            var children = MakeHierarchy(remainder, key(f), key, mapper, isImmediateChild);
            return mapper(f, children);
        });
}

class category1
{
    public int Id;
    public int ParentId;
    public string Name;

    public category1(int id, string name, int parentId) {
        Id = id;
        Name = name;
        ParentId = parentId;
    }
};

class category2
{
    public int Id;
    public int ParentId;
    public string Name;

    public IEnumerable<category2> Subcategories;
};

List<category1> categories = new List<category1>() {
    new category1(1, "Sport", 0),
    new category1(2, "Balls", 1),
    new category1(3, "Shoes", 1),
    new category1(4, "Electronics", 0),
    new category1(5, "Cameras", 4),
    new category1(6, "Lenses", 5),  
    new category1(7, "Tripod", 5), 
    new category1(8, "Computers", 4),
    new category1(9, "Laptops", 8),
    new category1(10, "Empty", 0),
    new category1(-1, "Broken", 999),
};

object KeyForCategory (category1 c1) {
    return c1.Id;
}

category2 MapCategories (category1 c1, IEnumerable<category2> subs) {
    return new category2 {
        Id = c1.Id,
        Name = c1.Name,
        ParentId = c1.ParentId,
        Subcategories = subs,
    };
}

bool IsImmediateChild (category1 c1, object id) {
    return c1.ParentId.Equals(id);
}

void Main()
{
    var h = MakeHierarchy<category1,category2>(categories, 0,
        // These make it "Generic". You can use lambdas or whatever;
        // here I am using method groups.
        KeyForCategory, MapCategories, IsImmediateChild);
    h.Dump();
}
于 2013-10-29T02:28:31.543 に答える
1

より簡単な解決策があり
ます。メモリ内に新しいノード オブジェクトを作成する必要はありません。ソース リストには既にオブジェクトがあります。正しく記入してChildrenください。
Node他の論理ユニットのベースとなるクラス。、などのようにPath見えます。 and の代わりにandを使用できます。1.11.2.12
PathParentPathIdParentId

    public abstract class Node
    {
        public int Id { get; set; }
        public string Name { get; set; }
        public string Path { get; set; }
        public string ParentPath
        {
            get
            {
                var lastDotPosition = Path.LastIndexOf('.');
                return lastDotPosition == -1 ? null : Path.Substring(0, lastDotPosition );
            }
        }
        public IEnumerable<Node> Children { get; set; }
    }

再帰的拡張方法:

public static class TreeExtension
{
    public static IEnumerable<T> GenerateTree<T>(this IEnumerable<T> table, T rootNode) where T : Node
    {
        var organizationalNodes = table.ToList();
        var rootNodes = organizationalNodes.Where(node => node.ParentPath == rootNode?.Path).ToList();

        foreach (var node in rootNodes)
        {
            node.Children = organizationalNodes.GenerateTree(node);
        }

        return rootNodes;
    }
}

使用法：

public class RegionNode : Node
{
    public string timezone {get; set;}
}

データベースからテーブルを取得し、ツリーを生成します。

var result = await _context.GetItemsAsync<RegionNode>();
return result.GenerateTree( null);
于 2020-07-29T09:07:08.500 に答える