我在c#中寻找树或图数据结构,但我猜没有提供。使用c# 2.0的数据结构的广泛检查。是否有一个方便的库通常用于提供这个功能?也许可以通过策略模式来解决文章中提出的问题。

我觉得实现我自己的树有点傻,就像实现我自己的数组列表一样。

我只想要一个一般的树,它可以是不平衡的。想象一个目录树。C5看起来很漂亮,但它们的树结构似乎被实现为更适合搜索的平衡红黑树,而不是表示节点的层次结构。


当前回答

大多数树是由您正在处理的数据形成的。

假设您有一个person类,其中包含某人的细节 父母们,你们愿意让树形结构成为你们的一部分吗 “域类”,或者使用包含链接的单独树类 你的人反对吗?考虑一个简单的操作,比如获取全部 一个人的孙子,应该是这个人的密码 类,或者person类的用户必须知道 单独的树类?

另一个例子是编译器中的解析树…

这两个例子都表明,树的概念是数据域的一部分,使用单独的通用树至少会使创建的对象数量增加一倍,同时也会使API更难再次编程。

我们想要一种重用标准树操作的方法,而不必为所有树重新实现它们,同时又不必使用标准树类。Boost已经尝试为c++解决这类问题,但是我还没有看到任何对. net进行适应的效果。

其他回答

我创建了一个Node<T>类,它可能对其他人有帮助。该类具有如下属性:

孩子们 的祖先 的后代 兄弟姐妹 节点级别 父 根 等。

还有一种可能是将一个带有Id和ParentId的项目平面列表转换为树。节点包含对子节点和父节点的引用,因此迭代节点非常快。

通常优秀的C5通用集合库具有几种不同的基于树的数据结构,包括集、包和字典。如果您想研究它们的实现细节,可以使用源代码。(我在产品代码中使用过C5集合,效果很好,尽管我没有特别使用过任何树结构。)

我已经使用上面的NTree类添加了一个完整的解决方案和示例。我还添加了AddChild方法…

    public class NTree<T>
    {
        public T data;
        public LinkedList<NTree<T>> children;

        public NTree(T data)
        {
            this.data = data;
            children = new LinkedList<NTree<T>>();
        }

        public void AddChild(T data)
        {
            var node = new NTree<T>(data) { Parent = this };
            children.AddFirst(node);
        }

        public NTree<T> Parent { get; private set; }

        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, string t, ref NTree<T> r)
        {
            visitor(node.data, node, t, ref r);
            foreach (NTree<T> kid in node.children)
                Traverse(kid, visitor, t, ref r);
        }
    }

    public static void DelegateMethod(KeyValuePair<string, string> data, NTree<KeyValuePair<string, string>> node, string t, ref NTree<KeyValuePair<string, string>> r)
    {
        string a = string.Empty;
        if (node.data.Key == t)
        {
            r = node;
            return;
        }
    }

使用它

 NTree<KeyValuePair<string, string>> ret = null;
 tree.Traverse(tree, DelegateMethod, node["categoryId"].InnerText, ref ret);

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

我已经完成了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;
    }
}