13,702,370 members
Add your own
alternative version

#### Stats

11.9K views
305 downloads
34 bookmarked
Posted 16 Aug 2014
Licenced CPOL

# Trees - Part I

, 16 Aug 2014
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)

## About the Author

 schoder.uk United Kingdom
generative artist: schoder.uk

## Comments and Discussions

 First Prev Next
 My vote of 3 53V3N19-Aug-14 10:54 53V3N 19-Aug-14 10:54
 Really looking forward to Part II woutercx18-Aug-14 2:24 woutercx 18-Aug-14 2:24
 Re: Really looking forward to Part II Paul C. Rhodes18-Aug-14 11:09 Paul C. Rhodes 18-Aug-14 11:09
 Last Visit: 31-Dec-99 18:00     Last Update: 20-Sep-18 2:43 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web06-2016 | 2.8.180906.1 | Last Updated 16 Aug 2014
Article Copyright 2014 by dietmar schoder
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid