C# Data Structures and Algorithms

Marcin Jamro

• Publisher: Packt Publishing
• Year: 2018
• ISBN:
  9781788834681
• Topic: Computer Science
• Subtopic: Programming in C#
• Index: Computer Science

A complete guide on using data structures and algorithms to write sophisticated C# code

Key Features

• Master array, set and map with trees and graphs, among other fundamental data structures
• Delve into effective design and implementation techniques to meet your software requirements
• Explore illustrations to present data structures and algorithms, as well as their analysis in a clear, visual manner

Book Description

Data structures allow organizing data efficiently. They are critical to various problems and their suitable implementation can provide a complete solution that acts like reusable code. In this book, you will learn how to use various data structures while developing in the C# language as well as how to implement some of the most common algorithms used with such data structures.At the beginning, you will get to know arrays, lists, dictionaries, and sets together with real-world examples of your application. Then, you will learn how to create and use stacks and queues. In the following part of the book, the more complex data structures will be introduced, namely trees and graphs, together with some algorithms for searching the shortest path in a graph. We will also discuss how to organize the code in a manageable, consistent, and extendable way. By the end of the book, you will learn how to build components that are easy to understand, debug, and use in different applications.

What you will learn

• How to use arrays and lists to get better results in complex scenarios
• Implement algorithms like the Tower of Hanoi on stacks of C# objects
• Build enhanced applications by using hashtables, dictionaries and sets
• Make a positive impact on efficiency of applications with tree traversal
• Effectively find the shortest path in the graph

Who this book is for

This book is for developers who would like to learn the Data Structures and Algorithms in C#. Basic C# programming knowledge would be an added advantage.

]]>

Variants of Trees

In the previous chapters, you have learned about many data structures, starting with simple ones, such as arrays. Now, it is time for you to get to know a significantly more complex group of data structures, namely trees.

At the beginning of this chapter, the basic tree will be presented, together with its implementation in the C# language and some examples showing it in action. Then, the binary tree will be introduced with a detailed description of its implementation and an example of its application. The binary search tree is another tree variant, which is one of the most popular types of trees, used in many algorithms. The following two sections will cover self-balancing trees, namely AVL and red-black trees.

The remaining part of the chapter is dedicated to heaps as tree-based data structures. Three kinds of heaps will be presented: binary, binomial, and Fibonacci. Such types will be briefly introduced, and the application of these data structures will be shown, using the external package.

Arrays, lists, stacks, queues, dictionaries, sets, and now... trees. Are you ready to increase the level of difficulty and learn the next set of data structures? If so, let's start reading!

In this chapter, the following topics will be covered:

• Basic trees
• Binary trees
• Binary search trees
• AVL trees
• Red-black trees
• Binary heaps
• Binomial heaps
• Fibonacci heaps

Basic trees

Let's start with introducing trees. What are they? Do you have any ideas about how such a data structure should look? If not, let's take a look at the following diagram, which depicts a tree with captions regarding its particular elements:

A tree consists of multiple nodes, including one root (100 in the diagram). The root does not contain a parent node, while all other nodes do. For example, the parent element of node 1 is 100, while node 96 has node 30 as the parent. Moreover, each node can have any number of child nodes, such as three children (that is, 50, 1, and 150) in the case of the root. The child nodes of the same node can be named siblings, as in the case of nodes 70 and 61. A node without children is named a leaf, such as 45 and 6 in the diagram. Take a look at the rectangle with three nodes (that is, 30, 96, and 9). Such a part of the tree can be called a subtree. Of course, you can find many subtrees in the tree.

Let's briefly talk about the minimum and maximum numbers of children of a node. In general, such numbers are not limited and each node can contain zero, one, two, three, or even more children. However, in practical applications, the number of children is often limited to two, as you will see in the following section.

Implementation

The C#-based implementation of a basic tree seems to be quite obvious and not complicated. To do so, you can declare two classes, representing a single node and a whole tree, as described in the following section.

Node

The first class is named TreeNode and is declared as the generic class to provide a developer with the ability to specify the type of data stored in each node. Thus, you can create the strongly-typed solution, which eliminates the necessity of casting objects to target types. The code is as follows:

public class TreeNode<T> { public T Data { get; set; } public TreeNode<T> Parent { get; set; } public List<TreeNode<T>> Children { get; set; } public int GetHeight() { int height = 1; TreeNode<T> current = this; while (current.Parent != null) { height++; current = current.Parent; } return height; } } 

The class contains three properties: the data stored in the node (Data) of the type (T) specified while creating an instance of the class, a reference to the parent node (Parent), and a collection of references to child nodes (Children).

