我在c#中寻找树或图数据结构，但我猜没有提供。使用c# 2.0的数据结构的广泛检查。是否有一个方便的库通常用于提供这个功能?也许可以通过策略模式来解决文章中提出的问题。
我觉得实现我自己的树有点傻，就像实现我自己的数组列表一样。
我只想要一个一般的树，它可以是不平衡的。想象一个目录树。C5看起来很漂亮，但它们的树结构似乎被实现为更适合搜索的平衡红黑树，而不是表示节点的层次结构。
当前回答
我已经完成了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;
}
}
其他回答
如果你需要一个使用较少内存的根树数据结构实现，你可以这样写你的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
}
我已经完成了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;
}
}
大多数树是由您正在处理的数据形成的。
假设您有一个person类，其中包含某人的细节 父母们，你们愿意让树形结构成为你们的一部分吗 “域类”，或者使用包含链接的单独树类 你的人反对吗?考虑一个简单的操作，比如获取全部 一个人的孙子，应该是这个人的密码 类，或者person类的用户必须知道 单独的树类?
另一个例子是编译器中的解析树…
这两个例子都表明，树的概念是数据域的一部分，使用单独的通用树至少会使创建的对象数量增加一倍，同时也会使API更难再次编程。
我们想要一种重用标准树操作的方法，而不必为所有树重新实现它们，同时又不必使用标准树类。Boost已经尝试为c++解决这类问题，但是我还没有看到任何对. net进行适应的效果。
这是我自己的想法:
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
这是我的，和艾伦·盖奇的很相似，只是在我看来更传统一点。就我而言，我使用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()));
}
}
}
推荐文章
- 实体框架核心:在上一个操作完成之前，在此上下文中开始的第二个操作
- 如何为构造函数定制Visual Studio的私有字段生成快捷方式?
- 如何使用JSON确保字符串是有效的JSON。网
- AppSettings从.config文件中获取值
- 通过HttpClient向REST API发布一个空体
- 如何检查IEnumerable是否为空或空?
- 自动化invokerrequired代码模式
- 在c#代码中设置WPF文本框的背景颜色
- 在c#中，什么是单子?
- c#和Java中的泛型有什么不同?和模板在c++ ?
- c#线程安全快速(est)计数器
- HyperLogLog算法是如何工作的?
- 如何将此foreach代码转换为Parallel.ForEach?
- 如何分裂()一个分隔字符串到一个列表<字符串>
- 如何转换列表<字符串>列表<int>?
