Click here to Skip to main content
11,712,270 members (71,863 online)
Click here to Skip to main content

Trees - Part I

, 16 Aug 2014 CPOL 7.3K 206 30
Rate this:
Please Sign up or sign in to vote.
An introduction to trees: generating and drawing.

Introduction

"A tree is a non-linear data structure that consists of a root node and potentially many levels of additional nodes that form a hierarchy." (Wikipedia).

How do we work with trees in OOP and C#? Let us keep it simple.

Background

If you want to know more about the tree/graph theory, you can e.g. study this basic material: Tree Graph Theory, Trees and Graphs, Parse Trees and Syntax Trees, Tree data class for C++, Binary Tree Operations, Tree Container Library, Visual Tree and Logical Tree in WPF, An Extensive Examination of Data Structures, Tree decomposition, Tree structure.

But I want to present less of the theory and more of the fun with trees here:

 

The Model

The best choice for this task should be the "composite pattern". And you can try it, if you want. But I'm working with the following adapted model:

The abstract Node has a Level, a Parent and maybe Children. It provides a Method for walking through the tree (WalkThroughTree) and for any form of aggregation (Aggregate).

Each specific TreeNode then contains the information for the graph on the canvas (StartPoint, Vector, Endpoint), and it provides all necessary methods for generation, calculation and drawing of the tree - node per node.

Let us see, how far we will come with it.

The Implementation in C#

We start with this basic principle:

This is a very regular tree with (constantly) three branches per node and a total number of four levels.

The following code shows the abstract class for the Node in general (only containing its Parent and its Children) and its WalkThroughTree-method for any traversal process performed for each tree node one after the other. Most important here is the Action as a parameter of the WalkThroughMethod. This Action can be filled with any method you want to be applied to each node later on.

public delegate void DoWalkThrough(Node Node, int Int1, int Int2); // Action delegate

public abstract class Node
{
    public Node Parent;
    public List<node> Children;
    public int Index = 0;

    public Node(int Level, Node Parent = null)
    {
        this.Parent = Parent;
        if (Parent != null)
        {
            if (Parent.Children == null)
                Parent.Children = new List<node>();
            Index = Parent.Children.Count;
            Parent.Children.Add(this);
        }
    }

    public static void WalkThroughTree(Node ActualNode, DoWalkThrough Action,
                                       int MaximumOfLevels = Int32.MaxValue, int Level = 0)
    {
        if (Level >= MaximumOfLevels)
            return;
        Action(ActualNode, MaximumOfLevels, Level); // Perform action for each node
        if (ActualNode.Children != null)
            foreach (var child in ActualNode.Children)
                WalkThroughTree(child, Action, MaximumOfLevels, Level + 1);
    }
}

So let us generate the tree objects. I separated the TreeNode from the Node, because I use the abstract Node class for all kinds of tree nodes, not only for those I want to paint on canvas. But when I want to paint an artificially generated tree, I use the following TreeNode class with its StartPoint, Vector, and EndPoint plus its possibility to Generate a tree with a given NumberOfLevels and a given NumberOfBranches (=number of children) per node.

The Generate method here of course has to follow exactly the format of the DoWalkThrough-delegate from above, because we want to hand it over to the general WalkThroughTree-method of the Node.

public class TreeNode : Node
{
    public static int NumberOfBranches = 3;
    public static int NumberOfLevels = 4;

    public Point StartPoint { get; set; }
    public Vector Vector { get; set; }
    public Point EndPoint { get { return StartPoint + Vector; } }

    public TreeNode(int Level = 0, Node Parent = null)
        : base(Level, Parent)
    {
    }

    // Specific DoWalkThrough-Action:
    public static void Generate(Node ActualNode, int MaximumOfLevels, int Level = 0)
    {
        if (Level >= MaximumOfLevels - 1)
            return;
        for (var i = 0; i < TreeNode.NumberOfBranches; i++)
            new TreeNode(Level + 1, ActualNode);
    }
}

Now we are ready for generating and painting the tree. To achieve this let us look a little bit into the basic parameters of the graphical representation of a tree in general. The shape of a tree is defined by its StartPoint, the orientation and the length of its root Vector and the Angle which defines the span of its branches:

As you can see, we let the Angle decrease with each new level here. That makes this specific tree look better. The root Vector points upwards (e.g. "0, -80"), but you can choose any other direction based on any other StartPoint, because each following branch will calculate its position and its direction based on its Parent's position and direction.

Now we create the root node paintRoot and apply the method TreeNode.Generate to it - and to all its children. Yes, it has no children at the beginning, but when our WalkThroughTree applies the TreeNode.Generate-method to the root node for the first time, the Generate-method will generate children for the root. And the WalkThroughTree immediately will apply the TreeNode.Generate-method again to all the new children which the Generate-method had just added to the root node. And so on. The process stops for each branch, when the given NumberOfLevels is reached, and continues every time with the next branch until the whole tree is generated:

