In this section we will consider two very important data structures - graphs and trees.

We are learning ...


So that we can ...



Way back in the AS part of the course, we met the 'Poor cartographer' - a problem in graph colouring. We actually used a game called Floodfill (which I'm not expecting you to play now, but you probably will!) A solution to this problem involves drawing graphs - connected diagrams which are used, in this case, to represent barred relationships between areas to be coloured. Using this data structure and a particular algorithm, we were able to deduce a solution (though not always optimal) to the problem.




Binary tree implementation

using System;

class TreeNode
{
    public int data;
    public TreeNode left, right;

    public TreeNode(int data)
    {
        this.data = data;
        left = null;
        right = null;
    }
}

class BinaryTree
{
    public TreeNode root;

    public BinaryTree()
    {
        root = null;
    }

    public void Insert(int data)
    {
        root = Insert(root, data);
    }

    private TreeNode Insert(TreeNode node, int data)
    {
        if (node == null)
        {
            node = new TreeNode(data);
        }
        else if (data < node.data)
        {
            node.left = Insert(node.left, data);
        }
        else
        {
            node.right = Insert(node.right, data);
        }
        return node;
    }

    public void Traverse()
    {
        Traverse(root);
    }

    private void Traverse(TreeNode node)
    {
        if (node != null)
        {
            Traverse(node.left);
            Console.Write(node.data + " ");
            Traverse(node.right);
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.Insert(5);
        tree.Insert(3);
        tree.Insert(8);
        tree.Insert(1);
        tree.Insert(4);
        tree.Insert(7);
        tree.Insert(9);

        Console.WriteLine("Tree traversal:");
        tree.Traverse();
    }
}

This implementation defines two classes:

TreeNode

which represents a single node in the binary tree, and

BinaryTree

which represents the binary tree as a whole. The

TreeNode

class has three fields:

data

which stores the node's value, and

left

and

right

which point to the node's left and right child nodes. The

BinaryTree

class has one field

root

which points to the root node of the tree.

The

BinaryTree

class defines two methods:

Insert

and

Traverse

. The

Insert

method inserts a new node with the given value into the tree, and the

Traverse

method performs an in-order traversal of the tree and prints out the values of each node.

In the

Main

method, we create a new

BinaryTree

object, insert some nodes, and then traverse the tree. The output of this program would be:

Tree traversal:
1 3 4 5 7 8 9

...which shows that the nodes have been inserted into the tree correctly and that the traversal algorithm is working.