Apart from the properties, the TreeNode class contains the GetHeight method, which returns a height of the node, that is, the distance to the root node. The implementation of this method is very simple, because it just uses the while loop to go up from the node until there is no parent element (when the root is reached).

Tree

The next necessary class is named Tree, and it represents the whole tree. Its code is even simpler than that presented in the preceding section, and is as follows:

public class Tree<T> { public TreeNode<T> Root { get; set; } } 

The class contains only one property, Root. You can use this property to get access to the root node, and then you can use its Children property to obtain data of other nodes located in the tree.

It is worth noting that both TreeNode and Tree classes are generic and the same type is used in the case of these classes. For instance, if tree nodes should store string values, the string type should be used in the case of instances of Tree and TreeNode classes.

Example – hierarchy of identifiers

Do you want to see how to use a tree in a C#-based application? Let's take a look at the first example. The aim is to construct the tree with a few nodes, as shown in the following diagram. Only the group of nodes with darker backgrounds will be presented in the code. However, it is a good idea to adjust the code to extend this tree by yourself.

As you can see in the example, each node stores an integer value. Thus, int will be the type used for both Tree and TreeNode classes. The following part of code should be placed in the Main method in the Program class:

Tree<int> tree = new Tree<int>(); tree.Root = new TreeNode<int>() { Data = 100 }; tree.Root.Children = new List<TreeNode<int>> { new TreeNode<int>() { Data = 50, Parent = tree.Root }, new TreeNode<int>() { Data = 1, Parent = tree.Root }, new TreeNode<int>() { Data = 150, Parent = tree.Root } }; tree.Root.Children[2].Children = new List<TreeNode<int>>() { new TreeNode<int>() { Data = 30, Parent = tree.Root.Children[2] } }; 

The code looks quite simple, doesn't it?

At the beginning, a new instance of the Tree class is created. Then, the root node is configured by creating a new instance of the TreeNode class, setting a value of the Data property (to 100), and assigning a reference to the TreeNode instance to the Root property.

In the following lines, the child nodes of the root node are specified—nodes with values equal to 50, 1, and 150. For each of them, a value of the Parent property is set to a reference to the previously-added root node.

The remaining part of the code shows how to add a child node for a given node, namely for the third child of the root node, that is, the node with value equal to 150. Here, only one node is added, the one with the value set to 30. Of course, you need to specify a reference to the parent node as well.

That's all! You have created the first program that uses trees. Now you can run it, but you will not see any output in the console. If you want to see how data of nodes are organized, you can debug the program and see values of variables while debugging.

Example – company structure

In the previous example, you saw how to use integer values as data for each node in a tree. However, it is also possible to store instances of user-defined classes in nodes. In this example, you will see how to create a tree presenting the structure of a company, divided into three main departments: development, research, and sales.

Within each department there can be another structure, such as in the case of the development team. Here, John Smith is Head of Development. He is a boss for Chris Morris, who is a manager for two junior developers, Eric Green and Ashley Lopez. The latter is also a supervisor of Emily Young, who is a Developer Intern.

An example tree is shown in the following diagram:

As you can see, each node should store more information than just an integer value. There should be an identifier, a name, and a role. Such data are stored as values of properties in an instance of the Person class, as shown in the following code snippet:

public class Person { public int Id { get; set; } public string Name { get; set; } public string Role { get; set; } public Person() { } public Person(int id, string name, string role) { Id = id; Name = name; Role = role; } } 

The class contains three properties ( Id, Name, and Role), as well as two constructors. The first constructor does not take any parameters, while the other takes three and sets values of particular properties.

Apart from creating a new class, it is also necessary to add some code in the Main method in the Program class. The necessary lines are as follows:

Tree<Person> company = new Tree<Person>(); company.Root = new TreeNode<Person>() { Data = new Person(100, "Marcin Jamro", "CEO"), Parent = null }; company.Root.Children = new List<TreeNode<Person>>() { new TreeNode<Person>() { Data = new Person(1, "John Smith", "Head of Development"), Parent = company.Root }, new TreeNode<Person>() { Data = new Person(50, "Mary Fox", "Head of Research"), Parent = company.Root }, new TreeNode<Person>() { Data = new Person(150, "Lily Smith", "Head of Sales"), Parent = company.Root } }; company.Root.Children[2].Children = new List<TreeNode<Person>>() { new TreeNode<Person>() {

 Data = new Person(30, "Anthony Black", "Sales Specialist"),
 Parent = company.Root.Children[2] } }; 

In the first line, a new instance of the Tree class is created. It is worth mentioning that the Person class is used as a type specified while creating new instances of Tree and TreeNode classes. Thus, you can easily store more than one simple data for each node.

The remaining lines of code...