Re: Tree design with generics

So if you have any idea how i could model this data structure...

You won't be able to do this for a general Tree unless you restrict
the depth of the Tree to d level and then create d different Node
types like you've shown. If this is appropriate for your application,
I'd say keep going in the direction you've chose.

If you have so support a tree of arbitrary depth, I would create a
Tree data structure with an extra array that holds the class type of
the first element inserted at a particular depth. Any subsequent
insertions would just need to check against this list. Once a level
of the tree has no nodes, clear the list.

If you know the exact class types that each level requires, then just
set the type list statically. Something like the following (off the
top of my head, so don't expect this to compile cleanly)


public class MyTree<E>
{
public class TreeNode
{
protected int depth;
protected E element;
protected ListNode parent;
protected List<E> children = new ArrayList<E>();

public TreeNode( E element, TreeNode parent, int depth )
{
this.element = element;
this.depth = depth;
this.parent = parent;
}
}

private List<Class<E>> depthTypeList = new ArrayList<Class<E>>();
private List<Integer> depthCount = new ArrayList<Integer>();
private TreeNode<E> root = null;
int maxDepth = 0;

public void insert( E element )
{
if ( root == null )
{
root = new TreeNode( element, null, 0 );
depthTypeList.add( element.class );
depthCount.add( 1 );
maxDepth++;
return;
}

// Use whatever method to find the insertion point
// for the new element.
TreeNode parent = findInsertionPoint( element );
TreeNode child = new TreeNode( element, parent, parent.depth +
1 );

// Check against the class type. If this is the first element
// at this level, extend the lists
if ( child.depth > depthTypeList.size() )
{
depthTypeList.add( element.class );
depthCount.add( 1 );
maxDepth++;
}
else
{
Class<E> type = depthTypeList.get( child.depth );
if ( type != null && !element.class.equals( type ))
throw new Exception( "Invalid type for depth " +
child.depth );

depthCount.set( child.depth, depthCount.get( child.depth ) +
1 );
}
}

public void remove( E element )
{
// Find the TreeNode that contains the element
TreeNode node = findTreeNode( element );

// Break the links
node.parent.children.remove( node );
node.parent = null;

// Update the class information
int depth = node.depth;
int count = depthCount.get( depth );

depthCount.set( depth, count - 1 );

// If this was the last node from a row, clear the class type
if ( count == 1 )
depthTypeList.set( depth, null );
}
}
.

Relevant Pages

  • Re: Unique identifier in every treenode?
    ... And it's really confusing the way the tree is being stored to whatever ... Then in the "Load" method, it deserializes the stored data into an array of TreeNodes, representing the root nodes, and adds each root node to the tree. ... Since TreeNode implements ISerializable and assuming the code you posted works, it must include logic for serializing the entire structure under a given TreeNode. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Unique identifier in every treenode?
    ... the tree is built. ... It would be up to the client code to impose any sort of unique identifier and store it with the TreeNode. ... Even in a regular database you can use the database itself to specify relationships between records in the database representing nodes, something like XML provides a natural "containment" semantic that would allow the tree structure to be represented without explicit references between nodes, and even a plain text file can be used to reliably store a tree structure as long as you have _some_ way of describing the structure. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Tree Node Rename Performance Problem
    ... I have two objects here ProjectNode, my business obejct and TreeNode a TreeNode of the TreeView in C#. ... > of the particular node in the whole Tree View. ... project node to a parent node), you should only be adding a reference to the ... Project Node A (a reference that points to instance A) ...
    (microsoft.public.dotnet.languages.csharp)
  • Binary Search Tree Input Problem
    ... typedef char DataType; ... // TreeNode struct ... // Recursively insert an item in the tree, ... // Program to test BinarySearchTree class: ...
    (comp.lang.cpp)
  • Binary Search Tree input question
    ... typedef char DataType; ... // TreeNode struct ... // Recursively insert an item in the tree, ... // Program to test BinarySearchTree class: ...
    (sci.lang)