我在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();
}
}
其他回答
见https://github.com/YaccConstructor/QuickGraph(原http://quickgraph.codeplex.com/)
QuickGraph为。net 2.0及更高版本提供了通用的有向/无向图数据结构和算法。QuickGraph提供了深度优先搜索、宽度优先搜索、A*搜索、最短路径、k-最短路径、最大流量、最小生成树、最小公共祖先等算法……QuickGraph支持MSAGL, GLEE和Graphviz来呈现图形，序列化到GraphML等。
如果要在GUI上显示这个树，可以使用TreeView和TreeNode。(我认为从技术上讲，你可以创建一个TreeNode而不把它放在GUI上，但它确实比一个简单的自定义TreeNode实现有更多的开销。)
delegate void TreeVisitor<T>(T nodeData);
class NTree<T>
{
private T data;
private LinkedList<NTree<T>> children;
public NTree(T data)
{
this.data = data;
children = new LinkedList<NTree<T>>();
}
public void AddChild(T data)
{
children.AddFirst(new NTree<T>(data));
}
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)
{
visitor(node.data);
foreach (NTree<T> kid in node.children)
Traverse(kid, visitor);
}
}
简单的递归实现… < 40行代码… 你只需要在类外保留一个对树根的引用， 或者在另一个类中包装它，也许重命名为TreeNode??
还有另一种树结构:
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;
}
... // for iterator details see below link
}
示例用法:
TreeNode<string> root = new TreeNode<string>("root");
{
TreeNode<string> node0 = root.AddChild("node0");
TreeNode<string> node1 = root.AddChild("node1");
TreeNode<string> node2 = root.AddChild("node2");
{
TreeNode<string> node20 = node2.AddChild(null);
TreeNode<string> node21 = node2.AddChild("node21");
{
TreeNode<string> node210 = node21.AddChild("node210");
TreeNode<string> node211 = node21.AddChild("node211");
}
}
TreeNode<string> node3 = root.AddChild("node3");
{
TreeNode<string> node30 = node3.AddChild("node30");
}
}
奖金 见羽翼丰满的树与:
迭代器 搜索 Java / c#
https://github.com/gt4dev/yet-another-tree-structure
具有通用数据的树
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);
}
}
