Binary search tree is a type of data structure which has various applications in computer science. One of the important application of binary search tree is sorting of data elements. In this method of sorting all the elements are arranged according to the binary search tree then in-order traversal will give all elements in ascending order. Example, to sorting 10 numbers 26, 5, 37, 1, 61, 11, 59, 48, 19 in ascending order we use following steps:

1. Arrange all the elements in binary search tree

2. find inorder traversal of binary search tree.

Inorder traversal is : 1 5 11 15 19 26 37 48 59 61 which is the required result.

Following is the code for implementation of sorting using binary search tree:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include<stdio.h> #include<conio.h> #include<malloc.h> struct node { int info; struct node *lchild; struct node *rchild; }*root=NULL; int main() { int no,i; printf("\nEnter 10 numbers to sort\n"); for(i=0;i<10;i++) { scanf("%d",&no); insert(&root,no); } printf("\nSorted numbers are\n"); inorder(root); getch(); } insert(struct node **s,int item) { if(*s==NULL) { *s=(struct node *)malloc(sizeof(struct node)); (*s)->info=item; (*s)->lchild=NULL; (*s)->rchild=NULL; } else { if(item<(*s)->info) { insert(&((*s)->lchild),item); } else { insert(&((*s)->rchild),item); } } } inorder(struct node *ptr) { if(ptr!=NULL) { inorder(ptr->lchild); printf(" %d ",ptr->info); inorder(ptr->rchild); } } |