Tree Terminology

In my last post Tree Data Structures I discussed modelling a tree as a raw data structure. That is, a self-describing tree node. In this post I offer some terminology and search/traversal techniques.

Top

In this post...

• What Is A Tree?
• Trees-Sample Usage
  • Abstract Syntax Tree
  • Document Object Model
  • Hierarchical Data
• Tree Terminology
• Modelling Trees

Top

What Is A Tree?

The following diagram illustrates a basic tree structure.

A tree is data structure that consists of nodes. A tree typically contains a root node (though may contain multiple root nodes). Each tree node contains data that may be searched/traversed.

Top

Examples Of Tree Usage

Trees are an important data structure, examples of use now follow...

Abstract Syntax Tree (AST)

Parsing is essentally data transformation. Take a sequence of characters and produce tokens. One or more tokens are then transformed to create abstract syntax tree nodes (Expressions, Assignment and so on). These nodes can be run against a runtime engine to run script type code. Most modern computer languages follow this idea. AST's can further be transformed to generate intermediate language code (aka byte code).

Top

A Document Object Model

HTML uses a tree structure to describe page elements. The DOM may be manipulated, once the HTML document is fully loaded. The DOM allows new HTML insertion, modifying existing elements and so on. This gives rise to the so-called "dynamic content".

Top

Hierarchical Data

This is possibly where trees excel. Most data is hierarchical in nature. Consider the following simple examples.

• A company
  Has a CEO. The CEO might manage numerous managers. Managers, manage workers.
• A Family
  Has a head of the family. Has grandparents. Has offspring which in turn will have their own offspring.

Top

Tree Terminology

Assuming the following tree...

• A is the root node.
• Node B1, B2, B3 are child nodes of the root node, A
  Examples
  childrenOf(A) => B1, B2, B3
  childrenOf(B3) => c1, c2
  
• Node A, the root node, is also the parent node of nodes B1, B2, B3
  Examples
  parent(B1) => A
  parent(B2) => A
  
• Nodes without child nodes are known as leaf nodes.
  Nodes B1, B2, C1 and D1 in the diagram are leaf nodes as they have no child nodes.
• Nodes have a depth or level.
  The root node(s) are always level 1.
  Node D1, has the highest depth level of 4.
  Examples
  depth(A) => 1
  depth(B1) => 2
  depth(D1) => 4
  
• All nodes bar the root node A are descendants of the root node.
  Examples
  descendants(A) => B1, B2, B3, C1, C2, D1 descendants(B3) => C1, C2, D1
• Sibling nodes are nodes that exist on the same level of the node in question.
  Examples
  siblings(A) => none
  siblings(B1) => B2, B3
  siblings(C1) => C2

Top

Commands

A command encapsulates a unit of work. Typically, a command might insert/update a database record, send an email or just update a model. There are numerous ways one can model a command. In this post I describe a simple command mechanism that is suitable for standalone applications. I will also discuss the pros and cons of the approach.

Top

In this post...

• Project Creation
• Project helper methods
• Simple Command
• Code Walkthrough
• Pros and Cons
• Example
• Testing

Top

Creating The Project

The project is a Console Application, using the .NET Framework (Ver 4.8). The project is named, CommandApp.

No external libraries are required for this project.

Top

Extension/Helper methods

To help visualise program flow I add an extension class.

using System;
namespace CommandApp
{
  public static class Extensions
  {
    //The Trace extension allows one to simply output a value to the console.
    //The method is easily modified to send output elsewhere..
    public static void Trace<T>(this T src) =>
      Console.WriteLine(src);
  }
}

Top

Simple Commands

The simple command encapsulates command values. The command is also responsible for its own behaviour, in this case, executing command code. The command is executed synchronously, that is, on the thread that created the command. The following diagram illustrates the concept.

The client is simply code that creates and executes the command. The code for the simple command is as follows...

Top

using System;

namespace CommandApp.SimpleCommands
{
  public abstract class Command
  {
    protected Command() { }

    public bool IsSuccess => null == Exception;

    public Exception Exception { get; private set; }

    public void Execute()
    {
      try
      {
        OnExecute();
      }
      catch (Exception e)
      {
        this.Exception = e;
      }
    }

    public abstract void OnExecute();
  }
}

Top

Code Walkthrough

• The class is declared as abstract, concrete classes override/implement onExecute to implement the command.
• Client(s) create a new command instance then call the Execute method which catches any exceptions and places into to the Exception property.
• Client(s) can query the command to check for success or failure an act appropriately.

Simple command Pros and Cons

Pros

• Simple to use.
• No infrastructure required.
• Command code, that is values and behaviour all in a single class.
• Works when using the Command base class that refers to a concraete instance. Can thank Polymorphism for this. For example, Command myCmd = new MyCommand()

Top

Cons

• Command is blocking - main thread blocks whilst waiting for command execution.
• Including cross-cutting concerns is difficult unless such concerns are included in the Execute parameters. However, this will complicate calling the Execute method.
• Client(s) can create and execute a given command. Not necessarily bad, but it might be best to separate command creation from command execution. This would allow the software to "inject" code before and after executing code.

Top

Sample Simple Command

The following code illustrates using the simple class. The example Sleeps for 1000ms to simulate a time consuming command.

using System.Threading;

namespace CommandApp.SimpleCommands
{
  public class AddCustomerCommand : Command
  {
    private readonly string _firstName;
    private readonly string _lastName;

    public int Id { get; private set; }

    public AddCustomerCommand(string firstName, string lastName)
    {
      _firstName = firstName;
      _lastName = lastName;
    }

    public override void OnExecute()
    {
      "---------------------------------------------------".Trace();
      $"AddCustomerCommand({_firstName}, {_lastName})".Trace();
      "About to sleep for 1000ms to simulate a time consuming command".Trace();
      Thread.Sleep(1000);
      "Setting Id to 1 to simulate adding a new database record and returning a new Id".Trace();
      Id = 1;
      "completed".Trace();
    }
  }
}

Top

Testing The simple Command

The following code was used to test the simple command...

namespace CommandApp.SimpleCommands
{
  public static class Test
  {
    public static void Run()
    {
      AddCustomerCommand cmd = new AddCustomerCommand("Fred", "Bloggs");
      cmd.Execute();
    }
  }
}

If all goes well, you should see the following text on the command prompt...

Top