Back
Featured image of post C# Tutoring Subject: MyTrees
ACDC

C# Tutoring Subject: MyTrees

Tutoring (soutien) subject for the 2021-03-18 session in C#

C# Soutien/Tutoring TP – MyTrees

This mini-subject intends to give you an example of how to use and why use some of the features we showed you.

In this subject, we will go over:

  • Basic OOP (Class, fields, methods, constructor)
  • Interfaces
  • Functions as parameters
  • Genericity
  • Binary trees and general trees (+ pre-order and post-order traversal)
  • Enums

Binary trees

Let’s implement a binary tree. As a reminder, a binary tree is a recursive structure made of nodes, starting from a root node. Each node may have a left child, a right child, both or neither.

Here is an example of a binary tree:

    a <------- Root node
   / \
  b   e
 / \
c   d <------- Leaf node

BinTreeNode

We will first implement our node in a BinTreeNode class. For now, we consider that all of our nodes will be labeled using characters (e.g. 'A'), stored in a value field, with getters and setters.

Here is the basic structure for the BinTreeNode class:

public class BinTreeNode
{
    private char value;
    private BinTreeNode leftNode; // FIXME: default value
    private BinTreeNode rightNode; // FIXME: default value

    // Constructor for a leaf
    public BinTreeNode(char value)
    {
        // FIXME
    }

    public BinTreeNode GetLeftNode()
    {
        // FIXME
        throw new NotImplementedException();
    }

    public BinTreeNode GetRightNode()
    {
        // FIXME
        throw new NotImplementedException();
    }

    public void SetLeftNode()
    {
        // FIXME
        throw new NotImplementedException();
    }

    public void SetRightNode()
    {
        // FIXME
        throw new NotImplementedException();
    }
}

Use null to signal that there is a node is absent (for example, a leaf would have both leftNode and rightNode set to null).

BinTree

While we could represent our entire tree by just having the root node, it is easier to have a separate class for the entire tree, mostly because we will later add functionality to that class.

We can then make our BinTree class which just contains the root of the tree for now:

public class BinTree
{
    private BinTreeNode root; // FIXME: Default value

    // We will keep the default constructor, no need to create our own

    public BinTreeNode GetRoot()
    {
        // FIXME
        throw new NotImplementedException();
    }

    public void SetRoot()
    {
        // FIXME
        throw new NotImplementedException();
    }
}

It is possible to have an empty tree: just set the root to null.

General trees

Let’s now make a general tree. A general tree is like a bin tree, except that nodes can have any number of children.

GeneralTreeNode

Let’s make its nodes, which, this time, will store its children as a list. Let’s also implement a list-like way of getting and replacing the nth child, by doing theNode[n]. We’ll also create an AddChild function, which will append the child to the end of your internal list.

public class GeneralTreeNode
{
    private char value;
    private List<GeneralTreeNode> children; // FIXME: default value

    public GeneralTreeNode(char value)
    {
        // FIXME
    }

    public char GetValue()
    {
        // FIXME
        throw new NotImplementedException();
    }

    public uint GetChildrenCount()
    {
        // FIXME
        throw new NotImplementedException();
    }

    public void AddChild(GeneralTreeNode node)
    {
        // FIXME
        throw new NotImplementedException();
    }

    /*
     * This is an indexer. It allows us to get the nth child of a node by using
     * the same syntax that we already use lists, arrays, dictionaries, etc.
     *
     * https://docs.microsoft.com/en-us/dotnet/csharp/programming-guideindexers/
     */
    public GeneralTreeNode this[int i]
    {
        // This one is for 'var x = aNode[i]'
        get
        {
            // FIXME
            throw new NotImplementedException();
        }

        // This one is for 'aNode[i] = x'
        set
        {
            // FIXME
            throw new NotImplementedException();
        }
    }
}

GeneralTree

And now, the tree class:

public class GeneralTree
{
    private GeneralTreeNode root; // FIXME: Default value

    public GeneralTreeNode GetRoot()
    {
        // FIXME
        throw new NotImplementedException();
    }

    public void SetRoot(GeneralTreeNode newRoot)
    {
        // FIXME
        throw new NotImplementedException();
    }
}

Now, let’s traverse our trees! We want to create functions that print all of our nodes in pre-order or post-order, something like…

Tree:
    a
   / \
  b   e
 / \
c   d

Pre-order: a b c d e
Post-order: c d b e a

:thonk:

While a quick and dirty solution would be to just implement the function directly, but that’s not super interesting or useful and leads to a lot of copy-pasting…

PrintMePostOrder(BinTree)
{
    ... the entire post order traversal algorithm ...
}

PrintMePreOrder(BinTree)
{
    ... the entire pre order traversal  algorithm ...
}

PrintMePostOrder(GeneralTree)
{
    ... the entire post order traversal algorithm ...
}

PrintMePreOrder(GeneralTree)
{
    ... the entire pre order traversal  algorithm ...
}

As a developer your goal should be to make functions that are reusable. This means functions that can be used for many things, so that you don’t have to copy paste everything all the time.

Let’s think about the problem we want to solve: I want to traverse my tree, and do “something” on each node… How could I express that in code?

We could say that all of our trees would have “TraversePreOrder” and “TraversePostOrder” functions, that would then take a function reference to the action we would like to make. That sounds good, but here, we have another problem. Let’s write some pseudo code down:

PrintValue(char value)
{
    Write value to the console
}

PrintMePostOrder(BinTree)
{
    Call "TraversePostOrder" on the tree, with "PrintValue" as a parameter
}

