Linked Lists

What is Linked Lists? Singly Linked Lists Doubly Linked Lists Circular Linked Lists Header Linked Lists

Stacks

What is Stack? Push Operation Pop Operation Peek Operation Linked Stack Multiple Stacks

Queues

What is Queues? Linear Queue

Searching

What is Searching? Linear Search Binary Search Interpolation Search Jump Search

Sorting

What is Sorting? Bubble Sort Insertion Sort Selection Sort Merge Sort Quick Sort Radix Sort Heap Sort Shell Sort Tree Sort

Hashing

What is Hashing? What is Collision?
The ones who are crazy enough to think they can change the world are the ones who do.
- Steve Jobs
NEXT

Tree Sort

The properties of binary search tree is completely make use of tree sort algorithm. The tree sort algorithm first builds a binary search tree using the elements in an array which is to be sorted and then does an in-order traversal so that the numbers are retrived in a sorted order.

Advantages - Tree Sort

  • The main advantage of tree sort algorithm is that we can make changes very easily as in a linked list.
  • Sorting in Tree sort algorithm is as fast as quick sort algorithm.

Disadvantages - Tree Sort

  • The worst case occur when the elements in an array is already sorted.
  • In worst case, the running time of tree sort algorithm is 0 (n2).

C program - Tree Sort

Here is the program to demonstrate Tree Sort.

tree-sort.c 
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct node
{
int data;
struct node *left, *right;
};
struct node *root;
void ins(struct node *, int, int);
void inser(struct node *, int);
void display(struct node *);
int main()
{
int choice, no = 0, parentnode;
root = (struct node *) malloc (sizeof(struct node));
printf("\n Enter a number for parent node : ");
scanf("%d",&parentnode);
root -> data = parentnode;
root -> left = root -> right = NULL;
do{
printf("\n 1.Add element");
printf("\n 2.Sort");
printf("\n 3.Exit");
printf("\n Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter the element to insert : \n");
scanf("%d",&no);
inser(root, no);
break;
case 2:
printf("\n Sorted elements are : \n");
display(root);
break;
default:
printf("\n Invalid press...");
exit(0);
}
}while(choice < 3);
return 0;
}
void ins(struct node *n, int value, int opt)
{
struct node *t;
t = (struct node *)malloc (sizeof (struct node));
t -> data = value;
t -> left = t -> right = NULL;
if(opt == 1)
n -> left = t;
else
n -> right = t;
printf("%d is inserted",value);
if(opt == 1)
printf(" at the left \n");
else
printf(" at the right \n");
}
void inser(struct node *t,int x)
{
if(t -> data > x)
if(t -> left == NULL)
ins(t,x,1);
else
inser(t -> left, x);
else if(t -> data < x)
if(t -> right == NULL)
ins(t, x, 2);
else
inser(t -> right,x);
else
printf(" Element is already exist in the list ");
}
void display(struct node *p)
{
if(p != NULL)
{
display(p -> left);
printf("%5d",p -> data);
display(p -> right);
}
}
Enter a number for parent node : 5 
1.Add element
2.Sort
3.Exit 
Enter your choice : 1
Enter the element to insert 4
4 is inserted at the left
1.Add element
2.Sort
3.Exit 
Enter your choice : 1
Enter the element to insert 6
6 is inserted at the right
1.Add element
2.Sort
3.Exit 
Enter your choice : 2
Sorted elements are :
4 5 6
1.Add element
2.Sort
3.Exit 
Enter your choice : 3
NEXT

Related to Tree Sort

Take a test

Report Us

We may make mistakes(spelling, program bug, typing mistake and etc.), So we have this container to collect mistakes. We highly respect your findings.

Report

Programming

Electrical

Interview

© Copyright 2019