从集合列表创建树<T>

Question

为了创建树，我使用了以下代码。

var db = _context.GetContext();
        var accounts = await db
            .Set<TradingAccount>()
            .ToListAsync(cancellationToken: token);

        accounts.ForEach(
            account => account.Children = accounts.Where(
                child => child.ParentTradingAccountId == account.Id).ToList()
        );

        
        return accounts;

它运行良好（虽然速度不快），但它没有创建完全正确的树。同一个元素可以既是根元素又是从属元素。如何从选择中排除已包含在树中的元素？

Answer 1

问题是上面的代码将依赖节点添加为子节点，但没有将它们从 top-level 列表中删除。通常递归可以用来创建树结构，像这样：

private IEnumerable<TracingAccount> GetAccounts(IEnumerable<TradingAccount> allAccounts, int parentTrackingAccountId)
{
  var accounts = allAccounts
    .Where(x => x.ParentTrackingAccountId == parentTrackingAccountId)
    .ToList();
  foreach (var acc in accounts)
  {
    // Get children of current node
    acc.Children = GetAccounts(allAccounts, acc.Id);
  }
  return accounts;
}

以上函数检索指定父 ID 的所有帐户并再次调用自身（这就是它被称为递归函数的原因）以检索子项。

您可以在您的代码中使用该函数，如下所示（我假设根级别帐户的父 ID 为 0）：

var db = _context.GetContext();
var allAccounts = await db
  .Set<TradingAccount>()
  .ToListAsync(cancellationToken: token);
var accounts = GetAccounts(allAccounts, 0);
return accounts;

对 GetAccounts 的调用获取所有根级别帐户，并且 - 因为该函数会为每个帐户再次调用自身 - 通过它还检索根级别帐户的子树。

Answer 2

我写了一个算法来从平面列表构建树。 （比反复过滤同一个列表更快的方法） 由于项目来自数据库，因此 parentId 应该存在，并且不应出现循环引用。 这个例子无法处理这些。但它可能会给你一个jump-start如何制作更快的算法。

简而言之，循环直到添加所有项目。使用 while-loop 而不是 foreach。 foreach 的问题是您不允许在迭代时对集合进行修改。这可以通过创建副本来解决，但在许多复制操作中会 end-up。

当是child（所以parentId被填），我用查找字典查他的parent 已经添加。如果没有，我将跳过它并检查下一项。（这使得 parent 可能低于 de 列表中的 child）。当它被添加到 parent 时，也会将 child 添加到查找中，因此他们的 children 能够将它们添加为 child.

当它是一个parent时，我将它添加到rootNodes中，并将它添加到查找中。

支持多个根节点。

public static class TreeBuilder
{
    public static IEnumerable<Node> BuildTree(IEnumerable<Item> items)
    {
        var nodeLookup = new Dictionary<int, Node>();
        var rootNodes = new List<Node>();
        var itemCopy = items.ToList(); // we don't want to modify the original collection, make one working copy.
        int index = 0;

        while (true)
        {
            // when the item copy is empty, we're done.
            if (itemCopy.Count == 0)
                return rootNodes.ToArray();

            // do go out of bounds.
            index = index % itemCopy.Count;

            // get the current item on that index.
            var current = itemCopy[index];
            
            // does it have a parent?
            if(current.ParentId.HasValue)
            {
                // yes, so, it's a child
                // look if the parent is already found in the lookup.
                if (nodeLookup.TryGetValue(current.ParentId.Value, out var parentNode))
                {
                    // create a new node
                    var node = new Node { Id = current.Id };
                    // add it to the lookup
                    nodeLookup.Add(current.Id, node);
                    // add it as child node to the parent.
                    parentNode.ChildNodes.Add(node);
                    // remove it from the itemCopy (so don't check it again)
                    itemCopy.RemoveAt(index);

                    // The index doesn't need to be increase, because the current items is removed.
                }
                else
                    // next item, the parent is not in the tree yet.
                    index++;

            }
            else
            {
                // root node
                var node = new Node { Id = current.Id };
                nodeLookup.Add(current.Id, node);
                rootNodes.Add(node);
                itemCopy.RemoveAt(index);
            }
        }
    }
}

我的测试设置：

private void button4_Click(object sender, EventArgs e)
{
    /* 
        * 1
        * |
        * +- 2
        *    |
        *    +- 3
        *    |
        *    +- 5
        *       |
        *       +- 4
        */


    var items = new[]
    {
        new Item{ Id = 1, ParentId = null},
        new Item{ Id = 2, ParentId = 1},
        new Item{ Id = 3, ParentId = 2},
        new Item{ Id = 4, ParentId = 5},
        new Item{ Id = 5, ParentId = 2},
    };



    var tree = TreeBuilder.BuildTree(items);

    DisplayTree(tree);
}

private void DisplayTree(IEnumerable<Node> nodes, string indent = "")
{
    foreach (var node in nodes)
    {
        Trace.WriteLine($"{indent}{node.Id}");
        DisplayTree(node.ChildNodes, indent + "  ");
    }
}

我用的类是：

public class Node
{
    public int Id { get; set; }
    public List<Node> ChildNodes { get; } = new List<Node>();

}

public class Item
{
    public int Id { get; set; }
    public int? ParentId { get; set; }
}

这导致：

从集合列表创建树<T>

Creating a tree from a collection List<T>

c#

.net-core