Traversing a Tree Structure

Question

I am trying to understand how to traverse a tree data structure, and I am having a problem doing it, especially as I am trying to use IEnumerable. I want the tree as a dictionary so I can refer to the nodes by their string names. The tree will hold different class objects but as these objects all implement an interface IMyInterface, type of the tree will be the IMyInterface interface.

I have the tree:

internal class Tree<T>
{
    private TreeNode<T> root;

    internal Tree(T value)
    {
        if (value == null)
        {
            throw new ArgumentNullException(
                "Cannot use a null value to construct a tree.");
        }

        this.root = new TreeNode<T>(value);
    }

    internal Tree(T value, params Tree<T>[] children) : this(value)
    {
        foreach (Tree<T> child in children)
        {
            this.root.AddChild(child.root);
        }
    }

    internal TreeNode<T> Root
    {
        get { return this.root; }
    }

    private void PrintDFS(TreeNode<T> root, int spaces)
    {
        if (spaces < 0)
        {
            throw new ArgumentOutOfRangeException(
                "The number of spaces used to represent the parent-child relation in a tree must be greater than or equal to zero.");
        }

        if (this.root == null)
        {
            return;
        }

        StringBuilder sb = new StringBuilder();
        sb.Append(' ', spaces);
        sb.Append(root.Value);

        TreeNode<T> child = null;

        foreach (Tree<T> child in this.root)     // <--- this generates an error
        {
            PrintDFS(child, spaces);
        }
    }

    // Traverses and prints the tree in
    // Depth-First Search (DFS) manner
    internal void TraverseDFS()
    {
        this.PrintDFS(this.root, 0);
    }
}

And my node class is:

internal class TreeNode<T> : IEnumerable<TreeNode<T>>
{
    private T value;
    private bool hasParent;

    private readonly Dictionary<string, TreeNode<T>> children = new Dictionary<string, TreeNode<T>>();

    internal TreeNode(T value)
    {
        if (value == null)
        {
            throw new ArgumentNullException(
                "Cannot insert null values for a tree node!");
        }

        this.value = value;
        this.children = new Dictionary<string, TreeNode<T>>();      // dictionary that holds the children of each node
    }

    internal T Value
    {
        get { return this.value; }
        set { this.value = value; }
    }

    internal int ChildrenCount
    {
        get
        {
            return this.children.Count;
        }
    }

    internal void AddChild(TreeNode<T> child)
    {
        if (child == null)
        {
            throw new ArgumentNullException(
                "Cannot insert null value as child node.");
        }

        if (child.hasParent)
        {
            throw new ArgumentException(
                "The child node already has a parent.");
        }

        child.hasParent = true;
        this.children.Add(child.ToString(), child);
    }

    internal TreeNode<T> GetChild(string nodeName)
    {
        return this.children[nodeName];
    }

    internal IEnumerator<TreeNode<T>> GetEnumerator()
    {
        return this.children.Values.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    IEnumerator<TreeNode<T>> IEnumerable<TreeNode<T>>.GetEnumerator()
    {
        throw new NotImplementedException();
    }
}

The issue seems to be the code:

foreach (Tree<T> child in this.root)     // <--- this generates an error
{
    PrintDFS(child, spaces);
}

(Code snippet from the Tree class) Any suggestions would be greatly appreciated.

EDIT

I get the error messages:

Error 669 A local variable named 'child' cannot be declared in this scope because it would give a different meaning to 'child', which is already used in a 'parent or current' scope to denote something else.

Error 672 Cannot convert type TreeNode<T> to Tree<T>

And the warning message:

Warning 668 TreeNode<T> does not implement the 'collection' pattern. TreeNode<T>.GetEnumerator() is either static or not public.

Answer 1

Issue #1

Error 669 A local variable named 'child' cannot be declared in this scope because it would give a different meaning to 'child', which is already used in a 'parent or current' scope to denote something else.

TreeNode<T> child = null;

foreach (Tree<T> child in this.root)     // <--- this generates an error
{
     PrintDFS(child, spaces);
}

You already have a child variable. You need to name them differently. The error is pretty self explanatory.

For this situation, just remove child from above the foreach since it is useless there.

foreach (var child in this.root) 
{
     PrintDFS(child, spaces);
}

I think you wanted TreeNode<T>, but not sure what was supposed to actually return out of root.

Issue #2

Error 672 Cannot convert type TreeNode to Tree

If you're supposed to be looping over TreeNode<T>, not Tree<T> as the error states. Just use var unless you are actually trying to iterates trees and not nodes.

Issue #3

Warning 668 TreeNode does not implement the 'collection' pattern. TreeNode.GetEnumerator() is either static or not public.

It needs to be public. Internal does not cut it because it needs to adhere to the IEnumerable contract. Looks like you have that solved though with the explicit implementation of it.

Answer 2

First, replace your 3 GetEnumertor functions with these 2:

public IEnumerator<TreeNode<T>> GetEnumerator()
{
  return this.children.Values.GetEnumerator();
}

IEnumerator IEnumerable.GetEnumerator()
{
  return this.GetEnumerator();
}

Then change the last part of your PrintDFS loop as follows:

//TreeNode<T> child = null;

foreach (var child in this.root)
{
  PrintDFS(child, spaces);
}

That compiles.