我在c#中寻找树或图数据结构,但我猜没有提供。使用c# 2.0的数据结构的广泛检查。是否有一个方便的库通常用于提供这个功能?也许可以通过策略模式来解决文章中提出的问题。
我觉得实现我自己的树有点傻,就像实现我自己的数组列表一样。
我只想要一个一般的树,它可以是不平衡的。想象一个目录树。C5看起来很漂亮,但它们的树结构似乎被实现为更适合搜索的平衡红黑树,而不是表示节点的层次结构。
我在c#中寻找树或图数据结构,但我猜没有提供。使用c# 2.0的数据结构的广泛检查。是否有一个方便的库通常用于提供这个功能?也许可以通过策略模式来解决文章中提出的问题。
我觉得实现我自己的树有点傻,就像实现我自己的数组列表一样。
我只想要一个一般的树,它可以是不平衡的。想象一个目录树。C5看起来很漂亮,但它们的树结构似乎被实现为更适合搜索的平衡红黑树,而不是表示节点的层次结构。
当前回答
也有可能在LINQ中使用XML:
在c#中创建XML树(LINQ to XML)
在使用树时,XML是最成熟和最灵活的解决方案,而LINQ为您提供了所需的所有工具。 您的树的配置也变得更加清晰和用户友好,因为您可以简单地使用XML文件进行初始化。
如果你需要处理对象,你可以使用XML序列化:
XML序列化
其他回答
试试这个简单的例子。
public class TreeNode<TValue>
{
#region Properties
public TValue Value { get; set; }
public List<TreeNode<TValue>> Children { get; private set; }
public bool HasChild { get { return Children.Any(); } }
#endregion
#region Constructor
public TreeNode()
{
this.Children = new List<TreeNode<TValue>>();
}
public TreeNode(TValue value)
: this()
{
this.Value = value;
}
#endregion
#region Methods
public void AddChild(TreeNode<TValue> treeNode)
{
Children.Add(treeNode);
}
public void AddChild(TValue value)
{
var treeNode = new TreeNode<TValue>(value);
AddChild(treeNode);
}
#endregion
}
具有通用数据的树
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);
}
}
我已经完成了Berezh分享的代码。
public class TreeNode<T> : IEnumerable<TreeNode<T>>
{
public T Data { get; set; }
public TreeNode<T> Parent { get; set; }
public ICollection<TreeNode<T>> Children { get; set; }
public TreeNode(T data)
{
this.Data = data;
this.Children = new LinkedList<TreeNode<T>>();
}
public TreeNode<T> AddChild(T child)
{
TreeNode<T> childNode = new TreeNode<T>(child) { Parent = this };
this.Children.Add(childNode);
return childNode;
}
public IEnumerator<TreeNode<T>> GetEnumerator()
{
throw new NotImplementedException();
}
IEnumerator IEnumerable.GetEnumerator()
{
return (IEnumerator)GetEnumerator();
}
}
public class TreeNodeEnum<T> : IEnumerator<TreeNode<T>>
{
int position = -1;
public List<TreeNode<T>> Nodes { get; set; }
public TreeNode<T> Current
{
get
{
try
{
return Nodes[position];
}
catch (IndexOutOfRangeException)
{
throw new InvalidOperationException();
}
}
}
object IEnumerator.Current
{
get
{
return Current;
}
}
public TreeNodeEnum(List<TreeNode<T>> nodes)
{
Nodes = nodes;
}
public void Dispose()
{
}
public bool MoveNext()
{
position++;
return (position < Nodes.Count);
}
public void Reset()
{
position = -1;
}
}
我对解做了一些扩展。
使用递归泛型声明和派生子类,可以更好地专注于实际目标。
注意,它不同于非泛型实现,你不需要将'node'转换为'NodeWorker'。
以下是我的例子:
public class GenericTree<T> where T : GenericTree<T> // recursive constraint
{
// no specific data declaration
protected List<T> children;
public GenericTree()
{
this.children = new List<T>();
}
public virtual void AddChild(T newChild)
{
this.children.Add(newChild);
}
public void Traverse(Action<int, T> visitor)
{
this.traverse(0, visitor);
}
protected virtual void traverse(int depth, Action<int, T> visitor)
{
visitor(depth, (T)this);
foreach (T child in this.children)
child.traverse(depth + 1, visitor);
}
}
public class GenericTreeNext : GenericTree<GenericTreeNext> // concrete derivation
{
public string Name {get; set;} // user-data example
public GenericTreeNext(string name)
{
this.Name = name;
}
}
static void Main(string[] args)
{
GenericTreeNext tree = new GenericTreeNext("Main-Harry");
tree.AddChild(new GenericTreeNext("Main-Sub-Willy"));
GenericTreeNext inter = new GenericTreeNext("Main-Inter-Willy");
inter.AddChild(new GenericTreeNext("Inter-Sub-Tom"));
inter.AddChild(new GenericTreeNext("Inter-Sub-Magda"));
tree.AddChild(inter);
tree.AddChild(new GenericTreeNext("Main-Sub-Chantal"));
tree.Traverse(NodeWorker);
}
static void NodeWorker(int depth, GenericTreeNext node)
{ // a little one-line string-concatenation (n-times)
Console.WriteLine("{0}{1}: {2}", String.Join(" ", new string[depth + 1]), depth, node.Name);
}
我已经使用上面的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);