Linq查询递归

Question

我使用C#和Entity framework。我有一个名为Genre的数据库表，它具有以下属性：idGenre、name、idParentGenre。

例如，它们的值可能是：

(idGenre = 1, name = "acoustic", idParentGenre=2)

(idGenre = 2, name = "rock", idParentGenre=2)

(idGenre = 3, name = "country", idParentGenre=4)

(idGenre = 4, name = "folk", idParentGenre=5)

(idGenre = 5, name = "someOtherGenre", idParentGenre=5)

正如您所看到的，这是一种树形结构。

现在，我有一个搜索该表的方法。输入参数是idGenre和idParentGenre。我需要返回genre（idGenre）是否是idParentGenre的子/孙/曾孙……。

例如，当我得到idGenre=3，idParentGenre=5时，我应该返回true。

然而，在Linq中没有递归。有没有办法可以做到这一点？

- petko_stankoski

---

“Linq中的递归”是什么意思？你能展示一下你的方法吗？它有什么问题？ - alf

老方式来做。LINQ 很棒，但它不能解决所有问题。 - cadrell0

Answer 1

我会创建一个方法来处理这个问题，而不是使用LINQ：

bool HasParent(int genre, int parent)
{
    Genre item = db.Genres.FirstOrDefault(g => g.IdGenre == genre);
    if (item == null)
        return false;

    // If there is no parent, return false, 
    // this is assuming it's defined as int?
    if (!item.idParentGenre.HasValue)
        return false;

    if (item.idParentGenre.Value == parent)
        return true;

    return HasParent(item.idParentGenre, parent);
}

这让你可以在一个递归函数中处理它。

- Reed Copsey

Answer 2

看起来你正在尝试实现一棵树，但又不想使用树结构。

你有没有考虑过...使用树结构呢？这里有一个很好的问题以及一些答案，你可以从中获取灵感（其中包括一个带有代码的答案）：

delegate void TreeVisitor<T>(T nodeData);

class NTree<T>
{
    T data;
    LinkedList<NTree<T>> children;

    public NTree(T data)
    {
        this.data = data;
        children = new LinkedList<NTree<T>>();
    }

    public void addChild(T data)
    {
        children.AddFirst(new NTree<T>(data));
    }

    public NTree<T> getChild(int i)
    {
        foreach (NTree<T> n in children)
            if (--i == 0) return n;
        return null;
    }

    public void traverse(NTree<T> node, TreeVisitor<T> visitor)
    {
        visitor(node.data);
        foreach (NTree<T> kid in node.children)
            traverse(kid, visitor);
    }        
}

- Jesse Smith

---

我不能使用树结构。我在我的数据库中有一个表格来实现这个目的。 - petko_stankoski

Answer 3

将流派表格存储在内存中（不能太大），并递归遍历它以创建一个映射，将idGenre与其后代的传递闭包对应起来，如下所示：

1: {1, 2}
2: {2}
3: {3, 4, 5}
4: {4, 5}
5: {5}

上述数据仅存储在内存中。每次启动和更新流派表时都需要重新计算。

当需要查询特定流派中的所有歌曲时，请在idGenre in ...查询中使用预先计算好的表，如下所示：

IEnumerable<Song> SongsWithGenreId(int idGenre) {
    var idClosure = idToIdClosure[idGenre];
    return context.Songs.Where(song => idClosure.Contains(song.idGenre));
}

- Sergey Kalinichenko

---

但这不是一个完美的解决方案。我已经有一个放置父级ID的地方（这个地方是表格），我不认为另一个用于同样目的的地方是好的。 - petko_stankoski

@Srcee 这不是“另一个地方”来存储您的数据，它是相同数据的缓存，只是预处理。您的查询将非常快-比迄今为止提出的任何其他建议都要快得多，因为只有一次往返。所有递归都将嵌入到“idToIdClosure”字典的结构中，这很好，因为流派并不经常更改。 - Sergey Kalinichenko