Binary Tree Sort

This has two phases. First phase is creating a binary search tree using the given array elements. Second phase is traverse the given binary search tree in inorder, thus resulting in a sorted array.

Performance
The average number of comparisons for this method is O(nlog₂n)
But in the worst case, the number of comparisons are reduced by O(n²), a case which arises when the sort tree is severely unbalanced .


/****** C Program For Implementation Of Binary Sort ***/

#define TRUE 1
#define FALSE 0

struct btreenode
{
struct btreenode *rightchild;
int data;
struct btreenode *leftchild;
};

insert(struct btreenode **sr,int num)
{
if(*sr==NULL)
{
*sr=malloc(sizeof(struct btreenode));

(*sr)- >leftchild=NULL;
(*sr)- >data=num;
(*sr)- >rightchild=NULL;
return;
}
else
{
if(num< (*sr)- >data)
insert(&((*sr)- >leftchild),num);
else
insert(&((*sr)- >rightchild),num);
}
return;
}

inorder(struct btreenode *sr)
{
if(sr!=NULL)
{
inorder(sr- >leftchild);
printf("%d ",sr- >data);
inorder(sr- >rightchild);
}
else
return;
}

postorder(struct btreenode *sr)
{
if(sr!=NULL)
{
postorder(sr- >rightchild);
printf("%d ",sr- >data);
postorder(sr- >leftchild);
}
else
return;
}

void main()
{
struct btreenode *bt;
int req,i=0,num,a[10],no;

bt=NULL;
clrscr();

while(i < 5)
{
printf("\nEnter value to be inserted: ");
scanf("%d",&a[i]);
insert(&bt,a[i]);
i++;
}
clrscr();
printf("\n\nSorted Binary tree in ascending order== > \n\n");
inorder(bt);
printf("\n\nSortred binary tree in descending order== >\n\n");
postorder(bt);
getch();
}


/************************** OUTPUT ***********************

Enter value to be inserted: 9

Enter value to be inserted: 8

Enter value to be inserted: 4

Enter value to be inserted: 5

Enter value to be inserted: 7


Sorted Binary tree in ascending order== >

4 5 7 8 9

Sortred binary tree in descending order== >

9 8 7 5 4 */