我在c#中寻找树或图数据结构,但我猜没有提供。使用c# 2.0的数据结构的广泛检查。是否有一个方便的库通常用于提供这个功能?也许可以通过策略模式来解决文章中提出的问题。

我觉得实现我自己的树有点傻,就像实现我自己的数组列表一样。

我只想要一个一般的树,它可以是不平衡的。想象一个目录树。C5看起来很漂亮,但它们的树结构似乎被实现为更适合搜索的平衡红黑树,而不是表示节点的层次结构。


当前回答

下面是我实现的BST:

class BST
{
    public class Node
    {
        public Node Left { get; set; }
        public object Data { get; set; }
        public Node Right { get; set; }

        public Node()
        {
            Data = null;
        }

        public Node(int Data)
        {
            this.Data = (object)Data;
        }

        public void Insert(int Data)
        {
            if (this.Data == null)
            {
                this.Data = (object)Data;
                return;
            }
            if (Data > (int)this.Data)
            {
                if (this.Right == null)
                {
                    this.Right = new Node(Data);
                }
                else
                {
                    this.Right.Insert(Data);
                }
            }
            if (Data <= (int)this.Data)
            {
                if (this.Left == null)
                {
                    this.Left = new Node(Data);
                }
                else
                {
                    this.Left.Insert(Data);
                }
            }
        }

        public void TraverseInOrder()
        {
            if(this.Left != null)
                this.Left.TraverseInOrder();
            Console.Write("{0} ", this.Data);
            if (this.Right != null)
                this.Right.TraverseInOrder();
        }
    }

    public Node Root { get; set; }
    public BST()
    {
        Root = new Node();
    }
}

其他回答

如果你需要一个使用较少内存的根树数据结构实现,你可以这样写你的Node类(c++实现):

class Node {
       Node* parent;
       int item; // depending on your needs

       Node* firstChild; //pointer to left most child of node
       Node* nextSibling; //pointer to the sibling to the right
}

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

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

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

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

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

具有通用数据的树

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);
    }
}

下面是我实现的BST:

class BST
{
    public class Node
    {
        public Node Left { get; set; }
        public object Data { get; set; }
        public Node Right { get; set; }

        public Node()
        {
            Data = null;
        }

        public Node(int Data)
        {
            this.Data = (object)Data;
        }

        public void Insert(int Data)
        {
            if (this.Data == null)
            {
                this.Data = (object)Data;
                return;
            }
            if (Data > (int)this.Data)
            {
                if (this.Right == null)
                {
                    this.Right = new Node(Data);
                }
                else
                {
                    this.Right.Insert(Data);
                }
            }
            if (Data <= (int)this.Data)
            {
                if (this.Left == null)
                {
                    this.Left = new Node(Data);
                }
                else
                {
                    this.Left.Insert(Data);
                }
            }
        }

        public void TraverseInOrder()
        {
            if(this.Left != null)
                this.Left.TraverseInOrder();
            Console.Write("{0} ", this.Data);
            if (this.Right != null)
                this.Right.TraverseInOrder();
        }
    }

    public Node Root { get; set; }
    public BST()
    {
        Root = new Node();
    }
}

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

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