sti*_*mms 238 c# data-structures
我在C#中寻找树或图形数据结构,但我想没有提供.对数据结构的广泛检查使用C#2.0解释了一些原因.是否有一个方便的库,通常用于提供此功能？也许通过策略模式来解决文章中提出的问题.
我觉得实现自己的树有点傻,就像我实现自己的ArrayList一样.
我只想要一个可以不平衡的通用树.想一下目录树.C5看起来很漂亮,但它们的树结构似乎被实现为更适合搜索的平衡红黑树而不是表示节点的层次结构.
Dav*_*ike 146
我最好的建议是没有标准的树数据结构,因为有很多方法可以实现它,用一个解决方案覆盖所有基础是不可能的.解决方案越具体,它就越不可能适用于任何给定的问题.我甚至对LinkedList感到恼火 - 如果我想要一个循环链表怎么办？
您需要实现的基本结构将是一组节点,这里有一些选项可以帮助您入门.我们假设类Node是整个解决方案的基类.
如果只需要向下导航树,那么Node类需要一个子列表.
如果需要向上导航树,则Node类需要指向其父节点的链接.
构建一个AddChild方法,负责处理这两点的所有细节以及必须实现的任何其他业务逻辑(子限制,对子项进行排序等)
Aar*_*age 116
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？
Ron*_*rby 53
在我看来,这是我的,与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()));
}
}
}
Grz*_*Dev 46
另一种树形结构:
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");
}
}
奖金
见完全成熟的树:
https://github.com/gt4dev/yet-another-tree-structure
nie*_*ras 10
见http://quickgraph.codeplex.com/
QuickGraph为.Net 2.0及更高版本提供通用的定向/无向图形数据结构和算法.QuickGraph带有深度优先搜索,呼吸优先搜索,A*搜索,最短路径,k最短路径,最大流量,最小生成树,最少共同祖先等算法... QuickGraph支持MSAGL,GLEE和Graphviz渲染图形,序列化为GraphML等...
这是我自己的：
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
如果您想自己编写,可以从这个由六部分组成的文档开始,详细介绍C#2.0数据结构的有效使用以及如何分析C#中数据结构的实现.每篇文章都有示例和安装程序,其中包含您可以使用的示例.
Scott Mitchell撰写的"使用C#2.0对数据结构进行了广泛的检查"
我对解决方案有一点延伸.
使用递归泛型声明和派生子类,您可以更好地专注于您的实际目标.
请注意,它与非泛型实现不同,您不需要在'NodeWorker'中强制转换'node'.
这是我的例子:
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);
}
我创建了一个对其他人有帮助的Node<T> 类。该类具有如下属性：
还可以将带有 Id 和 ParentId 的项目的平面列表转换为树。节点保存对子节点和父节点的引用，因此使得迭代节点变得相当快。
| 归档时间： |
|
| 查看次数： |
354403 次 |
| 最近记录： |