public MainWindow()
{
    InitializeComponent();

    var paintRoot = new TreeNode() { StartPoint = new Point(320, 400), Vector = new Vector(0, -80) };

    Node.WalkThroughTree(paintRoot, TreeNode.Generate, TreeNode.NumberOfLevels);
}

Now comes the painting. First we calculate the points and vectors for each node. Again we use the WalkThroughTree-method, but this time we hand over the method TreeNode.CalcGraph, which looks like this:

// DoWalkThrough
public static void CalcGraph(Node ActualNode, int MaximumOfLevels = Int32.MaxValue, int Level = 0)
{
    if (ActualNode.IsRoot)
        return;
    var node = ActualNode as TreeNode;
    var parent = ActualNode.Parent as TreeNode;
    double angle = 110 / Level;

    node.StartPoint = parent.EndPoint;
    node.Vector = parent.Vector;

    node.RotateVector(-angle / 2 + node.Index * (angle / (parent.Children.Count - 1)));
}
private void RotateVector(double Angle)
{
    var mId = Matrix.Identity;
    mId.Rotate(Angle);
    Vector = mId.Transform(Vector);
}

The span of the branches is 110 degrees at the beginning, and all points and vectors are calculated and stored in the nodes when we walk throught the tree applying the CalcGraph-method:

Node.WalkThroughTree(paintRoot, TreeNode.CalcGraph);

So we can connect the points on the canvas. In this case I prefer a StreamGeometry which draws the branches (black) and skips drawing whenever going back to the next start point (shown in blue here). Here you see the traversal of the tree by our WalkThroughTree-method shown in detail in orange:

Based on this pattern let us present the result on the screen. We collect all points, define some simple XAML, and produce the StreamGeometry data for the Path in the window:

TreeNode.Points = new List<Point>();
Node.WalkThroughTree(paintRoot, TreeNode.CollectPointsForDrawing);
public static List<point> Points;

// DoWalkThrough
public static void CollectPointsForDrawing(Node ActualNode,
                                           int MaximumOfLevels = Int32.MaxValue, int Level = 0)
{
    Points.Add((ActualNode as TreeNode).StartPoint);
    Points.Add((ActualNode as TreeNode).EndPoint);
}
public static StreamGeometry TreeGraph(Point StartPoint, Point[] Points)
{
    StreamGeometry lines = new StreamGeometry();
    var i = 0;

    using (StreamGeometryContext ctxt = lines.Open())
    {
        ctxt.BeginFigure(StartPoint, false, false);
        foreach (var point in Points)
            ctxt.LineTo(point, (++i % 2 == 0) ? true : false, false);
    }
    lines.Freeze();
    return lines;
}
<Window x:Class="Tree.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        Title="Tree" Width="Auto" Height="Auto" SizeToContent="WidthAndHeight">
    <Canvas Name="xamlCanvas" Width="640" Height="640">
        <Path Name="xamlPath" Stroke="Black" StrokeThickness="1" />
    </Canvas>
</Window>
xamlPath.Data = TreeNode.TreeGraph(paintRoot.StartPoint, TreeNode.Points.ToArray());

That's it: the tree is on the screen!

Here is the summary of the whole process:

public MainWindow()
{
    InitializeComponent();

    var paintRoot = new TreeNode() { StartPoint = new Point(320, 400), Vector = new Vector(0, -80) };

    Node.WalkThroughTree(paintRoot, TreeNode.Generate, TreeNode.NumberOfLevels);
    Node.WalkThroughTree(paintRoot, TreeNode.CalcGraph);
    TreeNode.Points = new List<Point>();
    Node.WalkThroughTree(paintRoot, TreeNode.CollectPointsForDrawing);
    xamlPath.Data = TreeNode.TreeGraph(paintRoot.StartPoint, TreeNode.Points.ToArray());
}

We generate, calculate and draw the tree (Generate, CalcGraph, CollectPointsForDrawing and connect the dots).

Points of Interest

I decided to adapt the composite design pattern here using the possibilities of delegates in C#. Let us see how far we come with that concept when we look at tree aggregations and variations in part II of this article:

 

History

16th of August, 2014 - Published.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Paul C. Rhodes
Architect
United Kingdom United Kingdom
No Biography provided

You may also be interested in...

Comments and Discussions

 
GeneralMy vote of 3 Pin
53V3N19-Aug-14 10:54
professional53V3N19-Aug-14 10:54 
GeneralReally looking forward to Part II Pin
woutercx18-Aug-14 2:24
memberwoutercx18-Aug-14 2:24 
GeneralRe: Really looking forward to Part II Pin
Paul C. Rhodes18-Aug-14 11:09
memberPaul C. Rhodes18-Aug-14 11:09 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150819.1 | Last Updated 16 Aug 2014
Article Copyright 2014 by Paul C. Rhodes
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid