Binary Tree Sort in C

Binary Tree Sort uses a Binary search tree. The various steps involved in such a sort would be –

1. Construct a binary tree with the given data (integers) such that all numbers to the left of a particular node say ‘nd’ is less than the number contained within the node and to the right, the numbers may be equal to or greater than the number contained in nd.
2. The sorted file is obtained by the the INORDER traversal of the binary search tree formed as per step1.

Suppose the input file is 3   9   15   6   0   2   10   1   15   7

The binary search tree formed is –

                  3
               /     \
              0       9
               \     /   \
                2   6     15
                     \   /  \
                      7  10 15
                           \ 
                            11  
INORDER traversal is 0 2 3 6 7 9 10 11 15 15

Algorithm for Binary Tree sort using Dynamic representation of Binary Tree is as follows –

Step 1: 

/* Binary search tree construction */

/* scans first number and make it the root of the search tree */

scanf("%d", & num);

PTREE = maketree(num);

/* while loop scans evvery other inputs till EOF */

while((scanf("%d", & num)) != EOF){

    p = q = PTREE; /* always initializes to root node for checking */

    /* while loop selects appropriate nodes for each inputed number*/

    while( q != NULL ){

        p = q;

        if(num < p->info)

           q = p->left;

        else

           q = p->right;

    }/*end while*/

    /* places the number at the appropriate node by creating the node*/

    if(num >= p->info)

       setright(p, num);

    else

       setleft(p, num);

}/*end while*/

/*end Binary search tree construction*/

Step2:

/*Sorts the Binary search tree in inorder */
/*routine for inorder traversal of a Binary tree intrav(PTREE)*/
if(PTREE != NULL){ /*root tree is PTREE */
       intrav(PTREE->left);
       printf("%d",PTRE->info);
       intrav(PTREE->right);
}

/*end sort*/

A complete C program for Binary Tree sort can be code as follows –

/* Binary Tree Sort*/
# include <stdio.h>
# include <stdlib.h>
struct node{
    int info;
    struct node * left;
    struct node * right;
};
typedef struct node *NODEPTR;

main(){
       NODEPTR maketree(int);
       void setleft(NODEPTR p, int);
       void setright(NODEPTR p, int);
       void intrav(NODEPTR PTREE);

       int num;
       NODEPTR p, q, PTREE;

       printf("\n Enter the numbers to be sorted>");
       scanf("%d", &num);

       PTREE = maketree(num); /*create root node*/
       
       printf("\nThe sorted numbers are>");

       while((scanf("%d",&num)) != EOF){
            p = q = PTREE;/*always initializes p,q to root node*/
< while( q != NULL ){ p = q; if(num < p->info) q = p->left; else q = p->right; }/*end while*/ /* places the number at the appropriate node by creating the node*/ if(num >= p->info) setright(p, num); else setleft(p, num); }/*end while*/ intrav(PTREE);/*calls for inorder traversal of the Binary Sort Tree with the root node PTREE*/ }/*end main*/ /*maketree()*/ NODEPTR maketree(int x){ NODEPTR getnode (void); NODEPTR p; p = getnode(); p->info = x;
              p->left = p->right = NULL;
              p->father = NULL;
              return(p);
     }

/*getnode()*/

     NODEPTR getnode(void){              
              return((NODEPTR) malloc(size of struct nodetype));
          }

/*setright()*/

     void setright(NODEPTR p, int x){
              NODEPTR maketree(int);
              if(p == NULL)
                    printf("\nVoid insertion\n");
              elseif(p->right != NULL)
                    printf("\nInvalid insertion\n");
              else
                    p->right = maketree(x);
              return;
           }

/*intrav()*/
void intrav(NODEPTR){
      if(tree != NULL){
           intrav(tree->left);/*traverse left subtree*/
           printf("%d",tree->info);/*visit root*/
           intrav(tree->right);/*traverse rightsubtree*/
      }
}

Efficiency of Binary Tree Sort

The efficiency of Binary Tree Sort depends on the original form of data. If original file is of sorted form, then comparisons of the order of O(n²) are required. If it is unsorted, then order is O(nlogn).

So average sorting time for Binary Tree Sort = O(nlogn) and for worst case is O(n²).