Implementation of Tree

The tree data structure can be formed by using pointers to create the nodes dynamically. As shown below, the memory tree can be expressed as follows:

• The memory representation of the tree data structure is shown in the diagram above. 
• The node in the above structure has three fields. 
• The data is stored in the second field, while the left child's address is stored in the first field and the right child's address is stored in the third field.

A node's structure can be defined as follows in programming:

struct node  

{  

  int data;  

struct node *left;  

struct node *right;   

}

• Because binary trees can only have two children, and generic trees can have more than two, the above structure can only be defined for binary trees. 
• In comparison to the binary tree, the structure of the node in generic trees would be different.

Applications of trees

• Trees are used to store data in a hierarchical form that is naturally hierarchical. Consider the file system. The file system, files, and folders are saved on the disc drive in the form of naturally hierarchical data in the form of trees.
• Organize Data: It is used to arrange data in order to make insertion, deletion, and searching more efficient. A binary tree, for example, has a logN time for searching an element.
• Trie: The dictionary is stored in a specific type of tree called a trie. It's a quick and easy approach to do dynamic spell checking.
• Heap: Heap is a tree data structure that is also built using arrays. Priority queues are implemented using it.
• B-Tree and B+Tree: B-Tree and B+Tree are tree data structures that are used in databases to implement indexing.
• Routing table: In routers, the tree data structure is also used to store data in routing tables.

Types of Tree data structure

Generic tree: 

• The generic tree is one of the different forms of tree data structures. A node in the general tree can have either 0 or maximum n nodes. 
• The degree of the node is not limited in any way (the number of nodes that a node can contain). 
• A root node is the node at the very top of a generic tree. Subtrees are the offspring of the parent node.

• A generic tree can have an infinite number of subtrees. The subtrees in the general tree are unordered because the nodes in the subtrees cannot be ordered.
• A downward edge runs through every non-empty tree, and these edges are connected to the nodes known as child nodes. 
• Level 0 is assigned to the root node. Sibling nodes are those that have the same parent.

Binary tree: 

• The name binary implies two numbers, namely 0 and 1. Each node in a binary tree can have a maximum of two child nodes. 
• The term "utmost" refers to whether a node has zero, one, or two nodes.

Binary Search Tree: 

• A binary search tree is a non-linear data structure in which one node is connected to a n number of other nodes. 
• It's a data structure with nodes. In a binary search tree, a node can be represented by three fields: data portion, left-child, and right-child. 
• In a binary search tree, a node can be connected to the utmost two child nodes, resulting in the node having two pointers (left child and right child pointer).
• Every node in the left subtree must have a value less than the root node's value, and every node in the right subtree must have a value greater than the root node's value.

C++ Programming Code for Selection Sort.

C++ Programming Code for Selection Sort.

Selection Sort

/* C++ Program - Selection Sort */		

#include<iostream.h>
#include<conio.h>
void main()
{
	clrscr();
	int size, arr[50], i, j, temp;
	cout<<"Enter Array Size : ";
	cin>>size;
	cout<<"Enter Array Elements : ";
	for(i=0; i<size; i++)
	{
		cin>>arr[i];
	}
	cout<<"Sorting array using selection sort...\n";
	for(i=0; i<size; i++)
	{
		for(j=i+1; j<size; j++)
		{
			if(arr[i]>arr[j])
			{
				temp=arr[i];
				arr[i]=arr[j];
				arr[j]=temp;
			}
		}
	}
	cout<<"Now the Array after sorting is :\n";
	for(i=0; i<size; i++)
	{
		cout<<arr[i]<<" ";
	}
	getch();
}

Output:-

Insertion Operation in Max Heap

Finding Maximum Value Operation in Max Heap

It's easy to find the node in a max heap with the highest value. The root node in the max heap has the highest value of all the other nodes in the max heap. As a result, we can display the value of the root node as the maximum value in the max heap.

Insertion Operation in Max Heap

Insertion Operation in max heap is performed as follows...

• Step 1: Insert the newNode as last leaf from left to right.
• Step 2: Compare newNode value with its Parent node.
• Step 3: If newNode value is greater than its parent, then swap both of them.
• Step 4: Repeat step 2 and step 3 until newNode value is less than its parent nede (or) newNode reached to root.

Example
Consider the above max heap. Insert a new node with value 85.

• Step 1: Insert the newNode with value 85 as last leaf from left to right. That means newNode is added as a right child of node with value 75. After adding max heap is as follows.
• 
• Step 2: Compare newNode value (85) with its Parent node value (75). That means 85 > 75
• 
• Step 3: Here newNode value (85) is greater than its parent value (75), then swap both of them. After swapping, the max heap is as follows...
• 
  
• 
• Step 4: Now, again compare the newNode value (85) with its parent node value (89).
• 
• Here, the newNode value (85) is smaller than its parent node value (89). So, we stop the insertion process. Finally, the max heap after insertion of a new node with value 85 is as follows...
• 

Merge sorting in c

C Program to Implement MERGE SORT

Merge Sort

#include<stdio.h>

#include<stdlib.h>

void Merge(int a[], int tmp[], int lpos, int rpos, int rend)

{

    int i, lend, n, tmppos;

    lend = rpos - 1;

    tmppos = lpos;

    n = rend - lpos + 1;

    while(lpos <= lend && rpos <= rend)

    {

        if(a[lpos] <= a[rpos])

            tmp[tmppos++] = a[lpos++];

        else

            tmp[tmppos++] = a[rpos++];




    }

    while(lpos <= lend)

        tmp[tmppos++] = a[lpos++];

    while(rpos <= rend)

        tmp[tmppos++] = a[rpos++];

    for(i = 0; i < n; i++, rend--)

        a[rend] = tmp[rend];

}

void MSort(int a[], int tmp[], int left, int right)

{

    int center;

    if(left < right)

    {

        center = (left + right) / 2;

        MSort(a, tmp, left, center);

        MSort(a, tmp, center + 1, right);

        Merge(a, tmp, left, center + 1, right);

    }

}

void MergeSort(int a[], int n)

{

    int *tmparray;

    tmparray = malloc(sizeof(int) * n);

    MSort(a, tmparray, 0, n-1);

    free(tmparray);

}

main()

{

    int i, n, a[10];

    printf("Enter the number of elements :: ");

    scanf("%d",&n);

    printf("Enter the elements :: ");

    for(i = 0; i < n; i++)

    {

        scanf("%d",&a[i]);

    }

    MergeSort(a,n);

    printf("The sorted elements are ::  ");

    for(i = 0; i < n; i++)

        printf("%d  ",a[i]);

    printf("\n");

}

OUTPUT:

Enter the number of elements :: 7
Enter the elements :: 70 60 50 40 10 20 30
The sorted elements are ::  10  20  30  40  50  60  70