我在c#中寻找树或图数据结构,但我猜没有提供。使用c# 2.0的数据结构的广泛检查。是否有一个方便的库通常用于提供这个功能?也许可以通过策略模式来解决文章中提出的问题。
我觉得实现我自己的树有点傻,就像实现我自己的数组列表一样。
我只想要一个一般的树,它可以是不平衡的。想象一个目录树。C5看起来很漂亮,但它们的树结构似乎被实现为更适合搜索的平衡红黑树,而不是表示节点的层次结构。
我在c#中寻找树或图数据结构,但我猜没有提供。使用c# 2.0的数据结构的广泛检查。是否有一个方便的库通常用于提供这个功能?也许可以通过策略模式来解决文章中提出的问题。
我觉得实现我自己的树有点傻,就像实现我自己的数组列表一样。
我只想要一个一般的树,它可以是不平衡的。想象一个目录树。C5看起来很漂亮,但它们的树结构似乎被实现为更适合搜索的平衡红黑树,而不是表示节点的层次结构。
当前回答
这是我的,和艾伦·盖奇的很相似,只是在我看来更传统一点。就我而言,我使用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()));
}
}
}
其他回答
我创建了一个Node<T>类,它可能对其他人有帮助。该类具有如下属性:
孩子们 的祖先 的后代 兄弟姐妹 节点级别 父 根 等。
还有一种可能是将一个带有Id和ParentId的项目平面列表转换为树。节点包含对子节点和父节点的引用,因此迭代节点非常快。
通常优秀的C5通用集合库具有几种不同的基于树的数据结构,包括集、包和字典。如果您想研究它们的实现细节,可以使用源代码。(我在产品代码中使用过C5集合,效果很好,尽管我没有特别使用过任何树结构。)
我不喜欢树的方法。它使事情变得过于复杂,包括搜索或下钻,甚至ui控件填充。
我建议使用dictionary <TChild, TParent>这种非常简单的方法。这也允许节点或级别之间没有连接。
试试这个简单的例子。
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
}
还有另一种树结构:
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