我在c#中寻找树或图数据结构,但我猜没有提供。使用c# 2.0的数据结构的广泛检查。是否有一个方便的库通常用于提供这个功能?也许可以通过策略模式来解决文章中提出的问题。
我觉得实现我自己的树有点傻,就像实现我自己的数组列表一样。
我只想要一个一般的树,它可以是不平衡的。想象一个目录树。C5看起来很漂亮,但它们的树结构似乎被实现为更适合搜索的平衡红黑树,而不是表示节点的层次结构。
我在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();
}
}
其他回答
大多数树是由您正在处理的数据形成的。
假设您有一个person类,其中包含某人的细节 父母们,你们愿意让树形结构成为你们的一部分吗 “域类”,或者使用包含链接的单独树类 你的人反对吗?考虑一个简单的操作,比如获取全部 一个人的孙子,应该是这个人的密码 类,或者person类的用户必须知道 单独的树类?
另一个例子是编译器中的解析树…
这两个例子都表明,树的概念是数据域的一部分,使用单独的通用树至少会使创建的对象数量增加一倍,同时也会使API更难再次编程。
我们想要一种重用标准树操作的方法,而不必为所有树重新实现它们,同时又不必使用标准树类。Boost已经尝试为c++解决这类问题,但是我还没有看到任何对. net进行适应的效果。
我创建了一个Node<T>类,它可能对其他人有帮助。该类具有如下属性:
孩子们 的祖先 的后代 兄弟姐妹 节点级别 父 根 等。
还有一种可能是将一个带有Id和ParentId的项目平面列表转换为树。节点包含对子节点和父节点的引用,因此迭代节点非常快。
还有另一种树结构:
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
如果你需要一个使用较少内存的根树数据结构实现,你可以这样写你的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
}
这是我的,和艾伦·盖奇的很相似,只是在我看来更传统一点。就我而言,我使用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()));
}
}
}