我一直在寻找 C# 中的树或图形数据结构，但我想没有提供。使用 C# 2.0 对数据结构进行广泛检查，了解原因。是否有一个方便的库通常用于提供此功能？或许可以通过一种策略模式来解决文章中提出的问题。
我觉得实现自己的树有点傻，就像我实现自己的 ArrayList 一样。
我只想要一个可以不平衡的通用树。想想目录树。 C5看起来很漂亮，但它们的树结构似乎被实现为平衡的红黑树，比表示节点层次结构更适合搜索。
stimms
问问题
439918 次
19 回答
174
我最好的建议是没有标准的树数据结构，因为有很多方法可以实现它，不可能用一种解决方案覆盖所有基础。解决方案越具体，它就越不可能适用于任何给定的问题。我什至对 LinkedList 感到恼火——如果我想要一个循环链表怎么办？
您需要实现的基本结构将是节点的集合，这里有一些选项可以帮助您入门。让我们假设类 Node 是整个解决方案的基类。
如果您只需要向下导航树，那么 Node 类需要一个子列表。
如果您需要向上导航树，那么 Node 类需要一个指向其父节点的链接。
构建一个 AddChild 方法来处理这两点的所有细节以及必须实现的任何其他业务逻辑（子限制、对子排序等）
于 2008-09-15T21:04:39.600 回答
130
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？
于 2010-01-06T12:29:12.200 回答
68
在我看来，这是我的，与Aaron Gage 的非常相似，只是更传统一点。就我的目的而言，我没有遇到任何性能问题List<T>。如果需要，切换到 LinkedList 很容易。
namespace Overby.Collections
{
public class TreeNode<T>
{
private readonly T _value;
private readonly List<TreeNode<T>> _children = new List<TreeNode<T>>();
public TreeNode(T value)
{
_value = value;
}
public TreeNode<T> this[int i]
{
get { return _children[i]; }
}
public TreeNode<T> Parent { get; private set; }
public T Value { get { return _value; } }
public ReadOnlyCollection<TreeNode<T>> Children
{
get { return _children.AsReadOnly(); }
}
public TreeNode<T> AddChild(T value)
{
var node = new TreeNode<T>(value) {Parent = this};
_children.Add(node);
return node;
}
public TreeNode<T>[] AddChildren(params T[] values)
{
return values.Select(AddChild).ToArray();
}
public bool RemoveChild(TreeNode<T> node)
{
return _children.Remove(node);
}
public void Traverse(Action<T> action)
{
action(Value);
foreach (var child in _children)
child.Traverse(action);
}
public IEnumerable<T> Flatten()
{
return new[] {Value}.Concat(_children.SelectMany(x => x.Flatten()));
}
}
}
于 2012-05-04T03:18:33.587 回答
52
另一个树结构：
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#
于 2013-09-12T20:58:44.383 回答
24
一般优秀的C5 Generic Collection Library有几种不同的基于树的数据结构，包括集合、包和字典。如果您想研究它们的实现细节，可以使用源代码。（我在生产代码中使用了 C5 集合并取得了很好的效果，尽管我没有专门使用任何树结构。）
于 2008-09-15T21:01:58.717 回答
11
见https://github.com/YaccConstructor/QuickGraph（以前是 http://quickgraph.codeplex.com/）
QuickGraph 为 .NET 2.0 及更高版本提供通用的有向/无向图数据结构和算法。QuickGraph 自带深度优先搜索、广度优先搜索、A* 搜索、最短路径、k-最短路径、最大流量、最小生成树、最小共同祖先等算法... QuickGraph 支持MSAGL、GLEE和Graphviz渲染图形，序列化到GraphML等。
于 2010-01-25T15:34:10.020 回答
10
这是我自己的：
class Program
{
static void Main(string[] args)
{
var tree = new Tree<string>()
.Begin("Fastfood")
.Begin("Pizza")
.Add("Margherita")
.Add("Marinara")
.End()
.Begin("Burger")
.Add("Cheese burger")
.Add("Chili burger")
.Add("Rice burger")
.End()
.End();
tree.Nodes.ForEach(p => PrintNode(p, 0));
Console.ReadKey();
}
static void PrintNode<T>(TreeNode<T> node, int level)
{
Console.WriteLine("{0}{1}", new string(' ', level * 3), node.Value);
level++;
node.Children.ForEach(p => PrintNode(p, level));
}
}
public class Tree<T>
{
private Stack<TreeNode<T>> m_Stack = new Stack<TreeNode<T>>();
public List<TreeNode<T>> Nodes { get; } = new List<TreeNode<T>>();
public Tree<T> Begin(T val)
{
if (m_Stack.Count == 0)
{
var node = new TreeNode<T>(val, null);
Nodes.Add(node);
m_Stack.Push(node);
}
else
{
var node = m_Stack.Peek().Add(val);
m_Stack.Push(node);
}
return this;
}
public Tree<T> Add(T val)
{
m_Stack.Peek().Add(val);
return this;
}
public Tree<T> End()
{
m_Stack.Pop();
return this;
}
}
public class TreeNode<T>
{
public T Value { get; }
public TreeNode<T> Parent { get; }
public List<TreeNode<T>> Children { get; }
public TreeNode(T val, TreeNode<T> parent)
{
Value = val;
Parent = parent;
Children = new List<TreeNode<T>>();
}
public TreeNode<T> Add(T val)
{
var node = new TreeNode<T>(val, this);
Children.Add(node);
return node;
}
}
输出：
Fastfood
Pizza
Margherita
Marinara
Burger
Cheese burger
Chili burger
Rice burger
于 2018-08-25T06:46:08.670 回答
9
我对解决方案有一点扩展。
使用递归泛型声明和派生子类，您可以更好地专注于您的实际目标。
请注意，它与非通用实现不同，您不需要将“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);
}
于 2012-11-17T12:24:16.730 回答
4
试试这个简单的示例。
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
}
于 2013-02-27T00:10:53.200 回答
3
我创建了一个可能对其他人有帮助的Node<T> 类。该类具有以下属性：
- 孩子们
- 祖先
- 后人
- 兄弟姐妹
- 节点级别
- 家长
- 根
- 等等。
还可以将具有 Id 和 ParentId 的项目的平面列表转换为树。节点包含对子节点和父节点的引用，因此迭代节点非常快。
于 2013-08-01T13:21:53.967 回答
2
有现在发布的 .NET 代码库：特别是SortedSet实现红黑树的代码：sortedset.cs
然而，这是一个平衡的树结构。所以我的回答更多地是对我认为是 .NET 核心库中唯一的本机树结构的参考。
于 2016-01-27T09:51:56.197 回答
2
我已经完成了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;
}
}
于 2016-07-24T18:46:50.913 回答
1
大多数树是由您正在处理的数据形成的。
假设您有一个
person包含某人详细信息的类，parents您希望将树结构作为“域类”的一部分，还是使用包含指向您的人员对象的链接的单独树类？考虑一个简单的操作，比如获取所有grandchildrenaperson，这段代码应该在person类中，还是类的用户person必须知道一个单独的树类？
另一个例子是编译器中 的解析树……</p>
这两个示例都表明，树的概念是数据域的一部分，使用单独的通用树至少会使创建的对象数量增加一倍，并使 API 更难再次编程。
我们想要一种重用标准树操作的方法，而不必为所有树重新实现它们，同时不必使用标准树类。Boost已尝试为 C++ 解决此类问题，但我还没有看到 .NET 对其进行调整的任何效果。
于 2016-04-11T11:00:14.833 回答
1
我使用上面的 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);
于 2017-04-13T05:09:47.147 回答
1
也可以将 XML 与LINQ一起使用：
在使用树时，XML 是最成熟、最灵活的解决方案，而 LINQ 为您提供了所需的所有工具。树的配置也变得更加简洁和用户友好，因为您可以简单地使用 XML 文件进行初始化。
如果需要处理对象，可以使用 XML 序列化：
于 2020-10-28T17:14:29.757 回答
0
这是我的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();
}
}
于 2014-04-18T08:05:43.543 回答
-1
具有通用数据的树
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);
}
}
于 2020-11-22T22:28:52.163 回答
-3
如果您需要使用较少内存的有根树数据结构实现，您可以按如下方式编写 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
}
于 2012-05-15T03:18:30.290 回答