如何在仅给定子元素的情况下用 C# 构建树？

Question

我有一组属于树的元素。我只关心祖先，不关心孩子。例如，我希望树看起来像这样：

1. 烧烤用品*
2. 家居清洁用品
1. 空气清新剂
1. Car Airfreshner*
2. 纸巾*
3. 餐具
1. 叉子*

我得到的唯一输入是带星号的元素。所以我有这样的东西：

List<Categories> categories = new List<Categories>("Forks", "Paper Towels", "Car Airfreshner", "Barbeque Supplies");

类别看起来像这样：

string Id;
Category Parent;
IList<Category> Children;
Category RootNode; // e.g., "Household cleaning supplies"

不幸的是，完整的树相当大......〜17,000 个项目。但该列表基本上永远不会改变，所以如果我必须做任何事情来修改它以使其更容易访问，我愿意这样做。

我正在使用 NHibernate，并且尝试了几种方法：

public IList<Categories> CompleteTree(IList<Categories> inputList) {
            var result = new List<Categories>();
            foreach (var item in inputList) {
                var recursiveItem = categoryRepository.Get(item);

                while (recursiveItem != null) {
                    result.Add(recursiveItem);
                    recursiveItem = item.Parent;
                }
            }    
            return result;
        }

无论如何，这对数据库的影响很大？如果有任何巧妙的代码的话，我正在使用 NHibernate 2。

我见过 Ayende 的博客文章， 但他正在研究儿童项目，我从儿童项目开始，然后我正在努力向上。或者我可能会做和他一样的事情，但只是没有意识到。

编辑：添加了categoriesRepository，以便更清楚地表明我正在访问数据库。

Answer 1

免责声明：由于我没有 NHibernate 的经验，所以我在这里冒险。

Ayende 的博客post 使用 join fetch 语句，这是 NHibernate 特定的 SQL，称为 HQL。由于 NHibernate 只是数据库之上的另一层，而 SQL 数据库并不是为处理层次结构而设计的，因此它仍然需要递归查询来获取整个树。

但 Ayende 还在 他的评论之一认为，如果直接关系和间接关系都存储在数据库中，查询树会更容易。他提到了这样的结构：

Ancestor                      Descendant        IsChild
-------------------------------------------------------
Household cleaning Supplies   Air fresheners    True
Household cleaning Supplies   Paper Towels      True
Household cleaning Supplies   Car Airfreshner   False
Air fresheners                Car Airfreshner   True
Utensils                      Forks             True

Ayende 使用 Level 列来指示树中节点的深度，这可用于限制查询中树的深度。但 IsChild 也会演示其原理。

查找祖先

给定后代节点 Car Airfreshner，您可以在一个查询中选择所有祖先节点。您可以通过检查 IsChild 值从这些节点重建父子关系。

SELECT * FROM TreeRelations WHERE Descendant = 'Car Airfreshner'

创建树

给定祖先节点“Household Cleaning Supplies”，您可以通过在单个查询中选择所有后代来构建从此节点开始的树。 IsChild 值可用于查找父子关系。

SELECT * FROM TreeRelations WHERE Ancestor = 'Household cleaning Supplies'

两个查询组合

要获取任何给定节点的整个树，您可以组合两个查询来检索所有祖先和后代，并从中构建一棵树：

SELECT * FROM TreeRelations WHERE Descendant = 'Entry node' OR Ancestor = 'Entry node'