Tree data structure in C#

I was looking for a tree or graph data structure in C# but I guess there isn't one provided. An Extensive Examination of Data Structures Using C# 2.0 explains a bit about why. Is there a convenient library which is commonly used to provide this functionality? Perhaps through a strategy pattern to solve the issues presented in the article.

I feel a bit silly implementing my own tree, just as I would implementing my own ArrayList.

I just want a generic tree which can be unbalanced. Think of a directory tree. C5 looks nifty, but their tree structures seem to be implemented as balanced red-black trees better suited to search than representing a hierarchy of nodes.

---

My best advice would be that there is no standard tree data structure because there are so many ways you could implement it that it would be impossible to cover all bases with one solution. The more specific a solution, the less likely it is applicable to any given problem. I even get annoyed with LinkedList - what if I want a circular linked list?

The basic structure you'll need to implement will be a collection of nodes, and here are some options to get you started. Let's assume that the class Node is the base class of the entire solution.

If you need to only navigate down the tree, then a Node class needs a List of children.

If you need to navigate up the tree, then the Node class needs a link to its parent node.

Build an AddChild method that takes care of all the minutia of these two points and any other business logic that must be implemented (child limits, sorting the children, etc.)

---

I hate to admit it but I ended up writing my own tree class using a linked list. On an unrelated note I just discovered this round thing which, when attached to a thing I'm calling an 'axle' allows for easier transportation of goods.

---

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？

链接地址: http://www.djcxy.com/p/26948.html

上一篇: 学习算法和数据结构基础

下一篇: C＃中的树数据结构