我在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的项目平面列表转换为树。节点包含对子节点和父节点的引用,因此迭代节点非常快。

如果要在GUI上显示这个树,可以使用TreeView和TreeNode。(我认为从技术上讲,你可以创建一个TreeNode而不把它放在GUI上,但它确实比一个简单的自定义TreeNode实现有更多的开销。)

见https://github.com/YaccConstructor/QuickGraph(原http://quickgraph.codeplex.com/)

QuickGraph为。net 2.0及更高版本提供了通用的有向/无向图数据结构和算法。QuickGraph提供了深度优先搜索、宽度优先搜索、A*搜索、最短路径、k-最短路径、最大流量、最小生成树、最小公共祖先等算法……QuickGraph支持MSAGL, GLEE和Graphviz来呈现图形,序列化到GraphML等。

还有另一种树结构:

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

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??