PrintMePreOrder(BinTree)
{
    Call "TraversePreOrder" on the tree, with "PrintValue" as a parameter
}

PrintMePostOrder(GeneralTree)
{
    Call "TraversePostOrder" on the tree, with "PrintValue" as a parameter
}

PrintMePreOrder(GeneralTree)
{
    Call "TraversePostOrder" on the tree, with "PrintValue" as a parameter
}

That’s much better, but we can go further. Our PrintMe functions don’t really care about the tree that is passed as a parameter: the only thing they care about is that the “thing” in the parameter is something we can traverse in pre-order and post-order. How can we say this in code?

With an interface!

Remember interfaces? They are “lightweight abstract classes”, and your ACDC’s might have told you that these are useful for representing the phrase “Hey, my class is ‘…able’”. That’s exactly what me need! We want to say “Hey, my binary tree is traversable” and “Hey, my general tree is traversable”. Through the interface, we’ll be able to say, “hey, my tree can do this thing”.

Our pseudo code now looks pretty clean:

PrintValue(char)
{
    Write the character to the console
}

PrintMePostOrder(ITraversable)
{
    Call "TraversePostOrder" on the traversable, with "PrintValue" as a parameter
}

PrintMePreOrder(ITraversable)
{
    Call "TraversePreOrder" on the traversable, with "PrintValue" as a parameter
}

… But still not clean enough. If you remember your algorithmics classes, you may remember that pre-order and post-order traversal is pretty much identical. In order to not have to implement everything twice in our trees (once for pre-order in TraversePreOrder, once for post-order in TraversePostOrder), let’s instead add a parameter to a single “TraverseNodes” function.

What will that parameter be? Great question! In this case, our options are:

  • A boolean, which is not great: the question is “pre-order or post-order”, not “true or false”. What is true? What is false? This is basically as useful as using stray integers for this.
  • Integers, where we could say that 1 is pre-order and 2 is post-order. But then, what if I give the function 3, 4 or -571, your code may explode, and it would be your fault, since you did not restrict the integers in any meaningful, compiler-verifiable way. But then… Wait, didn’t we talk about enums for this?
  • Enums, they are great for this sort of situation: X, Y or Z, all of them being different options that can’t be cleanly expressed using booleans or numbers.

Let’s say we create a TraversalType enum that contains two values, PreOrder and PostOrder.

Our pseudo code from the PrintMe side does not change all that much…

PrintValue(char)
{
    Write the character to the console
}

PrintMePostOrder(ITraversable)
{
    Call "Traverse" on the traversable, with "PrintValue" and as parameters
}

PrintMePreOrder(ITraversable)
{
    Call "TraversePreOrder" on the traversable, with "PrintValue" as a parameter
}

TraversalType and ITraversable

Create the following interface and enum:

public enum TraversalType
{
    PreOrder,
    PostOrder
}

public interface ITraversable
{
    public void Traverse(TraversalType type,  Action<char> action);
}

Implementations

Next, make both our BinTree and GeneralTree implement ITraversable, and implement the interface’s function in the trees.

Here is the pseudo code for a recursive pre/post-order traversal for binary trees:

bin_tree_traversal(node):

  #-- Pre-order callback here --#

  if node has left child:
    bin_tree_traversal(the node's left child)

  #-- In-order callback here --#

  if node has right child:
    bin_tree_traversal(the node's right child)

  #-- Post-order callback here --

And for general trees:

gen_tree_traversal(node):
  #-- Pre-order callback here --#
  for each child of node:
    gen_tree_traversal(child)
  #-- Post-order callback here --#

PrintMe (for real this time)

Now that this is done, create the PrintMePreOrder and PrintMePostOrder functions.

public static class Printers
{
    private static void PrintIt(char c)
    {
        // FIXME
        throw new NotImplementedException();
    }

    public static void PrintMePreOrder(ITraversable traversable)
    {
        // FIXME
        throw new NotImplementedException();
    }

    public static void PrintMePostOrder(ITraversable traversable)
    {
        // FIXME
        throw new NotImplementedException();
    }
}

Genericity

So far, our tree nodes are only capable of containing characters, which is kind of lame. Genericity is here for us!

Genericity makes your class depend on a type, in the “of” sense, for example:

List<string> => I am a list of strings
Dictionary<string, RedPanda> => I am a list of string keys and of red panda values

Remember that, to make a class generic (“A … of T”), simply add <T> next to its name. For example,

// Before
public class BinTree : ITraversable
{
    // ...
}
// After
public class BinTree<T> : ITraversable<T>
{
    // ...
}

Wait… Why did we change the ITraversable class here?

The reason is quite simple: we are also interested in making a “traversable of X”, so the traversable will also be generic. Same goes for our nodes.

Here is what the traversable interface becomes:

public interface ITraversable<T>
{
    public void TraversePreOrder(Action<T> action);

    public void TraversePostOrder(Action<T> action);
}

Make all of the classes and interfaces generic. Obviously, the values will become of type T instead of being characters: make the necessary changes.

Sum of All Nodes

Now that we have made our trees and traversables generic, we can have trees of anything. Let’s see how we can use our traversables using integers…

Write the following function:

public static class Summer
{
    public static int SumOfNodes(ITraversable<int> traversable)
    {
        // FIXME
        throw new NotImplementedException();
    }
}

This function must return the sum of all the nodes in traversable. Order does not matter here as we are working with sums.

You may need an additional private function.

© 2020 - 2022 Zoroblog
Built with Hugo
Theme Stack designed by Jimmy