Finding all objects of type T in a tree structure C#

Question

Hi,

I need to write a tree search method which takes a type parameter T and returns all items of type T that exist in the tree. Is there any way to do this? I would prefer elegance over efficiency at this point...

Answer 1

Assuming your tree is generic. i.e. Item<T>.

int count = yourTree.Count(p => p == typeof(T));

Otherwise, parse each node and compare "item == typeof(T)"

Answer 2

Well, internally the method would have to iterate over all the elements of the tree, so the skip to just enumerating over it, and using the OfType LINQ method isn't that far:

var onlyTs = yourTree.OfType<SomeT>();

Answer 3

What you need is a basic tree traversal function (preorder, inorder or postorder -- this doesn't matter) and a filter function. Then you can compose those two together and get what you need:

IEnumerable<T> Traverse(Tree<T> tree)
{
    yield return tree.Data;

    foreach(Tree<T> subtree in tree.Subtrees)
        foreach(T t in Traverse(subtree))
            yield return t;
}

IEnumerable<U> Filter<T, U>(IEnumerable<T> source)        
    where U : T
{
    foreach(T t in source)
        if(t is U)
            yield return (U)t;
}

Answer 4

Something like this:

internal static IEnumerable<T> AllDescendantNodes<T>( this TreeNode input ) 
    where T class;
{
    T current = null;
    foreach ( TreeNode node in input.Nodes )
        if( (current = node as T) != null )
        {
            yield return current;
            foreach ( var subnode in node.AllDescendantNodes<T>() )
                yield return subnode;
        }
}

You would then call this against the root node as an extension method:

foreach( MyCustomNodeClass item in rootNode.AllDescendantNodes<MyCustomNodeClass>() ) 
{
    ...
}