65.9K
CodeProject 正在变化。 阅读更多。
Home

在 .NET 中构建列表树

Daniel Flower
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.61/5 (18投票s)

2008 年 2 月 27 日

CPOL

5分钟阅读

viewsIcon

168733

downloadIcon

4382

一个简化从数据库行或对象列表创建树的接口

本文档面向哪些读者？

本文档面向需要通过加载数据库中的行数组或列表来构建对象树（或森林），并将它们转换为内存中的树结构以供使用或显示的 .NET 开发人员。

引言

在数据库中存储分层数据是一个非常普遍的需求，无论是产品类别、体育赛事还是员工层级。多年来，我曾多次创建、存储在数据库以及显示树，我的方法已经从固定大小的层级结构，到提供树功能的抽象类，再到本文所述的方法。本文介绍了一种非常简单的方法，用于从表中加载数据，并将其转换为 .NET 2.0+ 的 C# 代码中的树。

虽然关于此主题已有其他文章，但以下目标并不总是能实现：

  • 您不应需要扩展一个 abstract 类，因为您的数据类可能已经扩展了另一个类。
  • 您不应需要将您的类转换为部分类。
  • 您不应需要更改您的数据库表：只要它使用了标准的父 ID 列引用其自身的主键，就应该可以正常工作。
  • 不应需要对父对象或子对象进行任何类型转换。
  • 它应该易于使用。

答案是定义一个接口 - 在此例中称为 ITreeNode - 然后有一个实用方法来从该接口构建树。本文档假定您已经定义了一个类来保存单个节点（例如，一个 Category 对象），并且当您从数据库获取节点列表时，每个对父对象的引用都已实例化为一个对象，其 ID 已设置，但没有对完全填充的父对象或其子对象的引用。

一个示例

让我们来看一下用于对产品进行分类的非常常见的“Category”实体。数据库表如下所示：

Table definition of a Category

假设数据库中只有 8 行，它们将产品分为两个主要类别 -“硬件”和“软件” - 然后进一步细分。在这种情况下，“操作系统”和“开发工具”属于“软件”；“显示器”和“外围设备”属于“硬件”，最后“键盘”和“鼠标”属于“外围设备”，从而形成以下类别层级结构：

Example category hierarchy

数据库中的行如下：

Category table rows

为了在网站上显示此信息，您需要创建一个“Category”类：

public class Category
{
    private int _id;
    private string _name;
    private Category _parent;
    private List<Category> _children;
    
    public int Id
    {
        get { return _id; }
        set { _id = value; }
    }

    public string Name
    {
        get { return _name; }
        set { _name = value; }
    }

    public Category Parent
    {
        get { return _parent; }
        set { _parent = value; }
    }

    public List<Category> Children
    {
        get { return _children; }
        set { _children = value; }
    }
}

还需要一个方法来从数据库检索所有类别。这将是每个类别的“扁平”列表，即 _parent 字段将指向一个仅填充了 ID 的对象，而 _children 将为 null。下面是一个可能的方法示例：

static List<Category> GetListFromDatabase(DbConnection con) {
    DbCommand cmd = con.CreateCommand();
    cmd.CommandText = "SELECT Id, Name, ParentID FROM Category";
    cmd.CommandType = CommandType.Text;
    DbDataReader reader = cmd.ExecuteReader();
    List<Category> categories = new List<Category>(); 
    foreach (DbDataRecord row in reader) {
        Category c = new Category();
        c.Id = (int)row["Id"];
        c.Name = (string)row["Name"];
        if (row["ParentID"] != DBNull.Value)
        {
            c.Parent = new Category();
            c.Parent.Id = (int)row["ParentID"];
        }
        categories.Add(c);
    }
    reader.Close();
    return categories;
}

一旦有了内存中的对象列表，ITreeNode 接口就派上用场了。第一步是实现该接口：

public class Category : ITreeNode<Category> {
// contents of class remain as above, because the 
// interface is implemented by the Id, Parent, and 
// Children properties
}

该接口要求我们有一个属性指向类别的父级（其中 null 表示根级节点），以及一个指向子级的 IList 。

现在我们可以调用 TreeHelper 实用方法，将 GetListFromDatabase 返回的扁平数组转换为完全填充的层级结构：

IList<Category> topLevelCategories = 
    TreeHelper.ConvertToForest(GetListFromDatabase());

变量 topLevelCategories 包含两个类别：“软件”和“硬件”。

使用嵌套的 HTML <ul> 和 <li> 标签打印所有节点

使用递归方法，您可以轻松地打印出完整的类别层级结构，例如，使用嵌套的 <ul> 标签，如下所示：

void Page_Load(object sender, EventArgs e) {
    IList<Category> topLevelCategories = 
        TreeHelper.ConvertToForest(Category.GetListFromDatabase());
    Response.Write("<ul>");
    foreach(Category topLevelCategory in topLevelCategories) {
        RenderCategory(topLevelCategory);
    }
    Response.Write("</ul>");
}

void RenderCategory(Category category) {
    Response.Write("<li>" + category.Name);
    if (category.Children.Count > 0) {
        Response.Write("<ul>");
        foreach(Category child in category.Children) {
            RenderCategory(child);
        }
        Response.Write("</ul>");
    }
    Response.Write("</li>");
}

这将渲染以下输出：

  • 软件
    • 操作系统
    • 开发人员工具
  • 硬件
    • 监视器
    • 外围设备
      • 键盘
      • 鼠标

在树中搜索单个类别

// in a website, this may use the ASP.NET Cache object.
List<Category> categories = GetCategories();
int categoryId = int.Parse(Request.Params["categoryId"]); 
Category currentCategory = 
    TreeHelper.FindTreeNode(categories, categoryId);

打印面包屑

继续上面的示例，这里是如何打印当前类别的面包屑：

Category currentCategory = GetCategory();
foreach(Category category in 
    TreeHelper.Iterators.FromRootToNode(currentCategory))
{
    Response.Write(" / " + category.Name);
}

如果当前类别是“键盘”，这将渲染以下 HTML：

/ Hardware / Peripherals / Keyboards

树助手

TreeHelper 实用类包含许多其他有用的方法 - 例如 GetDepth 和 HasHierarchyLoop - 以及迭代器 - 例如 DepthFirstTraversal、BreadthFirstTraversal、ClimbToRoot、FromRootToNode 和 Siblings。

请查看完全文档化的源代码以获取详细信息。

使用扩展方法和“LINQ to Trees”

如果您使用的是 .NET 3.5 解决方案，您可以利用扩展方法。这会产生在接口声明中实现方法的效果（这在旧版本的 C# 中是不可能的），这可能是扩展方法最实用的方面，事实上这也是它们被发明的原因。

使用扩展方法的示例

List<Category> categories = GetCategories().ConvertToForest();
Category current = categories.FindCategory(3);
foreach(Category descendent in current.DepthFirstTraversal()) {
    Response.Write("Depth of " + descendent.Name + ": " + descendent.GetDepth();
}

请记住，ConvertToForest、FindCategory、DepthFirstTraversal 和 GetDepth 不是由 Category 类实现的，它仅仅通过实现 ITreeNode<T> 来“继承”这些方法，就像从 TreeHelper 类继承一样。

扩展方法与 LINQ 相辅相成。是的，严格来说，这只是“LINQ to Objects”，而不是“LINQ to trees”，但无论如何，这是一种查询树的新方法。

List<Category> categoryList = Category.GetCategories();

// Get all categories which are not top level categories, 
// and retrieve only the name.
var nonRootCategories = 
    from c in categoryList.DepthFirstTraversalOfList()
    where c.Parent != null
    select new { Name = c.Name };

// Get all categories at Depth 2, ordered by name, and
// get the whole category object.
var level2Categories = 
    from c in categoryList.DepthFirstTraversalOfList()
    where c.GetDepth() == 2
    orderby c.Name ascending
    select c;

一些很酷的功能

以下 .NET 语言功能使得这个类更加有用：

  • 使用泛型参数的接口。请注意，接口定义是 ITreeNode<T>，而对父级的引用，例如，是 T Parent。这意味着您永远不需要从 ITreeNode 转换为您的类。
  • 使用“yield”关键字创建迭代器。这可能是 .NET 2.0 中引入的最被低估的功能之一，它使得创建迭代器变得非常容易。请查看 TreeHelper<T>.Iterators 类中的方法。
  • 扩展方法和 LINQ。使用 LINQ 查询树 certainly 可以使某些任务变得更容易……也更有趣。

历史

  • 2008 年 2 月 27 日：首次发布
  • 2008 年 3 月 2 日：将 TreeHelper 从泛型类更改为非泛型类，并具有泛型方法（允许 类型方法推断），并添加了关于 LINQ 的部分。
© . All rights reserved.