大多数树是由您正在处理的数据形成的。

假设您有一个person类，其中包含某人的细节 父母们，你们愿意让树形结构成为你们的一部分吗 “域类”，或者使用包含链接的单独树类 你的人反对吗?考虑一个简单的操作，比如获取全部 一个人的孙子，应该是这个人的密码 类，或者person类的用户必须知道 单独的树类?

另一个例子是编译器中的解析树…

这两个例子都表明，树的概念是数据域的一部分，使用单独的通用树至少会使创建的对象数量增加一倍，同时也会使API更难再次编程。

我们想要一种重用标准树操作的方法，而不必为所有树重新实现它们，同时又不必使用标准树类。Boost已经尝试为c++解决这类问题，但是我还没有看到任何对. net进行适应的效果。

通常优秀的C5通用集合库具有几种不同的基于树的数据结构，包括集、包和字典。如果您想研究它们的实现细节，可以使用源代码。(我在产品代码中使用过C5集合，效果很好，尽管我没有特别使用过任何树结构。)

具有通用数据的树

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

public class Tree<T>
{
    public T Data { get; set; }
    public LinkedList<Tree<T>> Children { get; set; } = new LinkedList<Tree<T>>();
    public Task Traverse(Func<T, Task> actionOnNode, int maxDegreeOfParallelism = 1) => Traverse(actionOnNode, new SemaphoreSlim(maxDegreeOfParallelism, maxDegreeOfParallelism));
    private async Task Traverse(Func<T, Task> actionOnNode, SemaphoreSlim semaphore)
    {
        await actionOnNode(Data);
        SafeRelease(semaphore);
        IEnumerable<Task> tasks = Children.Select(async input =>
        {
            await semaphore.WaitAsync().ConfigureAwait(false);
            try
            {
                await input.Traverse(actionOnNode, semaphore).ConfigureAwait(false);
            }
            finally
            {
                SafeRelease(semaphore);
            }
        });
        await Task.WhenAll(tasks);
    }
    private void SafeRelease(SemaphoreSlim semaphore)
    {
        try
        {
            semaphore.Release();
        }
        catch (Exception ex)
        {
            if (ex.Message.ToLower() != "Adding the specified count to the semaphore would cause it to exceed its maximum count.".ToLower())
            {
                throw;
            }
        }
    }

    public async Task<IEnumerable<T>> ToList()
    {
        ConcurrentBag<T> lst = new ConcurrentBag<T>();
        await Traverse(async (data) => lst.Add(data));
        return lst;
    }
    public async Task<int> Count() => (await ToList()).Count();
}

单元测试

using System.Threading.Tasks;
using Xunit;

public class Tree_Tests
{
    [Fact]
    public async Task Tree_ToList_Count()
    {
        Tree<int> head = new Tree<int>();

        Assert.NotEmpty(await head.ToList());
        Assert.True(await head.Count() == 1);

        // child
        var child = new Tree<int>();
        head.Children.AddFirst(child);
        Assert.True(await head.Count() == 2);
        Assert.NotEmpty(await head.ToList());

        // grandson
        child.Children.AddFirst(new Tree<int>());
        child.Children.AddFirst(new Tree<int>());
        Assert.True(await head.Count() == 4);
        Assert.NotEmpty(await head.ToList());
    }

    [Fact]
    public async Task Tree_Traverse()
    {
        Tree<int> head = new Tree<int>() { Data = 1 };

        // child
        var child = new Tree<int>() { Data = 2 };
        head.Children.AddFirst(child);

        // grandson
        child.Children.AddFirst(new Tree<int>() { Data = 3 });
        child.Children.AddLast(new Tree<int>() { Data = 4 });

        int counter = 0;
        await head.Traverse(async (data) => counter += data);
        Assert.True(counter == 10);

        counter = 0;
        await child.Traverse(async (data) => counter += data);
        Assert.True(counter == 9);

        counter = 0;
        await child.Children.First!.Value.Traverse(async (data) => counter += data);
        Assert.True(counter == 3);

        counter = 0;
        await child.Children.Last!.Value.Traverse(async (data) => counter += data);
        Assert.True(counter == 4);
    }
}

我已经使用上面的NTree类添加了一个完整的解决方案和示例。我还添加了AddChild方法…

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

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

        public void AddChild(T data)
        {
            var node = new NTree<T>(data) { Parent = this };
            children.AddFirst(node);
        }

        public NTree<T> Parent { get; private set; }

        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, string t, ref NTree<T> r)
        {
            visitor(node.data, node, t, ref r);
            foreach (NTree<T> kid in node.children)
                Traverse(kid, visitor, t, ref r);
        }
    }

    public static void DelegateMethod(KeyValuePair<string, string> data, NTree<KeyValuePair<string, string>> node, string t, ref NTree<KeyValuePair<string, string>> r)
    {
        string a = string.Empty;
        if (node.data.Key == t)
        {
            r = node;
            return;
        }
    }

使用它

 NTree<KeyValuePair<string, string>> ret = null;
 tree.Traverse(tree, DelegateMethod, node["categoryId"].InnerText, ref ret);

有现在发布的。net代码库:具体来说，实现红黑树的SortedSet代码:SortedSet .cs

然而，这是一个平衡的树形结构。因此，我的答案更多的是参考。net核心库中唯一的原生树结构。

我最好的建议是，没有标准的树数据结构，因为有太多的方法可以实现它，不可能用一个解决方案覆盖所有的基础。解决方案越具体，它就越不可能适用于任何给定的问题。我甚至对LinkedList感到恼火——如果我想要一个循环链表呢?

您需要实现的基本结构是一个节点集合，这里有一些选项可以帮助您入门。让我们假设类Node是整个解决方案的基类。

如果您只需要沿着树向下导航，那么Node类需要一个子类的List。

如果需要向上导航树，则Node类需要一个到其父节点的链接。

构建一个AddChild方法来处理这两点的所有细节以及必须实现的任何其他业务逻辑(子限制、子排序等)。