5
\$\begingroup\$

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?

\$\endgroup\$
0

1 Answer 1

3
\$\begingroup\$

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);
}
\$\endgroup\$
1
  • \$\begingroup\$ Thank you very much Mattias. Thanks for walking me through each of the steps. I will incorporate all suggestions and post back. \$\endgroup\$
    – djpanda
    Commented Apr 24, 2016 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.