我在c#中寻找树或图数据结构,但我猜没有提供。使用c# 2.0的数据结构的广泛检查。是否有一个方便的库通常用于提供这个功能?也许可以通过策略模式来解决文章中提出的问题。
我觉得实现我自己的树有点傻,就像实现我自己的数组列表一样。
我只想要一个一般的树,它可以是不平衡的。想象一个目录树。C5看起来很漂亮,但它们的树结构似乎被实现为更适合搜索的平衡红黑树,而不是表示节点的层次结构。
我在c#中寻找树或图数据结构,但我猜没有提供。使用c# 2.0的数据结构的广泛检查。是否有一个方便的库通常用于提供这个功能?也许可以通过策略模式来解决文章中提出的问题。
我觉得实现我自己的树有点傻,就像实现我自己的数组列表一样。
我只想要一个一般的树,它可以是不平衡的。想象一个目录树。C5看起来很漂亮,但它们的树结构似乎被实现为更适合搜索的平衡红黑树,而不是表示节点的层次结构。
当前回答
我最好的建议是,没有标准的树数据结构,因为有太多的方法可以实现它,不可能用一个解决方案覆盖所有的基础。解决方案越具体,它就越不可能适用于任何给定的问题。我甚至对LinkedList感到恼火——如果我想要一个循环链表呢?
您需要实现的基本结构是一个节点集合,这里有一些选项可以帮助您入门。让我们假设类Node是整个解决方案的基类。
如果您只需要沿着树向下导航,那么Node类需要一个子类的List。
如果需要向上导航树,则Node类需要一个到其父节点的链接。
构建一个AddChild方法来处理这两点的所有细节以及必须实现的任何其他业务逻辑(子限制、子排序等)。
其他回答
通常优秀的C5通用集合库具有几种不同的基于树的数据结构,包括集、包和字典。如果您想研究它们的实现细节,可以使用源代码。(我在产品代码中使用过C5集合,效果很好,尽管我没有特别使用过任何树结构。)
有现在发布的。net代码库:具体来说,实现红黑树的SortedSet代码:SortedSet .cs
然而,这是一个平衡的树形结构。因此,我的答案更多的是参考。net核心库中唯一的原生树结构。
我最好的建议是,没有标准的树数据结构,因为有太多的方法可以实现它,不可能用一个解决方案覆盖所有的基础。解决方案越具体,它就越不可能适用于任何给定的问题。我甚至对LinkedList感到恼火——如果我想要一个循环链表呢?
您需要实现的基本结构是一个节点集合,这里有一些选项可以帮助您入门。让我们假设类Node是整个解决方案的基类。
如果您只需要沿着树向下导航,那么Node类需要一个子类的List。
如果需要向上导航树,则Node类需要一个到其父节点的链接。
构建一个AddChild方法来处理这两点的所有细节以及必须实现的任何其他业务逻辑(子限制、子排序等)。
试试这个简单的例子。
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
}
这是我自己的想法:
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