C#, a new widely-used programming language, was developed to meet the rising needs of new workloads and paradigm shifts in the programming community. When comparing a Tree to other data structures, like an array or a LinkedList, you don't have to state the tree's size, making it more efficient. Linked lists require large O(n) operations for insertion, deletion, and searching, while Trees do not.
You will cover the basics of trees in C# in this tutorial. Using the examples in this tutorial, you will learn how to implement trees in C#.
What Are Trees in C#?
Data representation characterizes a hierarchical structure in the form of a tree. Every node in a tree comprises two distinct components (Data and References). The top node of the tree is referred to as the Root node, and the two products that fall beneath it are referred to as the "Left Subtree" and the "Right Subtree."
You can now go on to the next topic to learn about the types of trees now that you have a basic knowledge of the definition of Trees in C#.
What Are the Types of Trees in C#?
There are five types of Trees in C#:
-
General Tree
When there is no restriction on the hierarchy of the tree, it is known as a general Tree. Children of a Node in the General Tree are unlimited; all other trees are subsets to this one.
-
Binary Tree
A Binary tree is a type of tree where each parent can only have two children. The children are called left or right children and are one of the most utilized trees.
-
Binary Search Tree
A binary search tree (BST) is a binary tree with some additional constraints. In BST, the value of the node's left child must be less than or equal to the value of its parent, while the value of the right child must be greater than or equal to the value of the parent.
-
AVL Tree
An AVL Tree is an extension of a Binary search tree that can self-balance itself. Each node in an AVL tree is assigned a balancing factor used to determine whether a tree is balanced. A balance factor is a difference between the heights of the left subtree with the right subtree. In a perfect world, a balance factor can only be either 1, 0, or -1.
-
Red-Black Tree
Another type of self-balancing tree is a red-black tree. In a red-black tree, each node has an extra bit. This extra bit is often considered the node's color (red or black). These colors are used to ensure that the tree stays balanced when new things are added and removed. Even though the balance of the tree isn't perfect, it's good enough to cut the time it takes to search and keep it around O(log n) time, where n is the number of elements in the tree.
So far, you have learned about the types of trees. Now you will explore the basic operations of trees in C#.
Some Basic Operations on Trees in C#
There are three basic operations you can perform on a Tree.
-
Insertion
You can perform insertion on a tree in various ways. It depends on where you want to insert the new element.
-
Deletion
When it comes to deleting a node, it can get tricky when you need to decide what to do with its left and right children.
-
Search Operation
When searching for an element, you have to determine whether the current node matches the given value, or if you have to recur to the left and right sub-tree, repeating the same process.
Now, look at some of the terminologies related to Trees.
Some Terminology Related to Trees in C#
- Root Node: A root node is the first node from which the tree sprouts.
- Edge: An edge in a tree is the link that connects a parent and a child node.
- Parent Node: Any node with a child node attached to it is a parent node.
- Child Node: Any node with a parent node is a child node.
- Subtree: Each parent-child node pair makes a subtree of its own.
- Key: Every node is assigned a value in a tree structure, also called a key.
- Degree: Total number of children is the degree of that node.
- Sibling: All the nodes which share a parent are called sibling nodes.
- Height: The total number of edges that lie on the longest path from a leaf node to a node is the height of that node.
- Leaf Node: Any node which doesn't have any children is called a leaf node.
- Level: From top to bottom, each step is called a level.
Tree Traversal in Trees in C#
There are three types of tree traversal possible on Trees in C#
-
Inorder
In this you will first visit the left subtree (node->left child->right child) root then root node then the right subtree (node->left child->right child).
-
PreOrder
In this, you will first visit the root then the left subtree (node->left child->right child) then the right subtree (node->left child->right child).
-
PostOrder
In this, you will first visit the left subtree (node->left child->right child), then the right subtree (node->left child->right child), then, at last, the root.
Now that you have looked at various operations and traversal on trees in C#. implement them in a code editor.
Implementation of Trees in C#
You will be implementing the Trees in C# with the help of a code editor.
Code:
using System;
namespace C__Trees
{
class Node
{
public Node LtNode { get; set; }
public Node RtNode { get; set; }
public int Data { get; set; }
}
class BinaryTree
{
public Node Root { get; set; }
public bool Insert(int value)
{
Node before = null, after = this.Root;
while (after != null)
{
before = after;
//Is new node in left tree?
if (value < after.Data)
after = after.LtNode;
//Is new node in right tree?
else if (value > after.Data)
after = after.RtNode;
else
{
//Exist same value
return false;
}
}
Node newNode = new Node();
newNode.Data = value;
if (this.Root == null)//Tree ise empty
this.Root = newNode;
else
{
if (value < before.Data)
before.LtNode = newNode;
else
before.RtNode = newNode;
}
return true;
}
public Node Search(int value)
{
return this.Search(value, this.Root);
}
public void Delete(int value)
{
this.Root = Delete(this.Root, value);
}
private Node Delete(Node parent, int key)
{
if (parent == null) return parent;
if (key < parent.Data) parent.LtNode = Delete(parent.LtNode, key); else if (key > parent.Data)
parent.RtNode = Delete(parent.RtNode, key);
// if the value is the same as the parent's value, then this node is to be deleted
else
{
// the node with one or no child
if (parent.LtNode == null)
return parent.RtNode;
else if (parent.RtNode == null)
return parent.LtNode;
// node with two children: Get the inorder successor (smallest in the right subtree)
parent.Data = MinValue(parent.RtNode);
// Delete the inorder successor
parent.RtNode = Delete(parent.RtNode, parent.Data);
}
return parent;
}
private int MinValue(Node node)
{
int minv = node.Data;
while (node.LtNode != null)
{
minv = node.LtNode.Data;
node = node.LtNode;
}
return minv;
}
private Node Search(int value, Node parent)
{
if (parent != null)
{
if (value == parent.Data) return parent;
if (value < parent.Data)
return Search(value, parent.LtNode);
else
return Search(value, parent.RtNode);
}
return null;
}
public int GetDepth()
{
return this.GetDepth(this.Root);
}
private int GetDepth(Node parent)
{
return parent == null ? 0 : Math.Max(GetDepth(parent.LtNode), GetDepth(parent.RtNode)) + 1;
}
public void PreOrder(Node parent)
{
if (parent != null)
{
Console.Write(parent.Data + " ");
PreOrder(parent.LtNode);
PreOrder(parent.RtNode);
}
}
public void InOrder(Node parent)
{
if (parent != null)
{
InOrder(parent.LtNode);
Console.Write(parent.Data + " ");
InOrder(parent.RtNode);
}
}
public void PostOrder(Node parent)
{
if (parent != null)
{
PostOrder(parent.LtNode);
PostOrder(parent.RtNode);
Console.Write(parent.Data + " ");
}
}
}
class Program
{
static void Main(string[] args)
{
BinaryTree binTree = new BinaryTree();
binTree.Insert(11);
binTree.Insert(21);
binTree.Insert(78);
binTree.Insert(31);
binTree.Insert(101);
binTree.Insert(51);
binTree.Insert(82);
Node node = binTree.Search(51);
int depth = binTree.GetDepth();
Console.WriteLine("PreOrder Traversal:");
binTree.PreOrder(binTree.Root);
Console.WriteLine();
Console.WriteLine("InOrder Traversal:");
binTree.InOrder(binTree.Root);
Console.WriteLine();
Console.WriteLine("PostOrder Traversal:");
binTree.PostOrder(binTree.Root);
Console.WriteLine();
binTree.Delete(78);
binTree.Delete(82);
Console.WriteLine("After Remove Operation, Preorder Traversal:");
binTree.PreOrder(binTree.Root);
Console.WriteLine();
Console.ReadLine();
}
}
}
Applications of Trees in C#
- The XML Parser employs tree Algorithms.
- In machine learning, a decision-based algorithm is used based on trees.
- Tree data structures are also used in databases for indexing.
- Tree structures are also used by Domain name servers (DNS).
- File Explorer/mobile, computer, or any computer BST used in computer graphics.
By now, you have a good grip on the technical aspects of Trees in C#.
Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!
Next Steps
The next lesson in your C# training can be "Graphs in C#." There are nodes and edges in a graph, which is a data structure that isn't straight. If you look at a graph, you can see lines or arcs that connect any two points in the graph. These points are called "nodes."
Simplilearn is the world's most popular online boot camp for learning digital economy skills, and it's here to help you do just that. Digital marketing and data science are just a few subjects we cover in-depth in our online courses.
The Caltech CTME and the Indian Institute of Technology, Kanpur, collaborated with Simplilearn to deliver their Software Development courses. In addition to more advanced topics like Competitive Programming, these courses teach the fundamentals of data structures and algorithms. Data structures including trees, graphs, and queues will be taught as a software developer.
The comments section below is open for questions and comments about this 'Trees in C#' tutorial. Happy learning!
