Problem
I was seeking for a tree or graph data structure in C#, but it appears that none is available. An In-Depth Analysis of Data Structures in C# 2.0 explains why. Is there a library that provides this feature that is widely used? Perhaps by using a strategy pattern to address the concerns raised in the article.
Building my own tree, like implementing my own ArrayList, makes me feel a little stupid.
I’m looking for a general tree that can be unbalanced. Consider a directory tree. C5’s tree structures appear to be implemented as balanced red-black trees, which are better suited to search than displaying a hierarchy of nodes.
Asked by stimms
Solution #1
My greatest recommendation is that there is no such thing as a standard tree data structure because there are so many different methods to implement it that it’s difficult to cover all bases with just one solution. The less relevant a solution is to any given problem, the more particular it is. Even LinkedList irritates me: what if I want a circular linked list?
A collection of nodes will be the basic structure you’ll need to construct, and here are some alternatives to get you started. Let’s pretend that the Node class is the solution’s base class.
If you need to only navigate down the tree, then a Node class needs a List of children.
The Node class requires a link to its parent node if you need to navigate up the tree.
Create an AddChild function to handle all of the details of these two points, as well as any additional business logic that needs to be handled (child limits, sorting the children, etc.)
Answered by David Boike
Solution #2
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 lines of code for a simple recursive implementation… Simply retain a reference to the tree’s root outside of the class, or wrap it in another class, perhaps renamed TreeNode??
Answered by Aaron Gage
Solution #3
Here’s mine, which is extremely similar to Aaron Gage’s but, in my opinion, a little more traditional. I haven’t had any performance difficulties using ListT> for my needs. If necessary, switching to a LinkedList would be simple.
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()));
}
}
}
Answered by Ronnie Overby
Solution #4
Another type of tree structure:
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
}
Sample usage:
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");
}
}
BONUS See a fully grown tree with:
Answered by Grzegorz Dev
Solution #5
dictionaries, g sets, and bags If you want to learn more about how they were implemented, you can look at the source code. (While I haven’t used any of the tree structures specifically, I have used C5 collections in production code with good results.)
Answered by McKenzieG1
Post is based on https://stackoverflow.com/questions/66893/tree-data-structure-in-c-sharp