Implementing Binary Tree using Queue in C#

Question

I am in the process of learning data structures and I am trying to implement Binary Tree using Queue in C#.

Below are my Tree implementation classes.

public class Tree
{
    public char Data { get; set; }
    public Tree LChild { get; set; }
    public Tree RChild { get; set; }
}

public class TreeImplementation
{
    //Initialize tree nodes with data.
    Tree _rootNodeF = new Tree {Data = 'F'};

    Tree _lChildNodeD = new Tree { Data = 'D' };
    Tree _rChildNodeJ = new Tree { Data = 'J' };

    Tree _lChildNodeB = new Tree { Data = 'B' };
    Tree _rChildNodeE = new Tree { Data = 'E' };

    //Initialize an empty queue to use for tree traversal.
    Queue<Tree> _treeQueue = new Queue<Tree>();

    public  TreeImplementation()
    {
        _rootNodeF.LChild = _lChildNodeD;
        _rootNodeF.RChild = _rChildNodeJ;

        _lChildNodeD.LChild = _lChildNodeB;
        _lChildNodeD.RChild = _rChildNodeE;

    }

    public void LevelOrder()
    {
            //Add root node to the queue.
            _treeQueue.Enqueue(_rootNodeF);

            //Create tempNode to add next node to the queue.
            Tree tempNode = new Tree();

            while (_treeQueue.Count != 0)
            {
                tempNode = _treeQueue.Dequeue();

                VisitedTreeNode(tempNode.Data);

                if (tempNode.LChild == null) continue;
                _treeQueue.Enqueue(tempNode.LChild);

                if (tempNode.RChild != null)
                {
                    _treeQueue.Enqueue(tempNode.RChild);
                }
            }
    }

    //Access the data at the node.
    public void VisitedTreeNode(char queueData)
    {
        Console.WriteLine(queueData);
    }

}

I am calling the LevelOrder() method in the main method in another class.

How can I improve my code?

Answer 1

As a first step, TreeImplementation can create the tree in the constructor and only keep a reference to the root node. Also the queue is only used in LevelOrder and should be moved there.

public class TreeImplementation
{
    Tree _rootNodeF;

    public TreeImplementation()
    {
        _rootNodeF = new Tree {
            Data = 'F',
            LChild = new Tree {
                Data = 'D',
                LChild = new Tree { Data = 'B' },
                RChild = new Tree { Data = 'E' }
            },
            RChild = new Tree { Data = 'J' }
        };
    }

    public void LevelOrder()
    {
        //Initialize an empty queue to use for tree traversal.
        Queue<Tree> _treeQueue = new Queue<Tree>();
        .
        .
        .
    }
}

To make sure future tree manipulations doesn't cause a bug in LevelOrder(), I'd just remove the mini-optimization of the continue statement. Also, checking if the queue has Any() elements is semantically better than checking if Count() != 0. tempNode isn't used outside the while loop and is initialized with an object that is never used. Move the declaration inside the loop instead.

LevelOrder() is actually a tree walker method. I'd rename it to ForEach() instead and pass in an Action<char> it could call instead of the hard coded method VisitedTreeNode(). The walker could then be reused easier.

Now LevelOrder() has been replaced with:

    public void ForEach(Action<char> action)
    {
        Queue<Tree> _treeQueue = new Queue<Tree>();
        _treeQueue.Enqueue(_rootNodeF);

        while (_treeQueue.Any())
        {
            var tempNode = _treeQueue.Dequeue();

            action(tempNode.Data);

            if (tempNode.LChild != null)
            {
                _treeQueue.Enqueue(tempNode.LChild);
            }

            if (tempNode.RChild != null)
            {
                _treeQueue.Enqueue(tempNode.RChild);
            }
        }
    }

.. and can be called with treeImplementation.ForEach((queueData) => Console.WriteLine(queueData));

Implementing the IEnumerable interface

It could probably be userful to manipulate Tree structures with the built in methods of C#, such as foreach() or any Linq calls. To do this, you need to implement the IEnumerable interface in Tree:

public class Tree : IEnumerable<char>
{
    public char Data { get; set; }
    public Tree LChild { get; set; }
    public Tree RChild { get; set; }


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

    public IEnumerator<char> GetEnumerator()
    {
        yield return Data;
        if (LChild != null)
        {
            foreach (var data in LChild)
            {
                yield return data;
            }
        }
        if (RChild != null)
        {
            foreach (var data in RChild)
            {
                yield return data;
            }
        }
    }
}

Of course this implementation totally makes ForEach above redundant, as it now can be replaced with:

    public void ForEach(Action<char> action)
    {
        foreach (var data in _rootNodeF)
            action(data);
    }

Generics

As a final thought, Tree is a pretty generic construct and would be a lot more useful as:

public class Tree<T> : IEnumerable<T>
{
    public T Data { get; set; }
    public Tree<T> LChild { get; set; }
    public Tree<T> RChild { get; set; }


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

    public IEnumerator<T> GetEnumerator()
    {
        yield return Data;
        if (LChild != null)
        {
            foreach (var data in LChild)
            {
                yield return data;
            }
        }
        if (RChild != null)
        {
            foreach (var data in RChild)
            {
                yield return data;
            }
        }
    }
}

Creating your specific tree is the done with

var myTree = new Tree<char>
{
    Data = 'F',
    LChild = new Tree<char>
    {
        Data = 'D',
        LChild = new Tree<char> { Data = 'B' },
        RChild = new Tree<char> { Data = 'E' }
    },
    RChild = new Tree<char> { Data = 'J' }
};

foreach(var data in myTree)
{
    Console.WriteLine(data);
}