從集合List<T>創建樹

為了創建一棵樹，我使用以下代碼。

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;

它運行良好（盡管速度不快），但它并不能創建完全正確的樹。同一個元素既可以是根元素，也可以是從屬元素。如何從選擇中排除已包含在樹中的元素？

uj5u.com熱心網友回復：

問題是上面的代碼將依賴節點添加為子節點，但沒有將它們從頂級串列中洗掉。通常遞回可用于創建樹結構，如下所示：

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 的呼叫獲取所有根級別帳戶，并且 - 因為該函式再次為每個帳戶呼叫自身 - 通過它還檢索根級別帳戶的子樹。

uj5u.com熱心網友回復：

我寫了一個演算法來從一個平面串列中構建一棵樹。由于專案來自資料庫，因此 parentId 應該存在，并且不應發生回圈參考。此示例無法處理這些。 但它可能會讓您快速開始如何制定更快的演算法。

簡而言之，回圈直到添加所有專案。使用 while 回圈而不是 foreach。foreach 的問題是不允許在迭代時對集合進行修改。這可以通過創建副本來解決，但最終會出現在許多復制操作中。

當它是一個孩子（所以 parentId 被填充）時，我使用查找字典來檢查他的父母是否已經被添加。如果沒有，我會跳過它并檢查下一項。（這使得父母可能在 de 串列中的孩子之下）。當它被添加到父級時，也將子級添加到查找中，因此他們的子級能夠將它們添加為子級。

當它是父節點時，我將其添加到 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; }
}

結果是：

1
  2
    3
    5
      4

標籤：C＃ .net-core

上一篇：c#.Last的替代品

下一篇：將列舉轉換為json物件