Tree structure ?

  • Thread starter Thread starter JezB
  • Start date Start date
J

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.
 
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 ...
 
Back
Top