Tree structure ?

[JezB]

I have trawled through the System.Collections namespace looking for some
structure that will enable me to represent and manipulate tree structures,
as yet to no avail.

Of course I can represent a tree as a Hashtable with one part of the Value
of each entry pointing to the key of the parent, but it strikes me that this
is only usefull for drilling up from a child to a parent node - to find all
the children of a node I'd need to scan the whole table!

There must be a native tree-like structure with supporting methods to help
in tree-walking ... please someone point me to it !

NB. I cant use a windows forms TreeView control since this is in library
code that may be used by asp.net also.

 

[Herfried K. Wagner [MVP]]

I have trawled through the System.Collections namespace looking for some
structure that will enable me to represent and manipulate tree structures,
as yet to no avail.

There is nothing available in the .NET Framework. You may want to have
a look at this library:

<http://www.brpreiss.com/books/opus6/>

 

[JezB]

Thanks that confirms what I suspected. I've just written this generic set of classes to handle it - well it compiles but I havent tested it yet but I'm thinking along these lines for something generic enough to handle key/value pairs in a tree structure :-

// ----------------------------------------------------
// CLASSES TO REPRESENT A TREE OF CONTROLS
// ----------------------------------------------------

// A Node is either a Leaf or a Branch (ABSTRACT)
abstract class Node
{
// Fields
public string key;
public object val;

// Constructors
public Node( string key, object val )
{
this.key = key;
this.val = val;
}

// Methods
abstract public void Add(Node node);
abstract public void Remove( string key );
abstract public object FindNode (string key); // anywhere under node not just in immediate children
}

class Branch : Node
{
// Fields
private Hashtable children = new Hashtable(); // hashtable holding child Nodes
// Constructors
public Branch( string key, object val ) : base( key, val ) {}
// Methods
public override void Add( Node node )
{
children.Add( node.key, node.val );
}
public override void Remove( string key )
{
children.Remove( key );
}
public override object FindNode (string key)
{
if (key == this.key)
{
return this.val;
}
else
{
foreach( Node node in children )
{
object foundObject = node.FindNode(key); // this itself will drill down to ITS children
if (foundObject != null)
{
return foundObject;
}
}
return null;
}
}
}

class Leaf : Node
{
// Constructors
public Leaf( string key, object val ) : base( key, val ) {}
// Methods
public override void Add( Node c )
{
// cannot add to a leaf
}
public override void Remove( string key )
{
// cannot remove from a leaf
}
public override object FindNode (string key)
{
if (key == this.key)
{
return this.val;
}
else
{
return null;
}
}
}

I also needed to be able to find a tree node by key anywhere under a starting node - a kind of tree-walking method. I hope I have this right. My only concern is efficiency if the tree gets very large ...